Search code examples
artificial-intelligencea-star

A* Graph search


http://i.imgur.com/ktdwhrT.png

Given the heuristic values h(A)=5, h(B)=1, using A* graph search, it will put A and B on the frontier with f(A)=2+5=7, f(B)=4+1=5, then select B for expansion, then put G on frontier with f(G)=4+4=8, then it will select A for expansion, but will not do anything since both S and B are already expanded and not on frontier, and therefore it will select G next and return a non-optimal solution.

Is my argument correct?


Solution

  • You maintain an ordered priority queue of objects on the frontier. You then take the best candidate, expand in all available directions, and put the new nodes in the priority queue. So it's possible for A to be pushed to the back of queue even though in fact the optimal path goes through it. It's also possible for A to be hemmed in by neighbours which were reached through sub-optimal paths, in which case most algorithms won't try to expand it as you say.

    A star is only an a way of finding a reasonable path, it doesn't find the globally optimal path.