幅優先探索で迷路を解くとは？仕組み・最短経路・注意点をわかりやすく解説

幅優先探索で迷路を解くとは？仕組み・最短経路・注意点をわかりやすく解説

幅優先探索の基本：近い場所から順番に調べる

幅優先探索の考え方はとても素直です。スタート地点から1歩で行ける場所を先にすべて調べ、その次に2歩で行ける場所、さらに3歩で行ける場所へと進みます。探索範囲が同心円状に広がるため、迷路では水面の波紋が広がるような動きとして理解できます。

この「近い順」という性質が、幅優先探索の中心です。ある分岐を深く進み続けるのではなく、同じ距離にある候補をひとまとめに確認してから次の距離へ進みます。そのため、出口が近くにあるのに遠い道を先に延々と調べてしまう、ということが起こりにくくなります。

迷路をコンピュータで扱う場合、各マスを点、上下左右の移動を点同士のつながりとして考えます。このような点と線の集まりをグラフと呼びます。幅優先探索は、迷路だけでなくグラフ全般に使える基本的な探索方法です。

迷路での探索手順

迷路で幅優先探索を行うときは、次に調べるマスを順番待ちの列として管理します。この列は、先に入れたものを先に取り出すため、アルゴリズムではキューと呼ばれます。キューを使うことで、古い候補、つまりスタートに近い候補から順に処理できます。

基本手順は、まずスタート地点をキューに入れ、訪問済みにします。次にキューから1つのマスを取り出し、その上下左右にある移動可能なマスを調べます。壁ではなく、迷路の範囲内にあり、まだ訪問していないマスだけをキューへ追加します。この処理を、ゴールを見つけるか、キューが空になるまで続けます。

最短経路そのものを後から取り出したい場合は、各マスに「どのマスから来たか」という親情報を記録します。ゴールに到達したあと、ゴールから親をたどってスタートまで戻れば、実際の経路を復元できます。単にゴールの有無を知りたいだけなら親情報は不要ですが、迷路の答えとして道筋を表示したい場合には重要です。

最短経路が見つかる理由

幅優先探索で最短経路が見つかる理由は、スタートからの距離を1段ずつ増やしながら調べるためです。1歩で行ける場所をすべて調べる前に、2歩先の場所を調べることはありません。同じように、2歩で行ける場所を調べ終える前に、3歩先へ進むこともありません。

この順序で探索すると、ゴールを最初に発見した時点で、それより短い経路はすでにすべて確認済みです。もしもっと短い道が存在するなら、幅優先探索はその短い距離の段階で先にゴールを見つけているはずだからです。したがって、移動コストがすべて同じ迷路では、最初に見つけたゴールまでの経路が最短経路になります。

ただし、この保証には条件があります。上下左右の1マス移動がすべて同じコストであるような問題では幅優先探索が適しています。一方、道によって移動時間や料金が異なる重み付きの問題では、幅優先探索だけでは正しい最短コストを求められません。その場合は、ダイクストラ法など重みを扱える手法を検討します。

キューと訪問済み管理が重要になる

幅優先探索を正しく動かすには、キューだけでなく訪問済みの管理も欠かせません。訪問済みを記録しないと、同じマスを何度もキューに入れてしまいます。迷路に輪のような通路がある場合、同じ場所を繰り返し調べ続け、処理時間もメモリ使用量も無駄に増えていきます。

訪問済みとして扱うタイミングも大切です。多くの場合、マスをキューに追加した時点で訪問済みにします。取り出した時点で訪問済みにすると、同じマスが複数の経路から何度もキューへ入ることがあり、余計な候補が増えやすくなります。

また、迷路では「壁ではない」「範囲外ではない」「まだ訪問していない」という条件を毎回確認します。初心者が実装でつまずきやすいのは、範囲外チェックを忘れて配列の外を参照してしまうことや、訪問済みの更新が遅れて同じマスを重複処理してしまうことです。

記憶容量が増えやすい点に注意する

幅優先探索の大きな弱点は、探索中に多くの候補を保持する必要があることです。迷路が広く、分岐が多いほど、同じ距離にある候補マスが一気に増えます。キューにはこれから調べるマスが入り、訪問済みの記録にはすでに調べたマスが残るため、迷路の規模に応じてメモリ消費が大きくなります。

小さな迷路では問題になりにくいものの、巨大な迷路や状態数の多いパズルでは、候補が増えすぎて処理が重くなることがあります。幅優先探索は最短経路の保証が魅力ですが、その保証のために広い範囲を同時に覚えておく必要がある、と考えると理解しやすいでしょう。

実務や学習では、幅優先探索を使う前に、状態数がどの程度増えそうかを見積もることが大切です。メモリが厳しい場合は、問題設定を小さくする、探索深さに上限を設ける、別の探索方法を使う、といった判断が必要になります。

深さ優先探索との違い

幅優先探索とよく比較されるのが、深さ優先探索です。深さ優先探索は、ひとつの道をできるだけ奥まで進み、行き止まりになったら戻って別の道を試します。迷路でいえば、分岐を見つけてもまず一方向へ進み続ける方法です。

深さ優先探索は、幅優先探索に比べて保持する候補が少なく済むことがあります。一方で、最初に見つけたゴールが最短経路とは限りません。たまたま遠回りの道を先に進んでゴールに着くことがあるため、最短手数を求めたい場合は幅優先探索のほうが基本的には適しています。

どちらが常に優れているというものではありません。最短経路が必要なら幅優先探索、メモリを抑えながら可能性を深く試したいなら深さ優先探索、というように、目的に合わせて選ぶことが重要です。

幅優先探索が使われる場面

幅優先探索は、迷路以外にも多くの問題で使われます。たとえば、SNSであるユーザーから何人のつながりで別のユーザーに届くかを調べる問題、ゲーム盤面で最短手数を探す問題、ネットワークで近いノードを順に確認する問題などです。

パズルゲームの自動解法でも、幅優先探索は基本的な候補になります。すべての操作のコストが同じなら、操作回数が少ない解を見つけやすいからです。ただし、盤面の種類が爆発的に増える問題ではメモリ負担が大きくなるため、探索範囲を制限したり、別の手法と組み合わせたりすることがあります。

また、幅優先探索の考え方は、より高度な探索アルゴリズムを学ぶ土台にもなります。ダイクストラ法、A*探索、双方向探索などを理解するときにも、「候補をどう管理し、どの順番で取り出すか」という視点が役立ちます。

まとめ

幅優先探索は、迷路をスタート地点から近い順に調べることで、移動コストが同じ場合の最短経路を見つけられる探索方法です。キューを使って候補を順番に処理し、訪問済みを記録することで、同じ場所を何度も調べる無駄を防ぎます。

一方で、探索範囲が広がるほど記憶しておく候補や訪問済みの情報が増えるため、メモリ消費には注意が必要です。深さ優先探索との違いを押さえ、最短経路を重視するのか、メモリを抑えたいのかを考えると、幅優先探索を使うべき場面が判断しやすくなります。

更新履歴