A* could fail even though using an admissible heuristic estimate

edit
 
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)Reply

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)Reply

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 103.21.125.78 (talk) 15:23, 16 August 2015 (UTC)Reply

Manhattan distance

edit

Should the Number six tile have a subscript of 1 not 2? — Preceding unsigned comment added by Rjones01 (talkcontribs) 10:34, 13 April 2011 (UTC)Reply

  Done Someone's fixed it.--92.27.34.75 (talk) 15:31, 15 July 2015 (UTC)Reply