深さ優先探索と幅優先探索の違い

深さ優先探索

深さ優先探索は、探索木の1本の枝を、行き止まりに着くまで奥へたどる方法です。解がなければ1つ前の分かれ道まで戻り（バックトラック）、まだ調べていない枝に進みます。迷路で、突き当たるまで進んでから引き返すやり方と同じです。

覚えておくのは、今たどっている道筋と、途中の分かれ道に残った枝だけです。1つのノードから出る枝の数をb、最も深いところまでの深さをmとすると、保持するノードはおよそb×m個で済みます。そのため、深い問題でもメモリが足りなくなりにくい方法です。一方で、先に選んだ枝の奥にある遠回りの解を先に見つけることがあり、無限に続く枝に入り込むと戻ってこられません。

幅優先探索

幅優先探索は、出発点のすぐ下にある深さ1のノードをすべて調べ、次に深さ2のノードをすべて調べる、というように1段ずつ広げる方法です。浅い順に調べるので、最初に見つかる解は、出発点からの手数が最も少ない解です。

その代わり、同じ深さのノードをまとめて覚えておく必要があります。最も浅い解の深さをdとすると、保持するノードはおよそbのd乗個に増えます。b=10、d=6なら約100万個です。

使い分けと発展

最短の手順が必要で、解が浅い位置にありそうなら幅優先探索が向いています。メモリが限られ、解が深い位置に多くあるなら深さ優先探索が向いています。両者の長所を合わせた方法に、深さの上限を少しずつ広げながら深さ優先探索をくり返す反復深化深さ優先探索があります。

どちらも、ゴールまでの近さの見込みを使わずに、決まった順番で機械的に調べる方法です。分岐が増えると、調べるノードの数は爆発的に増えます。第1次AIブームの探索は、迷路やパズルのようなトイ・プロブレムは解けても、選択肢が膨大な現実の問題を解くには至りませんでした。