On Tue, 27 Nov 2012, Dave Abrahams wrote:
on Tue Nov 27 2012, Jeremiah Willcock <jewillco-AT-osl.iu.edu> wrote:
I was just trying to work up an example for a class I'm teaching, to illustrate implicit graphs. The following shows how far I've gotten:
https://gist.github.com/4153918
This is attempting to apply Warnsdorff's heuristic (choose the next move with the least out-degree) using A* search. I'm running into several problems having to do with the requirements of astar_search_no_init. In particular, the requirement that we can assign an index to every vertex is quite painful, since enumerating all the possible vertices in the search space is difficult. Any advice here? I suppose I could keep a real map and simply assign indices in the order vertices are encountered, but that seems pretty ugly to me.
I think that's the best you can do with the current code. Longer-term, it would be better to make IndexInHeapMap a parameter so that you can replace it with an associative property map. Even now, you might want to use associative_property_maps for distance_map, rank_map, and color_map to avoid going through the index table for those.
I just realized that recording the available board positions in the search state may not be appropriate for this particular application, since the A* search will be remembering which vertices have been visited. So that makes the whole problem considerably easier. Still, in general, these kinds of requirements are onerous for work with most implicit graphs.
I added _tree versions of the various A* variants into the Boost trunk; they should work a lot better with implicit graphs since they do not require a vertex index map, and a lot of the other property maps become optional. -- Jeremiah Willcock