This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
This article has been rated as Low-importance on the project's importance scale.
A* could fail even though using an admissible heuristic estimate
This is an example of a graph that A* will fail to find the shortest path for, if the heuristics looks like that in the image (admissible though not consistent) and a closed set of nodes is used.
Just because using an admissible heuristic estimate in the A* algorithm, it doesn't mean that it will find an optimal path. To the right is a counterexample. --Kri (talk) 02:09, 7 November 2009 (UTC)
Oh, just realized that a closed set cannot be used if the heuristic is not consistent. My image supposes that a closed set is used, and that the heuristic looks like it does (not consistent), which is not allowed. --Kri (talk) 11:12, 21 November 2009 (UTC)
The A* search algorithm doesn't stop when generating the goal state but when expanding it. So, in your case the heuristic is admissible and also it finds the shortest path because even after generating the goal state from the node C it pushes it onto the Priority queue and then expands B because it has the lowest estimate(0+2) then the goal(3+0). — Preceding unsigned comment added by 188.8.131.52 (talk) 15:23, 16 August 2015 (UTC)