Eli*_*sky 14 algorithm artificial-intelligence a-star dijkstra path-finding
我正在研究A*路径寻找算法的定义,它似乎在不同的地方有所不同.
不同之处在于在遍历节点的后继者时执行的操作,并且发现后继者在关闭列表上.
我很困惑 - 哪种方法是正确的？直觉上,第一个对我来说更有意义,但我想知道定义的差异.其中一个定义是错误的,还是它们在某种程度上是同构的？
只有在始终首先遵循任何重复状态的最佳路径时,第一种方法才是最佳的.如果启发式函数具有一致性(也称为单性),则此属性成立.启发式功能是一致的,如果,每一个节点n和每一个继任者n'的n,到达目标的估计成本n并不比前往步骤成本较大n',从n加到达离目标的估计成本n.
如果启发函数仅是可接受的,那么第二种方法是最优的,也就是说,它永远不会过高估计达到目标的成本.
每个一致的启发函数也是可以接受的.尽管一致性是一个比可接受性更严格的要求,但是必须非常努力地编写可接受但不一致的启发式函数.
因此,即使第二种方法更通用,因为它与严格更大的启发函数子集一起工作,第一种方法在实践中通常是足够的.
参考:A*搜索小节:最小化估计解决方案总成本的第4.1节" 人工智能:现代方法 "一书的知情(启发式)搜索策略.