14

我正在查看 A* 寻路算法的定义，它在不同地方的定义似乎有所不同。

不同之处在于遍历节点的后继节点时执行的操作，并发现后继节点在封闭列表中。

  • 一种方法（由Wikipedia和本文建议）说：如果继任者在封闭列表中，则忽略它
  • 另一种方法（例如，在此处和此处建议）说：如果继任者在封闭列表中，请检查其成本。如果它高于当前计算的分数，则从封闭列表中删除该项目以供将来检查。

我很困惑 - 哪种方法是正确的？直觉上，第一个对我来说更有意义，但我想知道定义上的差异。其中一个定义是错误的，还是它们在某种程度上是同构的？

4

1 回答 1

11

只有当通往任何重复状态的最优路径总是首先被遵循时，第一种方法才是最优的。如果启发式函数具有一致性属性（也称为单调性），则此属性成立。启发式函数是一致的，如果对于每个节点n和 的每个后继者n'，n到达目标的估计成本n不大于到达目标的步骤成本加上到达目标的估计n'成本。nn

如果启发式函数仅仅是可接受的，则第二种方法是最优的，也就是说，它永远不会高估达到目标的成本。

每个一致的启发式函数也是可接受的。尽管一致性是比可接纳性更严格的要求，但必须非常努力地构造可接纳但不一致的启发式函数。

因此，即使第二种方法更通用，因为它适用于严格更大的启发式函数子集，但第一种方法在实践中通常就足够了。

参考：A* 搜索小节：最小化总估计解决方案成本在《人工智能：现代方法》一书的第4.1 节知情（启发式）搜索策略中。

于 2009-01-03T12:22:08.727 回答