探索木

初期状態から枝分かれしていく探索の木

コンピュータに問題を解かせるとき、問題は「どこから始まるか」と「ある状態から次にどの状態へ移れるか」の2つで表せます。前者を初期状態、後者を返す仕組みを後継関数と呼びます。後継関数は、ある状態を受け取り、そこで取れるアクションと、そのアクションを取った結果の状態の組を返します。初期状態と後継関数によって、たどり着ける状態の全体である状態空間が決まります。

探索木は、この状態空間を木の形に書き出したものです。根にあたるルートノードには初期状態を置きます。ルートノードに後継関数を当てると、取れるアクションの数だけ子ノードができます。この操作をノードの展開と呼びます。子ノードをさらに展開すると孫ノードができ、木は下へ下へと広がっていきます。

問題を解くとは、この木を展開しながら、目標の状態を含むノードを見つけることです。見つかったノードからルートまでたどった経路が、初期状態から目標までのアクションの並び、つまり解になります。

1つのノードが持つ5つの情報

探索木のノードは、状態そのものではなく、状態を記録するための入れ物です。1つのノードは次の5つの情報を持ちます。

1つ目は状態で、そのノードが表す世界の様子です。2つ目は親ノードで、このノードを生み出した1つ上のノードを指します。3つ目はアクションで、親ノードからこのノードへ移るときに取った行動です。4つ目は経路コストで、ルートからこのノードまでの経路にかかったコストの合計です。5つ目は深さで、ルートから数えて何段下にあるかを表します。ルートノードの深さは0です。

親ノードの情報があるので、目標のノードが見つかったら親をたどってルートまで戻り、解の経路を取り出せます。また、ノードと状態は別のものなので、違う経路で同じ状態にたどり着けば、同じ状態を持つノードが木の中に2つ以上できることがあります。

展開を待つノードの集まりとTREE-SEARCH

探索の途中には、作られたもののまだ展開されていないノードがたまっていきます。この集まりをフリンジと呼びます。探索木の探索は、TREE-SEARCHと呼ばれる次の一般形で書けます。

最初に、初期状態を持つルートノードをフリンジに入れます。次に、フリンジが空なら解は無いとして終わります。空でなければフリンジからノードを1つ取り出し、その状態が目標なら解として返します。目標でなければそのノードを展開し、できた子ノードをフリンジに加えます。この手順を解が見つかるかフリンジが空になるまで繰り返します。

この一般形の中で決まっていないのは、フリンジからどのノードを先に取り出すかだけです。最も浅いノードを先に取り出せば幅優先探索になり、最も深いノードを先に取り出せば深さ優先探索になります。経路コストが最も小さいノードを先に取り出す一様コスト探索、深さ優先探索に深さの上限を設ける深さ制限探索もあります。これらは状態について問題の定義以外の手がかりを使わないので、情報なし探索とまとめて呼ばれます。どの手法も同じ探索木を相手にしており、違うのは木を広げる順番です。

分岐数と深さで決まるノード数の式

探索木の大きさは、1つのノードから分かれる枝の数である分岐数 $b$ と、最も浅い解がある深さ $d$ でおおよそ決まります。

幅優先探索では、深さ1にノードが $b$ 個、深さ2に $b^2$ 個、深さ3に $b^3$ 個と、1段下がるごとにノードが $b$ 倍に増えます。TREE-SEARCHは、ノードを取り出した時点で目標かどうかを調べます。そのため、深さ $d$ の目標ノードを取り出すまでに、深さ $d$ のほかのノードもすべて展開してしまい、その子として深さ $d+1$ のノードまで作ります。最悪の場合に作られるノードの数は、次の式で表されます。

$b+b^2+b^3+...+b^d+(b^{d+1}-b)$

この合計は、最も大きな項である $b^{d+1}$ の程度に収まるので、計算量は $O(b^{d+1})$ と書きます。$O$ は、入力が大きくなったときに量がどの程度の速さで増えるかを表す記法です。

式の読み方で大切なのは、$d$ が指数の位置にあることです。深さが1増えるとノード数はおよそ $b$ 倍になり、分岐数が大きいほど増え方も急になります。

分岐数10の木で見るノード数と時間の計算例

分岐数 $b=10$ の探索木で、深さ $d=2$ に解がある場合を計算します。深さ1に10個、深さ2に100個、深さ3には $10^3-10=990$ 個のノードが作られるので、合計は $10+100+990=1100$ 個です。スチュアート・ラッセル(Stuart J. Russell)とピーター・ノーヴィグ(Peter Norvig)の教科書『Artificial Intelligence: A Modern Approach』第2版の第3章には、幅優先探索に必要な時間とメモリの見積もりの表があり、深さ2では1100ノード・0.11秒・1メガバイトとされています。1100ノードを0.11秒で作るので、この表は1秒あたり1万ノードを作れる計算機を想定した見積もりです。

同じ表で深さ12を見ると、ノード数はおよそ $10^{13}$ 個、時間は35年、メモリは10ペタバイトです。深さを2から12へ10段深くしただけで、ノード数は1100個からおよそ $10^{13}$ 個へと、約90億倍になります。メモリも1メガバイトから10ペタバイトへ、ほぼ同じ割合で増えています。

この数値から読み取れるのは、1秒あたりに作れるノードを多少増やしても、深さが数段増えれば追いつかなくなるということです。幅優先探索は作ったノードをメモリに残しておくので、表のメモリの量もノード数と同じ割合で増えていきます。深さ優先探索は調べ終えた枝のノードを手放せるので必要なメモリは小さくなりますが、展開の順番を変えても木そのものの大きさは変わりません。手がかりを使わずに木を端から調べるやり方がごく小さな問題にしか使えないことは、この式と表から読み取れます。