CODEWITHSUNDEEP
c++boostboost-graph
Philipp
Philipp

Reputation: 11814

Best-First search in Boost Graph Library

I am starting to work with boost graph library. I need a best-first search, which I could implement using astar_search by having zero costs. (Please correct me if I'm wrong.)

However, I wonder if there is another possibility of doing this? If the costs are not considered, the algorithm should be slightly more efficient.

EDIT: Sorry for the unclear description. I am actually implementing a potential field search, so I don't have any costs/weights associated with the edges but rather need to do a steepest-descent-search (which can overcome local minima).

Thanks for any hints!

Upvotes: 0

Views: 3180

Answers (3)

anonymous
anonymous

Reputation: 11

If you are comfortable with C++, I would suggest trying out YAGSBPL.

Upvotes: 1

Jeremiah Willcock
Jeremiah Willcock

Reputation: 30969

As suggested by Aphex's answer, you might want to use Dijkstra's algorithm; one way to set the edge weights is to set w(u, v) to potential(v) - potential(u), assuming that is nonnegative. Dijkstra's algorithm assumes that edge weights are positive and so that distances increase as you move away from the source node. If you are searching for the smallest potential, flip the sides of the subtraction; if you have potentials that go both up and down you might need to use something like Bellman-Ford which is not best-first.

Upvotes: 0

Aphex
Aphex

Reputation: 7490

You could definitely use A* to tackle this; you'd need h(x) to be 0 though, not g(x). A* rates nodes based on F which is defined by 

F(n) = g(n) + h(n).

TotalCost = PathCost + Heuristic.

g(n) = Path cost, the distance from the initial to the current state

h(n) = Heuristic, the estimation of cost from current state to end state.

From Wikipedia:

Dijkstra's algorithm, as another example of a best-first search algorithm, can be viewed as a special case of A* where h(x) = 0 for all x.

Upvotes: 1

Related Questions