アルゴリズム 幅優先探索で迷路を解く
幅優先探索は、繋がりを持ったデータの集まり、例えば路線図や家系図のような構造の中で、ある地点から別の地点への道筋を見つけるための手順です。
迷路を解くことを想像してみてください。あなたはスタート地点に立っています。まず、スタート地点に隣接する全てのマスを調べます。行き止まりなら、そこへは進めません。道が続いていたら、そこへ一歩進みます。次に、一歩進んだ地点からまた隣接する全てのマスを調べます。これを繰り返していくと、まるで水面に石を投げた時に波紋が広がるように、探索範囲がスタート地点を中心にして広がっていきます。これが幅優先探索です。
木の根元から枝が伸び、さらにその枝からまた枝が伸びていく様子を思い浮かべてください。幅優先探索は、根元から近い枝を先に探索し、徐々に遠い枝へと探索を広げていくイメージです。つまり、スタート地点に近い場所を優先的に調べるということです。
この手順の利点は、最初に見つかった道筋が、スタート地点から目的地点までの最短経路となることが保証されていることです。遠回りせずに、最も効率の良い道筋を見つけられるのです。
例えば、友達の友達の友達を辿って、世界中の人と繋がっていると言われています。幅優先探索を使えば、あなたと特定の人との間の最短の繋がりを見つけることができるでしょう。何人経由すればその人に辿り着けるのか、最短ルートで知ることができるのです。