A* 算法的正确公式化 [英] Correct formulation of the A* algorithm

问题描述

我在看 A* 寻路算法的定义，似乎在不同的地方定义有点不同.

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 ?

推荐答案

只有当到达任何重复状态的最优路径总是最先被遵循时，第一种方法才是最优的.如果启发式函数具有一致性(也称为单性)的属性，则此属性成立.如果对于 n 的每个节点 n 和每个后继 n'，从 达到目标的估计成本，启发式函数是一致的>n 不大于从 n 到 n' 的步骤成本加上从 n 达到目标的估计成本>.

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 n and every successor n' of n, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n' from n plus the estimated cost of reaching the goal from n.

如果启发式函数只是可接受的，则第二种方法是最优的，也就是说，它永远不会高估达到目标的成本.

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.

参考:人工智能:A 一书的 4.1 Informed (Heuristic) Search Strategies 小节 A* 搜索:最小化总估计解决方案成本现代方法.

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.

这篇关于A* 算法的正确公式化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！