幅優先探索

子供の頃、誰もが一度は遊んだことがある迷路。紙の上で鉛筆を走らせ、行き止まりにぶつかっては、分かれ道まで戻って別の道を試した経験をお持ちの方も多いのではないでしょうか。実は、コンピュータに迷路を解かせる際にも、私達人間と同じように、あらゆる道を試していくという方法が取られます。しかし、コンピュータは迷路をそのまま理解できるわけではありません。そこで登場するのが「探索木」という考え方です。迷路を、選択肢が枝分かれしていく「木」のような構造で表現するのです。迷路のスタート地点を木の根元と見立てます。そして、道が分岐するたびに、それぞれの道が枝分かれしていくように、木を成長させていきます。行き止まりは、木の枝の先端、つまり行き止まりとして表現されます。このようにして、複雑に入り組んだ迷路を、コンピュータが理解しやすい形に変換します。コンピュータはこの探索木を使って、スタート地点からゴール地点まで、全ての分かれ道を順番に辿っていきます。まるで、先を見通せるかのように、あらゆる可能性を検討していくのです。そして、ゴールにたどり着く道が見つかったとき、コンピュータは迷路を解いたことになるのです。このように、迷路と探索木は、一見すると異なるものに見えますが、実は密接に関係しており、コンピュータが迷路を解くための重要な鍵を握っています。