Boost logo

Boost :

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


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.

Any hints?

Dave Abrahams
BoostPro Computing                  Software Development        Training             Clang/LLVM/EDG Compilers  C++  Boost

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