在计算曼哈顿距离时，应该计算到终点还是起点？

Question

我正在尝试学习A*算法（在网格图案中应用），并认为在找到最短路径之前，需要计算离起点的距离。我正在按照此处指南进行操作：https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2 该指南显示了每个正方形的曼哈顿距离的图像，以及起始正方形为绿色，结束正方形为蓝色。然而，确定距离是否有更好的方法时，倒过来计算距离是不是更合理？A*选择连接到目标的最短距离的正方形，对吗？因此，如果我们从终点开始，询问连接到起点的最低值（在这种情况下为17），那么就可以去那里，然后依次去15等等。 子问题：图像中远离起点的距离似乎基于通过Von Neumann邻居移动，因此在返回过程中您肯定不能对角线行进，对吗？

- Robert Flook

---

A* 从起点到终点访问节点。另一方面，D* 从终点到起点访问它们。我想你也可以用 A* 实现相同的效果：如果你的边缘成本是对称的，从 X 到 Y 的最短路径与从 Y 到 X 的最短路径相同。 - dc_Bita98

Answer 1

其实很简单：

F = G + H
F 是节点的总成本。
G 是当前节点和起始节点之间的距离。
H 是启发式——从当前节点到终点节点的估计距离。

网格中的数字代表G（而不是启发式）。G 是从起点到实际距离。
H 应该计算到终点。

- c0der

---

那么A*算法实际上并没有预先填充所有可能节点的H值；而是在访问节点时计算该值？ - Robert Flook

这取决于具体实现。您可以预先计算所有节点的H值，也可以动态计算。典型的实现是动态计算：获取一个邻居节点，计算f：g = g(parent) + 1和h = heuristic(neighbor)，然后将其添加到open列表中。 - c0der