Jump to content

Talk:Admissible heuristic

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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]