A-star的曼哈顿启发函数(A*)

Question

我在这里找到了这个算法.

我有一个问题,我似乎无法理解如何设置和传递我的启发式功能.

    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个函数,一个距离和一个估计函数.

使用曼哈顿启发式距离函数,我需要采用2个参数.我是否需要修改他的来源并将其更改为接受TNode的2个参数,以便我可以将曼哈顿估算值传递给它？这意味着第4个参数将如下所示:

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));
    }

Answer 1

好问题.我同意这篇文章令人困惑.我已更新它以解决您的问题.

首先,回答你问的问题:你应该修改给出的代码来采取不同的功能吗？如果你想,当然,但你当然不必.我的建议是传递算法想要的功能,因为这是它需要的功能.为什么传递算法不需要的信息？

怎么做？

我给出的A*算法有两个功能.

第一个函数给出两个给定相邻节点之间的精确距离.

第二个函数给出给定节点和目标节点之间的估计距离.

这是你没有的第二个功能.

如果您有一个函数可以给出两个给定节点之间的估计距离,并且您需要一个函数来给出给定节点和目标节点之间的估计距离,那么只需构建该函数:

Func<Node, Node, double> estimatedDistanceBetweenTwoNodes = whatever;
Func<Node, double> estimatedDistanceToDestination = n=>estimatedDistanceBetweenTwoNodes(n, destination);

而且你已经完成了.现在您拥有了所需的功能.

通过将一个参数固定为特定值将双参数函数转换为单参数函数的这种技术称为"部分函数应用",并且在函数编程中非常常见.

这一切都清楚了吗？

现在谈到第二个也是更严重的问题.正如我在文章中所描述的那样,算法的正确操作是基于保守的估计函数.你能保证曼哈顿的距离永远不会高估吗？这似乎不太可能.如果网格中的任何地方都有"对角线"街道,那么曼哈顿距离会高估两点之间的最佳距离,而A*算法将无法找到它.大多数人使用欧氏距离(又称L2范数)作为A*算法,因为两点之间的最短距离根据定义并不是高估. 你为什么使用曼哈顿距离？ 我很困惑你为什么认为这是一个好主意.