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

Subject: [boost] [graph] A* search applied to knight's tour
From: Dave Abrahams (dave_at_[hidden])
Date: 2012-11-27 07:16:30

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