A*算法-起始点

Question

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

我的问题是，如果您从当前节点开始查找到达目标的方法，还是从目标节点开始并找到返回到当前节点的方法，是否会有所不同？

Answer 1

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

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

Answer 2

它对于每个特定的迷宫(假设有一些块使其成为迷宫)和算法的细节都是不同的，但两者都不是一致的更好，因为你总是可以交换开始和目标。

为了说明它的重要性，考虑一个简单的迷宫，其中有一个大的L型块，如下所示(进一步向上扩展)

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

从a开始，你似乎会从左边穿过整个正方形。从b一直往右走，然后往上走，再向左走一步。