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

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

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