幅優先探索

浅いノードから順に展開していく探索

幅優先探索は、探索木をルートノードから広げていくときに、ルートに近い浅いノードを先に展開していく探索の手法です。英語では breadth-first search と呼びます。深さ0のルートノードを展開したら深さ1のノードをすべて展開し、それが終わったら深さ2のノードへ進みます。このように、調べる範囲を1段ずつ下へ広げていきます。

このページで使う用語を先に確認しておきます。探索木は、問題の初期状態をルートノードに置き、そこから取れるアクションごとに、次の状態を表す子ノードを枝分かれさせた木です。あるノードに取れるアクションをすべて当てて子ノードを作る操作は、ノードの展開と呼びます。ルートノードから何段下にあるかを深さと呼び、ルートノードの深さは0です。作られたもののまだ展開されていないノードの集まりはフリンジと呼びます。

探索木を使った探索は、フリンジからノードを1つ取り出し、それが目標の状態なら解として返し、そうでなければ展開して子ノードをフリンジに加える手順のくり返しです。この手順だけでは、フリンジのどのノードを先に取り出すかが決まっていません。幅優先探索は、その選び方を「いちばん浅いノードから取り出す」と決めた手法です。目標にどれだけ近そうかという見積もりのような、問題の定義以外の手がかりを使わずに順番を決めるので、深さ優先探索などとあわせて情報なし探索に分類されます。

フリンジを先入れ先出しの待ち行列にする仕組み

浅いノードから取り出す順番は、フリンジを先入れ先出しの待ち行列にすると実現できます。先入れ先出しの待ち行列はキューとも呼ばれ、先に入れたものから順に取り出す入れ物です。新しく作った子ノードは列の後ろに加え、次に展開するノードは列の先頭から取り出します。

この入れ方で浅い順になるのは、子ノードが必ず親ノードより1段深いからです。深さ1のノードを展開してできる深さ2の子ノードは、その時点で列に残っている深さ1のノードの後ろに並びます。そのため、深さ1のノードがすべて取り出されるまで、深さ2のノードの順番は回ってきません。

小さな木で順番を追ってみます。ルートノードAから子ノードBとCが分かれ、Bからは子ノードDとE、Cからは子ノードFとGが分かれる木を考えます。D、E、F、Gは子ノードを持たず、目標の状態はGにあるとします。

最初、フリンジにはAだけが入っています。Aを取り出して展開すると、フリンジはB、Cの順になります。先頭のBを取り出して展開すると、DとEが後ろに加わり、フリンジはC、D、Eになります。続いてCを取り出すとFとGが加わり、D、E、F、Gになります。D、E、Fは取り出して目標でないことを確かめるだけで、子ノードは増えません。最後にGを取り出したところで目標にたどり着きます。取り出した順はA、B、C、D、E、F、Gで、深さ0、深さ1、深さ2の順にきれいに並んでいます。

最初に見つかる解が最も浅い解になる理由

幅優先探索では、ある深さのノードがすべて取り出されてから、1段深いノードの取り出しが始まります。そのため、目標の状態が木の中の複数の深さに現れるとき、最初に取り出されるのは最も浅い位置にあるものです。ルートノードからの深さは、初期状態から目標までに取ったアクションの数と同じです。したがって、幅優先探索が最初に返す解は、アクションの数が最も少ない解になります。

先ほどの木がもっと深くまで続いていて、Dの下の深さ4にも目標の状態があったとします。この場合も、幅優先探索は深さ2のノードをすべて取り出し終えるまで深さ3以降へ進まないので、先に深さ2のGを解として返します。

ここで注意したいのは、アクションの数が最も少ないことと、かかるコストの合計が最も小さいことは別だという点です。どのアクションもコストが同じなら両者は一致します。しかしアクションごとにコストが違う問題では、1回あたりのコストが5のアクションを2回取る解は合計10になり、コストが1のアクションを3回取る解は合計3になります。幅優先探索はアクションの数が少ない前者を先に返してしまいます。コストの合計が最も小さい解を求めるなら、フリンジの中で経路コストが最も小さいノードを先に取り出す一様コスト探索のように、取り出す順番の決め方そのものを変える必要があります。

