Correct formulation of the A* algorithm

Question

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 connection is that you don't need to replace states in the closed list if the first path to a state is the cheapest. The consistency property guarantees this condition holds.Note that if your items in the closed list are just the nodes as is usually the case, then you can return to the closed list even if you don't have loops: e.g. if a node can be reached by more than one path

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 monotonicity). 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.

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence Tutorial.  Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.