algorithm - A* 算法 - 起点

Question

我在一个二维网格迷宫中，你只能水平和垂直移动。边成本为 1，我使用曼哈顿距离来估计从节点到目标的距离。

我的问题是，如果您从当前节点开始寻找到达目标的路径，或者从目标节点开始并找到返回当前节点的路径，这是否会有所不同？

Answer 1

不，向前或向后工作没有任何区别。请记住，在实际应用中，您通常有许多目标节点，但几乎总是只有一个起始节点。如果只想到达一个目标节点，最好从起始节点开始向前搜索。

另请注意，如果使用可接受的启发式算法，A* 将产生最佳解决方案。可能有多个同样最优的解决方案，因此向后搜索而不是向前搜索可能会导致您找到不同但同样好的解决方案。