華榮道は役に立つ頭脳ゲームであり、そのルールは繰り返されることはありません。コンピュータで華榮道を解くのもよいプログラミングの練習になりますし、解答の手順には一般に、最小の手数を見つけるために幅優先探索アルゴリズムが用いられます。華栄道の一般的なオープニングを図1に示します。
フアラッシュを解くための幅優先探索アルゴリズムの基本ステップ：
- 2つの「グローバル変数」、キューQと集合Sを用意し、Sは「既知の状況」を表します。初期状態ではQもSも空。
- キューQの最後に初期状況を追加し、初期状況を既知とします。
- キューが空でない場合、Qの先頭から現在の状況currが取り出されます。キューが空の場合、探索は終了し、解がないことを示します。
- currが最終的な状況であれば検索を終了し、そうでなければステップ5に進みます。
- 移動可能なcurrの各駒を考え、上下左右に移動させて次の新しい位置を得ようとし、新しい位置が未知の場合はキューQに追加して既知とします。この移動によって複数の新しい位置が生成される可能性があります。
- ステップ2に戻ってください。
位置がわかっている」というのは、それぞれの駒が同じ位置にあることを要求しているのではなく、駒の投影が同じ形をしていることを要求しているのです。例えば、図1の張飛と趙雲を交換しても、新しい位置は生まれないので、探索空間が大幅に縮小されます。
上記のステップは簡単にC++コードに変換できますが、この記事ではステップ5の実装に焦点を当てます。
// 第 1 步
std::unordered_set<Mask> seen;
std::deque<State> queue;
// 第 2 步
State initial;
// 填入 initial，略。
queue.push_back(initial);
seen.insert(initial.toMask());
// 第 3 步
while (!queue.empty())
{
const State curr = queue.front();
queue.pop_front();
// 第 4 步
if (curr.isSolved())
break;
// 第 5 步
for (const State& next : curr.moves())
{
auto result = seen.insert(next.toMask());
if (result.second)
queue.push_back(next);
}
}
std::vector<State> 上記のオリジナルの実装では、curr.move()は一時オブジェクトを返します。 std::vector<State> オーバーヘッドを節約する1つの方法は、"scribble変数 "を用意し、curr.move()にそれを繰り返し変更させることです：
// 第 1 步新增一个 scratch 变量
std::vector<State> nextMoves;
// 第 3 步
while (!queue.empty())
{
// ...
// 第 5 步
curr.fillMoves(&nextMoves);
for (const State& next : nextMoves)
{ /* */ }
}
std::vector<State> ロジックの一部をラムダとしてcurr.move()に渡すことで、コードの構造を基本的に変更せずに、これを全く使用しない方法もあります：
// 第 3 步
while (!queue.empty())
{
// ...
// 第 5 步
curr.move([&seen, &queue](const State& next) {
auto result = seen.insert(next.toMask());
if (result.second)
queue.push_back(next);
});
}
こうすることで、メインプログラムのロジックが明確になり、不要なオーバーヘッドが最小限に抑えられます。
const std::function<void(const State&)> & std::function<void(const State&)> 私の初期の実装では、curr.move()は引数として持っていましたが、ここでオブジェクトを構築するたびに一度だけメモリを確保するのは少し意味がないように思えました。そのため、現在の実装ではcurr.move()は関数テンプレートとなっており、自動的にラムダ引数にマッチし、std::functionのメモリ確保が不要になっています。
この論文の完全なコードは あります。GCC 4.7でコンパイルする必要があり、図1の問題を解くのに数十ミリ秒かかります。
練習：駒の一手一手を印刷するようにプログラムを修正します。
