A*算法的正确表述

Question

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

区别在于遍历节点的后继节点并发现后继节点位于关闭列表中时所执行的操作。

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

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

Answer 1

仅当到达任何重复状态的最佳路径始终是第一个遵循的状态时，第一种方法才是最佳的。如果启发式函数具有以下属性，则该属性成立 一致性 （也叫 单调性）。启发式函数是一致的，如果对于每个节点 n 以及每一位后继者 n' 的 n, ，达到目标的估计成本 n 不大于到达的步数成本 n' 从 n 加上达到目标的估计成本 n.

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

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

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

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