正确制定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.

区别在于

• 一种方法（由< a href = http://en.wikipedia.org/wiki/A*_search_algorithm rel = noreferrer>维基百科和这篇文章）说：如果后继者在封闭列表中，只需忽略它即可。


• 另一种方法（建议此处和此处）说：如果后继者在封闭列表中，请检查其成本。如果它高于当前计算的分数，请从封闭列表中删除该项目以供将来检查。

• 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 ?

推荐答案

第一种方法只有在到达任何路径的最佳路径时才是最佳的重复状态始终是第一个要遵循的状态。如果启发式函数具有 consistency （也称为 monoticity ）的属性，则此属性成立。如果对于每个 n 节点和每个 n的后继 n'，启发式函数是一致的，从 n 达到目标的估计成本不大于达到 n'的成本。从 n 中的code>加上从 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知情（启发式）搜索策略。

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