幅優先探索/アルゴリズム講座

第４章: 幅優先探索

　再帰を使った探索は、とても簡単なプログラムでシラミ潰しに総てのパターンを調べられますが、調べる順序は仮定から仮定へと強引に突き進むので、直ぐ目の前に解があったとしても、随分と遠回りしてから解にたどり着くことがあります。
　探索順序が深さを優先しているので、「深さ優先探索」と言われています。

　1手目で可能なパターンを総て作って「1手目グループ」とし、次にその「1手目グループ」の要素を一つずつ呼び出してそれに1手だけ加えて「2手目グループ」を作る。同様にして「2手目グループ」に1手だけ加えて「3手目グループ」を作っていく。
　この様な探索方法を「幅優先探索」といいます。そして当然ながら、最初に見つかった解が「最短解」になります。

　しかしながら、この探索順序を実現させるには、生成された局面をどこかに保存しておかなくてはなりません。従って、 大きな保存場所が必要になります。ここでは汎用性の高いハッシュ法を使った幅優先探索を紹介します。

　例題５: ５パズル

　有名な15パズルのミニ版で、ルールは15パズルと同じです。
　左図の状態から最小手順で右図のように並べ変えて下さい。

　まず、局面の保存場所を作ります。そして、ハッシュ法とは、局面の保存場所(番地)をある計算によって求め、ダイレクトにそこを探しに行くものです。局面を保存できる数がHSIZE個あるとして,先ず局面を何らかの一定の規則で数値化しそれをHSIZEで割った余りを求める。この値をハッシュ値といって、これをその局面の保存場所(番地)とします。
　ある局面をハッシュ値に変換する関数をハッシュ関数と言いますが、これは何の意味もないメチャクチャな計算をさせることです。ここでハッシュ値(hash)は、

　　0 ≦ hash ＜HSIZE の範囲に出来る
　　だけ一様に分布するのが理想的です。

　しかし異なる２つの局面が同じハッシュ値になることは当然考えられます。もし保存しようとした場所に他の異なる局面が既に保存していれば、最も簡単な対処法として空き場所が見つかるまで、

　　hash ＝（hash + 1）% HSIZE

の式で再計算します。これを再ハッシュと言います。対処法は他にもありますが、この方法が最も手軽な方法だと思います。
　ボード設計をList.4-1のようにするとハッシュ関数は例えばList.4-2のようになります。

　前準備が出来たので、いよいよ本題ですが、幅優先探索の探索順序を実現させるには、待ち行列(キュー)を使います。待ち行列とは、列の先頭から順に出番が来て、列に加わる時は列の後ろへ並びジッと自分が先頭に来るのを待っています。そして、この行列には局面を保存した時の番地を入れておきます。List.4-3

　反復深化は同じ探索を何度も繰り返すというロスがありますが、幅優先探索はそのロスが無いので高速です。しかし、保存用に大きなメモリが必要になるという弱点があります。

ホームページへ戻る

List.4-1　ボード設計

#define  BOARD_SIZE  6 // ボードサイズ

//*******************************
//  ボードの座標
//  +--+--+--+
//  |０|１|２|
//  +--+--+--+
//  |３|４|５|
//  +--+--+--+
//*******************************

int  BOARD[BOARD_SIZE];  // ボード

List.4-2　ハッシュ関数(局面の格納番地を求める)

// 局面を数値化する
// 2ビットシフトして加算する
// というメチャクチャな計算 
hash = 0;
for (i=0; i<BOARD_SIZE; i++)
    hash = (hash << 2) + BOARD[i];
hash %= HASH_SIZE;   // ハッシュサイズに収める

// 実際の格納場所を見つける
for (;;) {
    ptr = &HASH[hash];              // 格納場所のポインタ
    if (ptr->space == EMPTY) break; // この場所は未使用

    // 同じ局面かをチェック
    for (i=0; i<BOARD_SIZE; i++)
        if (ptr->board[i] != BOARD[i]) break;
    if (i == BOARD_SIZE) break;     // 同じ局面である

    // 異なる局面で使用済みなので再ハッシュ
    hash = (hash + 1) % HASH_SIZE;
}
return ptr; // 格納場所のポインタを返す

List.4-3　待ち行列(キュー)を使った幅優先探索

int  Qhead;  // キューの先頭位置  
int  Qtail;  // キューの後ろ位置  

// キューにデータがある限りループ
while (Qhead < Qtail) {
    address1 = QUEUE[Qhead++];   // キュー先頭より取る
    // address1に保存されている局面をBOARD上に再現する

    for (可能な次の手の総てについて) {
        // 新たな局面を生成する;

        // 始めての局面ならハッシュ表とキューに追加する
        address2 = HashFunc();  // 格納番地を求める
        if (address2->space == EMPTY) {   // 空なら
            BucketIn(address1, address2); // ハッシュ表へ
            QUEUE[Qtail++] = address2;    // キュー後ろへ
        }
        if (解を発見した) {
            return TRUE; // 解を発見しました
        }

        // 局面を元に戻す;
    }
}
return FALSE; // 解がありません

List.4-4　例題５:５パズル を幅優先探索で解く

プログラムリスト→　5puzzle.c