Hello! I have not yet used BGL, but think there is a requirement on the heuristic missing in the documentation. See below: On 2011-03-30 15:16, Cedric Laczny wrote:
I had a look at the A*-search documentation and example code provided by boost (http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/astar_search.html). [...] Simple scenario: A graph with 3 vertices: one start, one goal, one intermediate and 3 edges: (start, goal), (start, intermediate), (intermediate, goal). If the weights are "similar enough" and the heuristic might be beneficial for the direct edge (start, goal), the program will throw the error when it examines the goal vertex, while actually it might have been optimal to take the route over the intermediate-vertex.
So, in your example: w(start, goal) < w(start, intermediate) + w(intermediate, goal) At the start of the second iteration of the while loop in the pseudo-code we have: Q = { intermediate, goal } f(intermediate) = w(start, intermediate) + h(intermediate) f(goal) = w(start, goal) + h(goal) = w(start, goal) Now, for goal to be examined prematurely we would need to choose u = goal at the line u := EXTRACT-MIN(Q) in the pseudo-code. But, given that f(intermediate) <= f(goal), we will choose u = intermediate. I think the documentation is indeed lacking there: The "<=" is only guaranteed if the heuristic does not overestimate the distance to the goal, which is a requirement of A* to (reliably) work. I could not find that mentioned within the documentation. Hope that clears it up. Cheers Thomas Luzat -- Thomas Luzat Softwareentwicklung USt-IdNr.: DE255529066 Kaiserring 2a Mobile: +49 173 2575816 Web: http://luzat.com 46483 Wesel Fax: +49 173 502575816 E-Mail: thomas@luzat.com