Re: [boost] BGL experience report and question

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-01-14 13:56:53

On Thu, 10 Jan 2002, David Abrahams wrote:
david.>
david.> Actually, it's not an A* search that I need. From reviewing my search
david.> algorithms, it looks like I want something more like best-first search. I
david.> don't think dijkstra's algorithm can be made to do that, can it?

So for a best-first search (p. 93 of Artificial Intelligence: A Modern
Approach by Russell and Norvig) the user provides a heuristic function
that estimates the shortest path for a vertex, and then the algorithm
orders the queue based on the function. I suppose it would be possible to
use the BGL BFS with a custom-made queue to implement this.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------