Boost Graph Library A* for consistent heuristic

Question

I've read that, when applying A* to a problem, if your heuristic is consistent then you can further optimize the A* search. The Boost Graph Library offers two versions of the A* algorithm: astar_search and astar_search_tree. The documentation isn't very clear on the distinction between the two; does one of these perform the optimized search which assumes a consistent heuristic?

Answer 1

I got the answer I was looking for by consulting the Boost mailing list. I'll reproduce the answer here for posterity:

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.

Link to the thread

Answer 2

The difference between the _tree and the non _tree boost graph algorithm versions is that the _tree version assumes your graph is really a tree, so it has no cycles and only has one in arrow for node.