[Boost-users] [BGL] Question/suggestion about example/astar-cities.cpp

Subject: [Boost-users] [BGL] Question/suggestion about example/astar-cities.cpp
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-03-30 09:16:56

Hi,

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).
In the example code, an exception is thrown as soon as the examined vertex is 
equal to the goal-vertex.
Now I am wondering if this example is adequate because, as far as I have 
thought about it, this solution must not necessarily fullfill the 
characteristics of the A*-algorithm as it might lead to a premature abort 
(indeed actually intended) and thus could miss an optimal solution.

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.

This is not intended to be picky. I just sat on the example (or a custom 
modification to it) for quite some time now, wondering if my thoughts are 
correct.
If they are, I think a short comment/note might help to clarify the situation 
for future readers, perhaps getting unexpected results on their own.

Please correct me if I missed some point there. Thank you.

Best,

Cedric