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

Subject: Re: [Boost-users] [BGL] Question/suggestion about example/astar-cities.cpp
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2011-03-30 16:27:51

On Mar 30, 2011, at 12:28 PM, Cedric Laczny wrote:
> 
> 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?

Not sure, but I think you might just use Dijkstra's shortest-path algorithm in that case.  Will be faster than looking at all paths and still minimal.