幅優先探索と Queue

講義資料

今回から、各種アルゴリズムについて、問題に取り組みはじめてもらいます。 今回のお題は、幅優先探索と Queue です。

幅優先探索

木構造などの探索に、深さ優先探索(depth first search)と幅優先探索(breadth first search)があるのは知っていますよね？

幅優先探索は、 起点ノードから近いノードを順番に探索をかけていく手法で、 波紋のように探索領域が広がっていきます。 擬似コードで書くと、こんな感じです。

/* 単純に queue を使う場合 */
enqueue(start);
while(/* queue に要素がある*/) {
    current = dequeue();
    for(/* current から参照される各ノードについて */) { 
        if(/*そのノードが未探索なら*/) {
	        enqueue(/*そのノード*/);
        }
    }
}

ゴールがあるなら、ゴールにたどりついた時点でおしまいです。

対象が木構造なら、たどり着いた場所は必ず未探索ノードなんですが、一般のグラフを探索する場合は、それまでに探索済みの場所かどうか、調べなくてはいけません。

  • ハッシュや多次元配列を使って、探索済みノードを覚えておく
  • 8パズル(or 15 パズル)のような問題の場合、すべての探索済みノードを覚えておくことはメモリ容量的に厳しいが、n(>2)手前以上に戻ることはありえないことを利用すれば、記憶する要素数を減らすことはできます。

さて、実際に課題２を解きながら理解を深めていきましょう。