A*算法的正确表述
我正在查看 A* 寻路算法的定义，它似乎在不同的地方定义有所不同。
区别在于遍历节点的后继节点并发现后继节点位于关闭列表中时所执行的操作。
- 一种方法（由 Wikipedia 和 这篇文章）说：如果继任者处于关闭状态列表，忽略它
- 另一种方法（建议 此处和此处，例如）说：如果后继者在封闭列表中，则检查其成本。 如果它高于当前计算的分数，则从关闭列表中删除该项目以供将来检查。
我很困惑 - 哪种方法是正确的？ 直觉上，第一个对我来说更有意义，但我想知道定义上的差异。 其中一个定义是错误的，还是它们在某种程度上是同构的？
I'm looking at definitions of the A* path-finding algorithm, and it seems to be defined somewhat differently in different places.
The difference is in the action performed when going through the successors of a node, and finding that a successor is on the closed list.
- One approach (suggested by Wikipedia, and this article) says: if the successor is on the closed list, just ignore it
- Another approach (suggested here and here, for example) says: if the successor is on the closed list, examine its cost. If it's higher than the currently computed score, remove the item from the closed list for future examination.
I'm confused - which method is correct ? Intuitively, the first makes more sense to me, but I wonder about the difference in definition. Is one of the definitions wrong, or are they somehow isomorphic ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
仅当到达任何重复状态的最佳路径始终是第一个遵循的状态时，第一种方法才是最佳的。 如果启发式函数具有一致性（也称为单调性）属性，则该属性成立。 如果对于每个节点
n和n的每个后继n'，从达到目标的估计成本，启发式函数是一致的>n不大于从n到达n'的步骤成本加上从n达到目标的估计成本>。如果启发式函数只是可接受的，即它永远不会高估达到目标的成本，则第二种方法是最佳的。
每个一致的启发式函数也是可接受的。 尽管一致性是比可采性更严格的要求，但人们必须非常努力地编造可采但不一致的启发式函数。
因此，尽管第二种方法更通用，因为它适用于启发式函数的更大子集，但第一种方法在实践中通常就足够了。
参考：《人工智能：一种现代方法》4.1 知情（启发式）搜索策略章节中的A*搜索：最小化总估计解决方案成本 /em>.
The first approach is optimal only if the optimal path to any repeated state is always the first to be followed. This property holds if the heuristic function has the property of consistency (also called monoticity). A heuristic function is consistent if, for every node
nand every successorn'ofn, the estimated cost of reaching the goal fromnis no greater than the step cost of getting ton'fromnplus the estimated cost of reaching the goal fromn.The second approach is optimal if the heuristic function is merely admissible, that is, it never overestimates the cost to reach the goal.
Every consistent heuristic function is also admissible. Although consistency is a stricter requirement than admissibility, one has to work quite hard to concoct heuristic functions that are admissible but not consistent.
Thus, even though the second approach is more general as it works with a strictly larger subset of heuristic functions, the first approach is usually sufficient in practice.
Reference: the subsection A* search: Minimizing the total estimated solution cost in section 4.1 Informed (Heuristic) Search Strategies of the book Artificial Intelligence: A Modern Approach.