Re: [Boost-users] [Graph] Difference between astar_search and astar_search_tree

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