A*算法的正确表述

Question

14

我正在研究A*寻路算法的定义，不同的地方似乎有些不同。

区别在于当经过节点的后继节点时，在发现后继节点已在关闭列表中时所执行的操作。

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

- eliben

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- namin · Accepted Answer

第一种方法仅在到达任何重复状态的最优路径始终是第一条被遵循的路径时才最优。当启发式函数具有一致性（也称单调性）属性时，此属性成立。如果每个节点n和n'的每个继承者，从n到n'的步骤成本加上从n到目标的预计成本不大于从n到目标的估计成本，则启发式函数是一致的。

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

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

因此，即使第二种方法更为通用，因为它使用一个严格更大的启发式函数子集，但第一种方法在实践中通常就足够了。

参考资料：书籍《人工智能：一种现代方法》第4.1节“信息（启发式）搜索策略”中的小节“A*搜索：最小化总预测解决方案成本”。