迷路を探索するアルゴリズムには、「深さ優先探索」を用いるものと「幅優先探索」を用いるものがあります。

これらは元々、木構造やグラフ構造を探索するためのアルゴリズムで、今回はそれを迷路に応用しています。

 「深さ優先探索」とは、一つの道を突き進み、行き止まりになったら引き返す方法のことです。

人が巨大な迷路を探索するときに壁伝いに迷路を解く方法と似ています。

このアルゴリズムを実現する際に利用するのが、「スタック」というデータ構造。

これは「後入れ先出し」といって、データを出し入れする際に、後から入ったデータを先に出すという仕組みになっています。

例えば、お皿を食器棚にしまった後、食事の時にまたお皿を出すとします。この時、しまう時は下から上へ積み上げるようにお皿をしまい、出す時は上から下に向かってお皿を出しますよね。しまった時と逆順でお皿を出していくので、「後入れ先出し」というわけです。

現実世界ではこれ位しか例えがありませんが、プログラムの世界では深さ優先探索や再帰処理など、様々な処理で使われています。

このスタックを利用した深さ優先探索の主なアルゴリズムは、以下の通りです。

1. 現在位置を既に通ったマスに設定した後、現在位置から進めるマス（壁ではない and 既に通ったマスではない）を探す。
2. 進めるマスがあれば、現在位置をスタック（Excelファイルではセル[C15:D15]以下）に格納し、現在位置を進めるマスの位置に変更する。なお、進めるマスが見つかった時点で、進めるマスの候補の探索は終了する。
3. 進めるマスがなければ、スタックから進む前の位置を取り出し、現在位置を元の位置へ戻す（＝引き返す処理）。
4. ゴールするまで、1～3を繰り返す。

本来、一度通ったマスに進むと無限ループになってしまうので、進めるマスの候補には入れません。しかしこのままだと、引き返すことができず、行き止まりに出会った時点で終了してしまいます。そこで、行き止まりの時にだけスタックから元の位置を取り出すことにより、「引き返す」という処理を実現しているのです。

※なお、Excelファイルの方では、スタックへの出し入れを実際にしているわけではなく、スタックの先頭位置を切り替えることで再現しています。セル[C15:D15]以下に過去の位置が記録されているので、見てみてください。

深さ優先探索は、別の道を探索する必要がないため、迷路と探索の優先順位が噛み合えば、早く探索できます。

しかし、各迷路にどの優先順位が適しているかを見つけるのは困難なこと。行き止まりばかりで探索が遅くなることが多く、迷路と優先順位によって解く時間が大幅に変わってしまいます。

今回のExcelファイルでは「右→下→左→上」の優先順位で探索を行っていますが（Moveプロシージャ）、この順番を変えれば、当然探索する時間も変わってきます。編集したい人はしてみてください。

また、今回のようなゴールまでの道が1つしかない場合は、スタックを逆順で取り出すことで、最短経路を求めることができます。

しかし、ゴールまでの道が複数ある場合は、最初に通った道しか考えないので、常に最短経路を求められるとは限りません。

「幅優先探索」とは、道が分かれていた場合、全ての道を並行して探索する方法のことです。

このアルゴリズムを実現する際に利用するのは、「キュー」というデータ構造。 

これは、先ほどのスタックとは逆の「先入れ先出し」といい、データを出し入れする際に、先に入ったデータを先に出す仕組みです。

例えば、レジやATMで順番待ちをする時、先に並んだ人から順に処理をしてもらえますよね。いわゆる「待ち行列」というものと同じなので、先ほどのスタックよりは馴染み深い構造ではないでしょうか。

このきゅーを利用した幅優先探索の主なアルゴリズムは、以下の通りです。

1. 現在位置を既に通ったマスに設定した後、現在位置から進めるマス（壁ではない and 既に通ったマスではない）を探す。
2. 進めるマスがあれば、それら全てをキュー（Excelファイルではセル[C15:D15]以下）に格納する。
   さらに、進んだマスがどのマスから来たのか分かるように、現在位置の情報を記録しておく（最短経路の導出に利用。Excelファイルではセル[AC4:AP12], セル[AC16:AP24]）。
3. キューから進めるマスの位置を取り出し、現在位置とする。
4. ゴールするまで、1～3を繰り返す。

本来、プログラムもまったく同時に別の処理を行うことはできません。複数の処理の実行を短時間で切り替えることで、同時に処理を行っているように見せかけているのです。

今回の幅優先探索も、まったく同時に別の道を探索しているわけではありません。例えば、道Aと道Bに分かれた場合、道Aの探索→道Bの探索→道Aの探索→道Bの探索...といった具合に、各道を交互（3つ以上の場合は順番）に探索しているのです。この時に、各道の現在位置を取り出す必要があるので、キューを使っています。

なお、Excelファイルの方では、キューへの出し入れを実際にしているわけではなく、キューの先頭位置・最後尾位置を切り替えることで再現しています。セル[C15:D15]以下に位置が記録されているので、見てみてください。

幅優先探索は、複数の道を探索しながら進むため、どのような迷路でも安定した時間で解くことができます。

しかし、あらゆる道を探索してしまうためその分だけ時間がかかり、分かれ道が非常に多い迷路等では、深さ優先探索の方が早く解ける場合もあります。また、分かれ道が多いとその分メモリを消費しやすいという欠点もあります。

なお、各マスへどのマスから来たのかの情報を記録しておくと、それを逆順にたどることによって、最短経路を求めることができます。

 早く着いた道こそが最短経路なので、ゴールまでの道が複数ある場合でも可能です。

最後に、各迷路探索アルゴリズムの特徴をまとめておきます。

• 深さ優先探索
• • 長所：迷路と探索の優先順によっては、早く解ける。メモリの消費が少ない。
  • 短所：迷路と探索の優先順によっては、解く時間が大変大きくなる ＆ 解く時間の差が大きい。
    　　　常に最短経路を求められるわけではない。
• 幅優先探索
• • 長所：安定した時間で迷路を解ける。常に最短経路を求められる。
  • 短所：迷路によっては、解く時間が大きくなることもある。メモリの消費が多い。

つまり、常に幅優先探索が早いというわけではありませんが、幅優先探索の方が迷路を解くのには向いてます。

最短経路を常に求められるというのも強みですね。

ただ、人間が迷路を解く際には、深さ優先探索を使う機会が多そうです。人は同時にたくさんの処理はできないので（苦笑）

VBAのプログラム一覧に戻る