最短路径 A* f(n) = g(n) + h(n)

Question

当你使用A*时，它会选择最接近目标的最佳节点，对吗？ （使用 f(n) = g(n) + h(n)） （使用 h(n) 的曼哈顿距离）

但是如果起点和目标之间有墙怎么办？我无法用语言解释它，但我会展示一张图片。

_{（来源：uploadir.com）}

如果A*选择了距离目标最近的节点，为什么路径不是红圈的那个？但那是绿色圈起来的。我真的不明白 A* 特别是当有无法通过的单元格/图块/节点/等时。 （墙壁）。另外，您还可以在视频 http://www.youtube.com/watch?v=DINCL5cd_w0（路径查找算法（A*、Dijkstra、双向 BFS））中看到我在 1 处制作的图片： 20

Answer 1

A* 还考虑当前路径的长度以及到目标的距离。所有可能的路径均已扩展，但优先考虑以下路径：

1. 距离目标最近了
2. 最短

路径成本 f(n) 等于上一步的成本 g(n) 加上基于到目标距离的因子 h(n)。因此，路径每经过一个额外的网格空间，路径的成本就会增加。这将有效地在短路径和直接到达目标的路径之间建立平衡。

因此，当您的示例路径再次连接起来时，紫色路径是最短的，因此这将是首先扩展的路径，并最终首先到达目标。

Udacity 有一门课程：机器人汽车编程，其中有关于 A*（和类似）算法的很好的部分。

Answer 2

正如你所说，A*根据f(n)=g(n)+h(n)选择当前最佳路径，其中g(n)是当前计算的成本，h(n)是剩余成本的估计。只有当前最有希望的节点（f(n)最小的节点）才会被扩展。因此，当蓝色和紫色路径分叉时（我们称之为A点），它会径直走向墙壁，因为那里的h(n)更小，整个f(n)也变小。

请记住，h 函数通常是问题的松弛 - 在您的情况下，它可能是到目标的直线距离。因此，整个f变得更小。如果当前 f 变得大于对未追踪路径的估计，则将考虑另一条路径。

因此，它不经过紫色路径的可能原因是蓝色路径中每个点的当前 f 值总是小于紫色路径中的值。

这对我来说很奇怪，因为你的 g 总是在增加，并且蓝色路径中有很多点比 A 点距离目标更远。不过，如果你想确定，你应该做一些调试并验证每个点每个未追踪点的 f、g 和 h 值与当前追踪路径的值。