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