Boost logo

Boost :

Subject: Re: [boost] [graph] A* search applied to knight's tour
From: Dave Abrahams (dave_at_[hidden])
Date: 2012-12-15 17:12:01


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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk