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

Subject: Re: [Boost-users] [BGL] Question/suggestion about example/astar-cities.cpp
From: Thomas Luzat (thomas_at_[hidden])
Date: 2011-03-30 11:43:17

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: [phone]   Web:       http://luzat.com
46483 Wesel      Fax:    [phone] E-Mail:    thomas_at_[hidden]