コンピュータの頭の中

コンピュータがこのような迷路を解く時、どのように解いているのだろうか？

実際の処理では、上図のような形式に変換する。

上図の迷路の枠を取り去ってあげて、Sを起点にぶら下げてみると、以下のようになる。

このように、木のような構造(ツリー構造)になる。これを探索木と呼ぶ。探索木とは、場合分けである。場合分けを続けていけば、いつか目的の条件に合致するものが出現するという考え方を基礎にしている。

基本的な検索をする手法として、幅優先探索と深さ優先探索がある。

幅優先探索

幅優先探索では、あるノードからつながっている隣のノード全て探索し、続いてさらにつながっている隣のノードを探索するという流れを繰り返す。

特徴として、最短距離でゴールにたどり着く解を見つけることができる。しかし、探索の途中で立ち寄ったノードを全て記憶する必要があるため、複雑なツリー構造になるとメモリ不足になる可能性がある。

深さ優先探索

深さ優先探索では、あるノードから行き止まりのノードまでいったん探索を行い、行き止まりにたどり着いたら一つ手前のノードに戻って次の行き止まりまで探索を行うことを繰り返す。

深さ優先探索では、解が見つからない場合は一つ手前のノードに戻る。そのため、メモリはあまり必要ではない。しかし、解を発見してもそれが最短距離だとは限らない。

まとめ

コンピュータが迷路の問題を解く時、コンピュータで処理できる形式に変換する。基本的な検索をする手法として、幅優先探索と深さ優先探索がある。