algorithm - A*算法的正确表述

Question

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

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

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

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

Answer 1

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

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

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

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

引用:《人工智能:A》一书4.1 知情(启发式)搜索策略部分A* 搜索:最小化总估计解决方案成本现代方法。