正确制定A*算法

我正在研究A*路径寻找算法的定义,它似乎在不同的地方有所不同.

不同之处在于在遍历节点的后继者时执行的操作,并且发现后继者在关闭列表上.

一种方法(由维基百科和本文建议)说:如果后继者在封闭列表中,则忽略它

另一种方法(例如,此处和此处建议)说:如果后继者在封闭列表中,则检查其成本.如果它高于当前计算的分数,则从关闭的列表中删除该项目以供将来检查.

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

只有在始终首先遵循任何重复状态的最佳路径时,第一种方法才是最佳的.如果启发式函数具有一致性(也称为单性),则此属性成立.启发式功能是一致的,如果,每一个节点n和每一个继任者n'的n,到达目标的估计成本n并不比前往步骤成本较大n',从n加到达离目标的估计成本n.

如果启发函数仅是可接受的,那么第二种方法是最优的,也就是说,它永远不会过高估计达到目标的成本.

每个一致的启发函数也是可以接受的.尽管一致性是一个比可接受性更严格的要求,但是必须非常努力地编写可接受但不一致的启发式函数.

因此,即使第二种方法更通用,因为它与严格更大的启发函数子集一起工作,第一种方法在实践中通常是足够的.

参考:A*搜索小节:最小化估计解决方案总成本的第4.1节" 人工智能:现代方法 "一书的知情(启发式)搜索策略.