5

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

我有一个问题，我似乎无法理解如何设置和传递我的启发式函数。

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

2 回答 2

8

好问题。我同意这篇文章令人困惑。我已对其进行了更新以解决您的问题。

首先，回答您提出的问题：您是否应该修改给出的代码以采用不同的功能？如果你愿意，当然可以，但你当然不必。我的建议是传递算法想要的函数，因为那是它需要的函数。为什么要传递算法不需要的信息？

怎么办？

我给出的 A* 算法有两个函数。

第一个函数给出了两个给定的相邻节点之间的准确距离。

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

这是您没有的第二个功能。

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

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

你完成了。现在你有了你需要的功能。

这种通过将其中一个参数固定为某个值来将二参数函数变为一参数函数的技术称为“部分函数应用”，在函数式编程中极为常见。

这一切都清楚了吗？

现在讨论第二个更严重的问题。正如我在文章中所描述的，算法的正确操作取决于估计函数是保守的。你能保证曼哈顿距离永远不会高估吗？这似乎不太可能。如果网格中的任何地方都有一条“对角线”街道，那么曼哈顿距离会高估两点之间的最佳距离，而 A* 算法将找不到它。大多数人在 A* 算法中使用欧几里得距离（又名 L2 范数），因为根据定义，两点之间的最短距离不会被高估。 你为什么使用曼哈顿距离？ 我很困惑为什么你认为这是一个好主意。

于 2010-12-26T16:01:32.693 回答
0

是的，您需要修改代码，因为无法estimate在其中安装带有两个TNode参数的方法。

于 2010-12-26T03:00:34.820 回答