On Wednesday, 30. March 2011 17:43:17 Thomas Luzat wrote:
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.
Yes, thank you for this nice explanation. More formally, this seems to come down for the heuristic to be at least admissible, or even stronger, to be monotonic or consistent. I found that out only later on. Given the case of an overestimating heuristic, if the program aborts upon examination of the goal, it might miss the optimal path due to the overestimation. However, when it runs as long as the queue Q is not empty, I think it should find the optimal path nevertheless, although possibly reopening the closed goal-vertex. What do you think about that?
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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Best, Cedric