経路をすべて求めることができます。ゴールに到達していない場合は経路をのばして探索を進めます。含まれていないかチェックすることを忘れないで下さい。地点にたどり着くことができなくなります。実行すると、次のような経路を表示します。通りの経路を見つけることができました。バックトラックによる探索は経路を先へ先へ進めるので、「縦形探索」とか「深さ優先探索」と呼ばれています。このため、結果を見てもわかるように、最初に見つかる経路が最短経路とは限りません。優先探索は一つの経路を先へ先へと進めていくため、最初に見つかる経路が最短経路であるとは限りません。幅優先探索はすべての経路について平行に探索を進めていくため、最初に見つかる経路が最短経路となります。それでは、同じ経路図を使って幅優先探索を具体的に説明しましょう。幅優先探索の様子を下図に示します。あり、これをすべて記憶しておきます。進めることができますね。同様に進めて、すべての経路を記憶します。あとはこの作業をゴールに達するまで繰り返せばいいのです。ゴールに達していることがわかります。この性質は、すべての経路を平行に進めていく探索順序から考えれば当然のことといえるでしょう。このことからバックトラックの縦形探索に対して、幅優先探索は「横形探索」と呼ばれます。このあとも探索を繰り返せばすべての経路を求めることができます。完成までの最小手数を求めるパズルを解く場合、幅優先探索を使ってみるといいでしょう。探索を進めるにしたがって、記憶しておかなければならないデータの総数が爆発的に増加する、つまりメモリを大量消費することに注意してください。上図の場合ではメモリを大量消費することはありませんが、問題によってはマシンに搭載されているメモリが不足するため、幅優先探索を実行できない場合もあるでしょう。したがって、幅優先探索を使う場合は、メモリの消費量を抑える工夫も必要になります。経路の管理はキューを使うと簡単です。幅優先探索でのキューの動作を下図に示します。ように出発点をキューにセットしておきます。作り、それをキューに追加します。あとはキューに経路がある間、処理を繰り返せばいいわけです。性質を持つデータ構造です。距離の短い経路から順番に処理されるため、幅優先探索として機能するわけです。●プログラムの作成それではプログラムを作りましょう。次のリストを見てください。経路を幅優先探索で求めます。経路をキューに追加します。