アルゴリズム 迷路を解くならコレ！幅優先探索で最短経路を探そう
子供の頃、誰もが一度は遊んだことがある迷路。簡単な迷路ならサッと解けるかもしれませんが、行き止まりや分かれ道が多い複雑な迷路になると、解くのはなかなか大変です。頭の中で道筋をシミュレーションして、それでも分からなければ、実際に鉛筆で道を辿ってみたりするのではないでしょうか。
では、コンピュータを使って迷路を解く場合、どのようにして正しい経路を見つけ出すのでしょうか？実は、人間が迷路を解く時のように、コンピュータも分かれ道に差し掛かるごとに「こっちかな？それともあっちかな？」と順番に選択肢を試していく方法があります。このような方法を『探索』と呼びます。
探索には様々な方法がありますが、その中でも代表的な方法の1つが、『幅優先探索』です。幅優先探索は、迷路のスタート地点から出発し、そこから行ける場所を全て調べていきます。そして、行ける場所からまた行ける場所を調べて…というように、まるで波紋が広がるように探索範囲を広げていく方法です。
幅優先探索は、必ずゴールまでの最短経路を見つけ出すことができるという利点があります。しかし、迷路が複雑になると、探索範囲が爆発的に広がり、処理に時間がかかってしまうという欠点もあります。そのため、状況に応じて他の探索方法と使い分けたり、工夫を加えたりする必要があるのです。
