A* 算法 - 起点

Question

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

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

Answer 1

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

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

Answer 2

它对每个特定的迷宫（假设有一些块使它成为一个迷宫）和算法的细节都有所不同，但两者都不是始终如一的更好，因为你总是可以交换起点和目标。

为了证明它的重要性，考虑一个简单的迷宫，其中有一个大的 L 形块（进一步向上延伸）

  |
  |                        
  |        a
  |  |  |
  |    
  |---------
 b

从 a 开始，您似乎会向左穿过整个广场。 从b开始向右直行，然后向上，向左一步