農夫と山羊と狼とキャベツの問題
http://www.geocities.jp/m_hiroi/puzzle/farmer.html
の場合、
深さ優先
- 移動できるキャラがあれば移動してみる方式
- 過去の各フェーズの状態を全て覚えておく。過去と同じ状態になる場合、移動しないためと、結果表示のため
- 農夫の位置（右岸か左岸か）を覚えるのではなく、フェーズのたびに移動方向を右、左、右、左、と固定的に切り替えている（よって、このコードでは農夫が複数いるような問題には使えない）
search(){
foreach 全てのキャラについて
{
if(対岸に移動できるか？過去の状態に一致しないか？)
{
移動後状態を覚える。
完了（全部対岸に移動）なら、完了。
search();
}
}
}
幅優先
- 遷移可能な状態が見つかった場合、すぐに遷移してみるのではなく、キューに放りこんでおく方式
- メインロジックは、キューから一つ取り出し、次に遷移可能な状態（０〜複数）をキューに登録する、の繰り返し
- スタックを使わないで済む
- 状態（農夫、狼、羊、キャベツ、農夫の右左）を５ビットで表現
- 二つの可変長の配列を使用する。
- 一つは状態を記録する配列
- その状態で対岸に移動できるものがあれば、移動後の状態をリストに追加（移動可能なオブジェクトの数だけ配列が増える可能性がある）
- もう一つは各状態がどの状態から派生したかを覚えるprev配列（これは結果表示のために使われる）
search(){
state配列のindex 0に全員左岸状態をセット；
prev配列のindex 0に直前状態無しを意味する−１をセット；
foreach state配列をindex0から順番に・・・
{
foreach 全てのキャラについて
{
if(対岸に移動できるか？過去の状態に一致しないか？)
{
state配列を一つ増やし、移動後の状態を追加;
prev配列を一つ増やし、現在のindexをセット;
移動後が完了なら、終わり。
}
}
}
}ミソは、配列をなめながら、配列の末尾にどんどん次に遷移可能な状態を追加していくところ。これにより、ツリーの探索と次の段のノードの管理を一緒に行っている。
