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

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

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: [phone]   Web:       http://luzat.com
> 46483 Wesel      Fax:    [phone] E-Mail:    thomas_at_[hidden]
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

Best,

Cedric