コンピュータが問題を解くときの探索は、初期状態からゴールまでの道すじを見つける作業です。あり得る状態を枝分かれの形に書き出した「探索木」を作り、それをたどって探します。その木のたどり方に、幅優先探索と深さ優先探索という2つのやり方があります。違うのは、次にどの節点を調べるかという順番だけです。それだけで、次の2つがちょうど逆になります。
| 比べる点 | 幅優先探索 | 深さ優先探索 |
|---|---|---|
| 調べる順番 | 浅いところにある節点から順に | 深いところにある節点を先に |
| 手数が最も少ない経路 | 必ず得られる | 得られるとは限らない |
| 覚えておく量 | 深くなるほど急激に増える | いまたどっている道すじの分だけ |
幅優先探索と深さ優先探索は、第1次AIブームを支えた推論と探索のうち、探索にあたる手法です。ブームそのものの流れはAIブームと冬の時代で扱っています。
探索木とは：問題を木の形に書き出す
迷路を思い浮かべてください。分かれ道に来るたびに、右へ行くか左へ行くかを選びます。その選び方の積み重ねが、そのまま枝分かれの形になります。コンピュータも、問題を解くときに同じ形を作ります。
- 問題を解いている途中の状態を1つずつ、点として書く。これを節点と呼ぶ。出発点になる最初の状態を表す節点が、木の根にあたる
- その状態でできる操作をすべて当てはめる。1つの操作から次の状態が1つ決まるので、それを新しい節点として書いて、もとの節点と枝でつなぐ。この動きを展開と呼ぶ
- 展開してできた節点を、また展開する
これを繰り返すと、根を上にして、枝分かれが下へ下へと伸びていきます。こうしてできる木が探索木です。解く前に図として全部できあがっているのではなく、探しながら伸ばしていくものです。
ゴールの状態を表す節点が現れたら、そこで終わりです。その節点から枝をさかのぼって根まで戻り、通った操作を根のほうから並べ直すと、初期状態からゴールまでの手順になります。これが求めていた答えです。
木の作り方はこれで決まりました。ただ、実際に探すときには、もう1つ決めることが残っています。まだ展開していない節点がいくつもあるとき、次にどれを展開するか、です。
幅優先探索：浅いところから順に調べる
幅優先探索は、まだ展開していない節点のうち、最も浅いところにあるものから順に展開します。根のすぐ下にある節点を全部展開してから、その1つ下の段へ移る。段を1つずつ、横に埋めていくやり方です。
浅いほうから順に調べるので、最初に見つかるゴールは、必ず一番浅いゴールになります。だから、手数が最も少ない経路が得られます。
最短が得られるってことは、幅優先探索のほうが答えも早く出るの？
いいえ。最も少ないのは、見つかった経路の手数です。探索にかかる時間の話ではありません。
むしろ、幅優先探索は手間のかかるやり方です。段をひととおりそろえてから次へ進むので、展開した節点をすべて覚えておかなければなりません。枝が分かれるたびに節点は増えますから、1段深くなるごとに、覚えておく節点の数は何倍にもふくれ上がります。ゴールが深いところにある問題では、この量が現実的でなくなり、解けなくなります。
深さ優先探索：行き止まりまで進んで、戻る
深さ優先探索はその逆で、まだ展開していない節点のうち、最も深いところにあるものを先に展開します。1本の枝を選んだら、行けるところまでそのまま下りていく。行き止まりに突き当たってゴールが無ければ、直前の分かれ道まで戻って、まだ試していない別の枝へ進みます。
このやり方なら、覚えておくのは、いまたどっている一本の道すじだけで済みます。段全体を抱えたまま進まずに済むので、覚えておく量はずっと少なくなります。
その代わりに、手放すものがあります。最初に見つかったゴールが、一番浅いところにあるとは限りません。深く潜っていった先で、たまたま出会ったゴールかもしれない。ですから、得られた経路が最も少ない手数だとは限りません。
どちらを使うかは問題による
2つを並べてみます。探索木の作り方も、ゴールかどうかの調べ方も同じです。違うのは、次にどの節点を展開するかという選び方だけです。ところが、その一点の違いから、得られるものと払うものがちょうど入れ替わります。
幅優先探索は、浅い順にすべてそろえて進むので、手数が最も少ない経路が得られます。ただし、その段の節点を抱えたまま進まなければなりません。深さ優先探索は、一本の道すじだけを抱えて進むので、覚えておく量は少なくて済みます。その代わり、先に見つかった経路が最も少ない手数とは限りません。
ポイント
どちらが優れているという話ではありません。選び方の目安は、まず手数が最も少ない経路が必要かどうかです。必要なら幅優先探索、そうでなく覚えておく量を抑えたいなら深さ優先探索が候補になります。どちらが早く答えを見つけるかは、問題の形とゴールの位置しだいです。
ブルートフォース：手がかりを使わずに全部調べる
この2つは、順番こそ違いますが、やっていることは共通しています。どちらも、問題についての手がかりを何も使っていません。ゴールがどちらの方向にありそうか、という見当をつけないまま、あり得る候補を端から全部調べています。
こういうやり方を、ブルートフォース（力任せの探索）と呼びます。幅優先探索も深さ優先探索も、調べる順番が違うだけで、どちらもブルートフォースにあたります。
手がかりを使わないぶん、その問題についての知識も要りません。だからどんな問題にも、同じやり方をそのまま持ち込めます。これが強みです。
代償もあります。手がかりが無い以上、調べる先を減らせません。枝分かれが多く、ゴールが深いところにある問題では、調べなければならない節点が急激に増えて、現実的な時間では終わらなくなります。手がかりを使って調べる先を絞り込む方法もありますが、ここで扱った2つはそこまではしません。
探索で解ける問題の例：ハノイの塔
3本の柱と、大きさの違う円盤を使うパズルです。円盤は一度に1枚しか動かせず、小さい円盤の上に大きい円盤を置くこともできません。この規則のもとで、積み上がった円盤を全部、別の柱へ移します。
この問題は、探索の話にそのまま当てはまります。「どの柱に、どの円盤が積まれているか」が状態で、「円盤を1枚動かす」が操作です。ですから、いまの積み方を1つの節点にして、そこでできる動かし方の数だけ枝を分ければ、探索木が作れます。ゴールは、全部の円盤が目的の柱へ移った状態の節点です。
規則がはっきりしていて、小さく作られた問題を、トイ・プロブレムと呼びます。ハノイの塔はその代表例で、探索の例としてよく名前が挙がります。
まとめ
探索は、いまの状態を節点、操作を枝にした探索木を作り、それをたどってゴールまでの道すじを見つけます。たどり方には、浅い段から順に調べる幅優先探索と、深いほうへ先に進む深さ優先探索があり、違うのは次にどの節点を展開するかという順番だけです。
その順番だけで、手数が最も少ない経路が必ず得られるかどうかと、覚えておく量が入れ替わります。どちらも手がかりを使わずに全部調べるブルートフォースで、問題を選ばない代わりに、大きな問題では時間が足りなくなります。
次は、相手のいるゲームで先を読む方法、ミニマックス法とαβ法・モンテカルロ法を取り上げます。