資料2
幅優先探索と Queue
講義資料
今回から、各種アルゴリズムについて、問題に取り組みはじめてもらいます。 今回のお題は、幅優先探索と Queue です。
幅優先探索
木構造などの探索に、深さ優先探索(depth first search)
と幅優先探索(breadth first search)
があるのは知っていますよね?
幅優先探索は、 起点ノードから近いノードを順番に探索をかけていく手法で、 波紋のように探索領域が広がっていきます。 擬似コードで書くと、こんな感じです。
/* 単純に queue を使う場合 */
enqueue(start);
while(/* queue に要素がある*/) {
current = dequeue();
for(/* current から参照される各ノードについて */) {
if(/*そのノードが未探索なら*/) {
enqueue(/*そのノード*/);
}
}
}
ゴールがあるなら、ゴールにたどりついた時点でおしまいです。
対象が木構造なら、たどり着いた場所は必ず未探索ノード
なんですが、一般のグラフを探索する場合は、それまでに探索済みの場所かどうか、調べなくてはいけません。
- ハッシュや多次元配列を使って、探索済みノードを覚えておく
- 8パズル(or 15 パズル)のような問題の場合、すべての探索済みノードを覚えておくことはメモリ容量的に厳しいが、n(>2)手前以上に戻ることはありえないことを利用すれば、記憶する要素数を減らすことはできます。
さて、実際に課題2を解きながら理解を深めていきましょう。