我正在研究 A* 寻路算法的定义，但似乎在不同的地方定义略有不同。
区别在于遍历节点的后继节点时执行的操作，以及发现后继节点在已关闭列表中。
- 一种方法（由维基百科和这篇文章 提出）指出：如果后继节点在已关闭列表中，则忽略它
- 另一种方法（例如，这里和这里提出）指出：如果后继节点在已关闭列表中，则检查其成本。如果成本高于当前计算的分数，则从已关闭列表中删除该项目以供将来检查。
我很困惑 – 哪种方法是正确的？ 直观上，第一种方法对我来说更有意义，但我想知道定义的区别。 是否其中一个定义是错误的，或者它们在某种程度上是同构的？
回答：
只有当到达任何重复状态的最佳路径始终是第一个被遵循的路径时，第一种方法才是最佳的。 如果启发式函数具有一致性（也称为单调性）的属性，则此属性成立。 如果对于每个节点n和n的每个后继节点n'，从n到达目标的估计成本不大于从n到达n'的步进成本加上从n到达目标的估计成本，则启发式函数是一致的。
如果启发式函数仅仅是可容许的，即它从不高估到达目标的成本，则第二种方法才是最佳的。
每个一致的启发式函数也是可容许的。 尽管一致性比可容许性更严格，但人们必须非常努力地才能设计出可容许但不一致的启发式函数。
因此，即使第二种方法更通用，因为它适用于严格更大的启发式函数子集，但在实践中第一种方法通常就足够了。
参考文献：书籍人工智能：一种现代方法中4.1 知情（启发式）搜索策略一节的子节A* 搜索：最小化总估计解决方案成本。
