Re: [boost] [graph] A* search applied to knight's tour

Subject: Re: [boost] [graph] A* search applied to knight's tour
From: Dave Abrahams (dave_at_[hidden])
Date: 2012-11-27 12:51:36

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