深さ優先探索

最も深いノードから展開する探索の手順

コンピュータに問題を解かせる方法の1つに、初期状態から取れるアクションを順に試し、目標の状態にたどり着く道筋を探すやり方があります。このとき、初期状態を根にあたるルートノードに置き、そこから取れるアクションごとに次の状態を表す子ノードを作ると、枝分かれした木ができます。これを探索木と呼び、あるノードから子ノードを作る操作をノードの展開と呼びます。

探索の途中では、作られたもののまだ展開されていないノードがたまっていきます。この集まりをフリンジと呼びます。探索の手順は、フリンジからノードを1つ取り出し、目標の状態なら解として終わり、そうでなければ展開して子ノードをフリンジに加える、という操作のくり返しです。

深さ優先探索は、このくり返しの中で、フリンジにあるノードのうち最も深いノードを先に取り出して展開する手順です。展開すると、その子ノードがフリンジの中で最も深いノードになります。そのため次もその子ノードが取り出され、探索は1本の枝を下へ下へと進みます。子を持たないノードに行き着くと、そのノードは展開しても何も増えないので、フリンジの中で次に深いノード、つまり引き返した先にある別の枝のノードが取り出されます。

小さな木でたどる展開の順番

ルートノードAが子BとCを持ち、Bが子DとE、Cが子FとGを持つ、深さ2の木で考えます。深さ優先探索は、Aを展開したあとBを取り出し、Bを展開してDを取り出します。Dは子を持たないので、次にEを取り出します。Bの下を調べ終えたところでCへ戻り、F、Gの順に取り出します。ノードを取り出す順番は、A、B、D、E、C、F、Gです。

同じ木を幅優先探索で調べると、最も浅いノードから取り出すので、A、B、C、D、E、F、Gの順になります。2つの手順は同じ探索木を相手にしており、違うのはフリンジからどのノードを先に取り出すかだけです。

スタックで管理するフリンジ

最も深いノードを先に取り出すという規則は、フリンジをスタックとして扱うと実現できます。スタックは、最後に入れたデータを最初に取り出す仕組みのデータ構造で、この取り出し方を後入れ先出しと呼びます。展開して作った子ノードはスタックの上に積まれるので、次に取り出されるのはいま作ったばかりの子ノードです。

先ほどの木では、Aを展開するとBとCがスタックに積まれます。Bを取り出して展開するとDとEがその上に積まれ、Cはその下に残ります。DとEを取り出し終えて初めて、下に残っていたCが一番上に出てきます。スタックの一番上には常に最も新しく作られた、つまり最も深いノードがあるので、何も工夫しなくても深いノードから順に展開されます。幅優先探索が最初に入れたものを最初に取り出す構造を使うのと、この点が対になります。

計算量とメモリの小ささ

深さ優先探索の手間を見積もるには、1つのノードから分かれる枝の数である分岐数 b と、木の中で最も深い経路の深さ m を使います。時間計算量は O(b^m) です。O は、問題が大きくなったときに量がどの程度の速さで増えるかを表す記法です。最悪の場合、深さ優先探索は木のすべてのノードを調べるので、木全体の大きさに合わせて手間が増えます。

一方、空間計算量は O(bm) で、b と m の積に比例する程度に収まります。深さ優先探索が覚えておく必要があるのは、ルートからいま調べているノードまでの1本の経路と、その経路上の各ノードのまだ展開していない兄弟ノードだけです。ある枝の下を調べ終えたら、その枝のノードはメモリから手放せます。分岐数10、最も深い経路が深さ12の木なら、覚えておくノードは10と12の積の120個程度です。同じ深さ12まで幅優先探索で調べると、同じ深さのノードをすべて抱えるのでメモリの量は b の指数で増えていきます。深さ優先探索を選ぶ最大の理由は、このメモリの小ささにあります。

深く潜ることで起きる弱点

深いノードを先に調べるので、浅いところに解があっても、先に下りた枝の奥に別の解があればそちらが先に見つかります。先ほどの木でCとEが両方とも目標の状態だとすると、深さ優先探索はA、B、D、Eの順に取り出し、深さ2のEを解として返します。深さ1のCはまだ取り出されていません。幅優先探索なら浅い順に取り出すのでCが先に見つかります。深さ優先探索が最初に返す解は、最も浅い解とは限りません。

時間計算量の O(b^m) も、m が解の深さより大きい場合に不利になります。解が浅いところにあっても、先に下りた枝が深ければ、その枝の奥まで調べ尽くすまで引き返しません。木に終わりの無い経路があって m に上限が無い場合、深さ優先探索はその経路を下り続け、ほかの枝に解があっても戻ってこられません。

この弱点に対して、深さに上限を設け、上限の深さのノードは子を持たないものとして扱う手順があり、深さ制限探索と呼ばれます。深さ優先探索のメモリの小ささを保ったまま、終わりの無い経路を下り続けることを防ぐための変形です。