幅優先探索と Queue

幅優先探索と Queue の利用

講義資料

• 講義資料

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

幅優先探索

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

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

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

あるいは、起点からの距離に応じてデータ構造を準備する場合は、こんな感じ。

/* 手数ごとにデータ構造を準備 */
push(nextStage, start);
while(/* nextStage に要素がある*/) {
    currentStage=nextStage;
    reset(nextStage);
    for(node in currentStage) {
        for(/* node から参照される各ノードについて */) { 
            if(/*そのノードが未探索なら*/) {
	            push(nextStage, /*そのノード*/);
			}
        }				
    }
}

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

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

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

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