algorithm - A *算法-起点

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

我的问题是,如果您从当前节点开始寻找通往目标的方法,还是从目标节点开始并找到返回当前节点的方式,这是否有所不同?

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

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

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

为了说明这一点,请考虑一个具有大L形块的简单迷宫,如下所示(进一步向上延伸)

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

从看来,您将遍历左侧的整个正方形。 从b开始,您将向右直行,然后向上,向左走一步

转载请注明来自askonline.tech,本文标题:algorithm - A *算法-起点


 Top