Boost logo

Boost :

Subject: Re: [boost] [graph] A* search applied to knight's tour
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-11-27 17:15:37

On Tue, 27 Nov 2012, Dave Abrahams wrote:

> on Tue Nov 27 2012, Jeremiah Willcock <> 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:
>>> 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

-- Jeremiah Willcock

Boost list run by bdawes at, gregod at, cpdaniel at, john at