幅優先探索とは

幅優先探索は、問題を解く手順の候補を木の形（探索木）に広げ、出発点から近い順に調べていく探索方法です。探索木では、1つの状態を表す点をノード（節点）と呼びます。出発点から何本の枝をたどったかを、そのノードの深さと呼びます。

進み方

まず、出発点のすぐ下にある深さ1のノードをすべて調べます。次に深さ2のノードをすべて調べ、その次に深さ3へ進みます。木を上から1段ずつ、横に塗りつぶしていくイメージです。実際の処理では、これから調べるノードを待ち行列（キュー）に並べ、先に並べたものから順に取り出します。

長所と短所

浅いノードから順に調べるため、最初に見つかった解は、出発点からの手数が最も少ない解です。また、1つのノードから出る枝の数が有限であれば、解がある限りいずれ見つかります。

一方で、メモリを多く使います。1つのノードから平均b本の枝が出るとすると、深さdには約b^d個のノードが並びます。たとえばb=10なら、深さ5だけで約10万個です。幅優先探索は、同じ深さのノードをまとめて覚えておく必要があるため、深い問題ではメモリが足りなくなりがちです。

位置づけ

幅優先探索と深さ優先探索は、ゴールまでの近さの見込みを使わず、決まった順番で機械的に調べる探索です。第1次AIブームでは、迷路やハノイの塔のようなパズルをこうした探索で解く研究が進みました。しかし、現実の問題は組合せの数が膨大で、この方法だけでは解けません。この限界は、AIはトイ・プロブレム（おもちゃの問題）しか解けないという批判につながりました。

覚え方

「幅＝1段ずつ横に広げる。だから最短の手数で見つかるが、メモリを食う」と覚えます。