[graph] A* search applied to knight's tour
Hi, 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. Any hints? -- Dave Abrahams BoostPro Computing Software Development Training http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost
On Tue, 27 Nov 2012, Dave Abrahams wrote:
Hi,
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. -- Jeremiah Willcock
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. -- Dave Abrahams BoostPro Computing Software Development Training http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost
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
on Tue Nov 27 2012, Jeremiah Willcock <jewillco-AT-osl.iu.edu> wrote:
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.
This is nifty, thanks. I haven't looked into the details, but it seems to me that it should also in principle be possible to use vertex coloring with no index map if you start with a map that has a default color for any nodes not yet looked up. Not sure that provides any advantage over relying on the distance map, though. -- Dave Abrahams BoostPro Computing Software Development Training http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost
participants (2)
-
Dave Abrahams -
Jeremiah Willcock