幅優先探索

複雑に入り組んだ道と、たった一つの正解への道筋を持つ迷路。これを機械に解かせるにはどうすれば良いのでしょうか。人のように目で見て考えることができない機械のために、迷路をデータの形に変換する必要があります。迷路は、縦横に交差する道と壁でできています。この構造を、点と線で表現してみましょう。まず、道の交わる点を一つずつデータとして記録します。次に、どの点と点が線で繋がっているか、つまり道で繋がっているかを記録します。そして、迷路の始まりと終わりとなる二つの特別な点も記録します。これで、機械が理解できる形で迷路を表現できました。 機械は、記録された迷路のデータに基づいて、出発点から探索を始めます。まるで、一本の木が枝分かれしていくように、一つ一つの分岐点ですべての可能な道を探っていきます。これは、木の根っこが出発点、枝が道、そして葉が行き止まり、またはゴール地点となる木のような図で表すことができます。この図を探索木と呼びます。探索木を使うことで、機械が迷路をどのように探索しているのかを視覚的に捉えることができます。もし、行き止まりに辿り着いたら、一つ前の分岐点に戻り、まだ進んでいない別の道を探索します。これをゴールに辿り着くまで繰り返します。まるで、迷路の中で糸を手繰るように、機械は一つずつ道を辿り、最終的にゴールへの道筋を見つけ出すのです。このように、迷路の探索は、複雑な問題を一つずつ分解し、順序立てて解いていくという、機械の得意とする作業の一つなのです。