Boost logo

Boost Users :

Subject: Re: [Boost-users] [Graph] Difference between astar_search and astar_search_tree
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-04-29 13:32:54


On Mon, 29 Apr 2013, Luis Torres wrote:

> I didn't find the A* documentation very clear on this: when should one
> use astar_search, and when should one use astar_search_tree? Does the
> distinction have to do with whether the given heuristic is consistent?

The distinction is whether there should be an effort made to avoid
visiting the same vertex multiple times. For a graph where vertices can
often by reached using many paths, you should prefer astar_search to avoid
extra work from revisiting that vertex and its successors. If it is
unlikely that the same vertex will appear on multiple paths, or checking
vertices is inexpensive enough that it is not worthwhile to avoid repeated
work, use astar_search_tree which does not remember which vertices it has
visited previously. The disadvantage of trying to find repeated vertices
is that it requires a growing amount of memory to store the lookup table
of which vertices have been seen before, and it takes time to search and
update this table. Both versions of the algorithm require admissible
heuristics to work correctly.

-- Jeremiah Willcock


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net