我发现这个算法here。
我有一个问题，我似乎无法理解如何设置和传递我的启发式函数。
static public Path<TNode> AStar<TNode>(TNode start, TNode destination,
Func<TNode, TNode, double> distance,
Func<TNode, double> estimate) where TNode : IHasNeighbours<TNode>
{
var closed = new HashSet<TNode>();
var queue = new PriorityQueue<double, Path<TNode>>();
queue.Enqueue(0, new Path<TNode>(start));
while (!queue.IsEmpty)
{
var path = queue.Dequeue();
if (closed.Contains(path.LastStep))
continue;
if (path.LastStep.Equals(destination))
return path;
closed.Add(path.LastStep);
foreach (TNode n in path.LastStep.Neighbours)
{
double d = distance(path.LastStep, n);
var newPath = path.AddStep(n, d);
queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
}
}
return null;
}
如您所见，它接受两个函数，一个距离函数和一个估计函数。
使用曼哈顿启发式距离函数，我需要采取2个参数。我是否需要修改他的来源，并将其更改为接受Tnode的2个参数，以便我可以将曼哈顿的估计传递给它？这意味着第四个参数将如下所示：
Func<TNode, TNode, double> estimate) where TNode : IHasNeighbours<TNode>
并将估计函数更改为：
queue.Enqueue(newPath.TotalCost + estimate(n, path.LastStep), newPath);
我在曼哈顿的职责是：
private float manhattanHeuristic(Vector3 newNode, Vector3 end)
{
return (Math.Abs(newNode.X - end.X) + Math.Abs(newNode.Y - end.Y));
}
最佳答案
好问题。我同意这篇文章令人困惑。我已经更新了它来解决你的问题。
首先，回答您提出的问题：您是否应该修改给定的代码以获得不同的函数？如果你想的话，当然可以，但你当然不必。我的建议是传递算法需要的函数，因为这是它需要的函数。为什么要传递算法不需要的信息？
怎么办？
我给出的a*算法有两个函数。
第一个函数给出了两个相邻节点之间的精确距离。
第二个函数给出给定节点和目标节点之间的估计距离。
这是你没有的第二个功能。
如果有一个函数提供两个给定节点之间的估计距离，并且需要一个函数提供给定节点和目标节点之间的估计距离，则只需构建该函数：
Func<Node, Node, double> estimatedDistanceBetweenTwoNodes = whatever;
Func<Node, double> estimatedDistanceToDestination = n=>estimatedDistanceBetweenTwoNodes(n, destination);
你完了。现在你有了你需要的功能。
通过将一个参数固定到某个值，将两个参数函数转换成一个参数函数的技术称为“部分函数应用”，它在函数编程中非常常见。
明白了吗？
接下来是第二个更严重的问题。正如我在文章中所描述的，算法的正确操作取决于估计函数的保守性。你能保证曼哈顿的距离永远不会高估吗？这似乎不太可能。如果网格中有一条“对角线”街道，那么曼哈顿距离高估了两点之间的最佳距离，而a*算法将找不到它。大多数人在a*算法中使用欧几里德距离（也称为l2范数），因为根据定义，两点之间的最短距离不是高估的。你为什么要用曼哈顿的距离？我很困惑你为什么认为这是个好主意。