深さ優先探索と比べた順番とメモリの違い

深さ優先探索は、幅優先探索とは反対に、フリンジの中で最も深いノードを先に取り出す手法です。後から入れたものを先に取り出すスタックという入れ物をフリンジに使うと、この順番になります。先ほどの木で、左側の子ノードから先に調べるとすると、深さ優先探索の取り出す順はA、B、D、E、C、F、Gです。Bの下を調べ尽くしてから、Cの側へ移ります。

この順番の違いは、見つかる解に表れます。深さ優先探索は1本の枝を深くまで先に進むので、別の枝のもっと浅い位置に解があっても、深い位置の解を先に見つけることがあります。幅優先探索は浅い順に調べるので、この食い違いが起きません。

一方、必要なメモリは深さ優先探索のほうが小さく済みます。木の最大の深さを m、分岐数を b とすると、深さ優先探索が覚えておくのは、いま進んでいる1本の経路上のノードと、それぞれのノードのまだ調べていない兄弟ノードだけです。調べ終えた枝のノードは手放せるので、必要なメモリは O(bm) の程度に収まります。これに対して幅優先探索は、ある深さのノードをすべて展開し終えた時点で、1段深いノードをすべてフリンジに並べて持っていなければならず、空間計算量はノードの数と同じくO(b^(d+1))の程度まで増えます。どちらを使うかは、最も浅い解が欲しいのか、メモリを節約したいのかで決まります。

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

幅優先探索が作るノードの数は、1つのノードから分かれる枝の数である分岐数 b と、最も浅い解がある深さ d で見積もれます。深さ1には b 個、深さ2には b^2 個、深さ3には b^3 個と、1段下がるごとにノードは b 倍に増えます。

ノードを取り出した時点で目標かどうかを調べる手順では、深さ d の目標ノードを取り出す前に、同じ深さのほかのノードを展開してしまうことがあります。最悪の場合は、目標ノード以外の深さ d のノードをすべて展開し、深さ d+1 のノードまで作ります。このため、作られるノードの数は最大で b^(d+1) の程度になり、計算量は O(b^(d+1)) と書きます。O は、問題が大きくなったときに量がどのくらいの速さで増えるかを表す記法です。

分岐数2、解の深さ3の場合で数えてみます。深さ1に2個、深さ2に4個、深さ3に8個のノードができます。最悪の場合は、目標ノード以外の深さ3のノード7個も展開され、深さ4のノードが14個作られます。合計は2 + 4 + 8 + 14 = 28個です。

分岐数を10、解の深さを5に変えると、深さ1から深さ5までで10 + 100 + 1000 + 10000 + 100000 = 111110個、深さ6で最大999990個が作られ、合計は1111100個になります。深さ5のノードをすべて展開し終えた時点では、フリンジに深さ6のノードがおよそ100万個並んでいます。同じ木で最大の深さを6とすると、深さ優先探索が覚えておくノードは b × m = 60 の程度です。幅優先探索のメモリが先に足りなくなるのは、この差によります。

深さ優先探索のほうも、時間の面では有利とは限りません。最大の深さ m まで枝をたどりきることがあるので、作るノードの数は O(b^m) の程度になります。m が d より大きい木では、幅優先探索より多くのノードを調べることもあります。

向いている問題と限界

幅優先探索が向いているのは、どのアクションもコストが同じで、アクションの数が最も少ない解を求めたく、しかもその解が浅い位置にあると見込める問題です。浅い順に取りこぼしなく調べるので、条件を満たせば手数が最小の解を返せます。

限界は、分岐数が大きいか解が深いと、ノードの数とメモリが指数的に増えることです。目標に近そうなノードを優先するような手がかりを使わず、浅い順にノードを一つ残らず調べていくので、手がかりで候補を絞らずにすべて試すブルートフォース、つまり総当たりの探索と同じ性質を持ちます。アクションごとにコストが違う問題では、手数が最小の解がコスト最小の解とは限らない点にも注意が必要です。