Correct formulation of the A* algorithm

Question

Hello,

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 ?

Answer 1

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.

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.