パズル問題解法のアルゴリズム講座
実践編
ハッシュ法(幅優先探索)
１．「１５パズル」のミニ版「５パズル」を解く
 |
スライドして元の順番通りになる様に最小の手順で並べ直して下さい。
この問題に先ほどのバックトラックを使っても失敗します。何故なら
「堂々巡り」という現象が発生してしまうからです。
堂々巡りとは、局面Ａから局面Ｂへと変化しさらに局面Ｃへと探索が
進んでいったが、もしいつしか元の局面Ａに変化してしまったらこれま
での探索の過程が繰り返し実行されてしまいます。これでは無限地獄。
これを防止するには、探索過程の総ての局面を保存しておいて過去に
同じ局面がなかったかをチェックしながら探索しなければなりません。
そうなると次のことが問題となります。
膨大な量の保存局面の中からいかに速く指定の局面を探し出すか？
ひとつひとつ照合したのでは探索時間がバカになりません。ここで登場するのがハッシュ法です。
２．ハッシュ法
ハッシュ法とは、局面の保存場所をある計算によって求め、ダイレクトにそこを探しに行くものです。局面を保存できる場所数がＭ個あるとして、先ず局面を何らかの規則で数値化しそれをＭで割った
余りを求める。この値をハッシュ値といい、これをその局面の保存場所(番地)とする。ここで大切なこと
はハッシュ値(h)は、０≦ｈ＜Ｍの範囲に出来るだけ一様に分布することです。それでも異なる２つの
局面が同じハッシュ値を持つことを覚悟しなければなりません。もし保存しようとした場所が他の局面の
保存で既に使用済みなら、最も簡単な対処法として空き場所が見つかるまでｈ＝（ｈ＋１）％Ｍの式で
再計算します。対処法は他にもありますが、この方法が最も手軽な方法としてよく利用されます。
３．ハッシュ関数を作る
ある局面をハッシュ値に変換する関数をハッシュ関数と言い、こんな方法がよく用いられます。局面のそれぞれの位置のデータを少しずつビット値をシフトして加算し一つの数値を作ります。
/* ハッシュ関数 */
int hash_func() {
int hash; /* ハッシュ値 */
long num = 0;
/* 局面を数値化しハッシュ値を求める */
for (局面の全位置をスキャンする)
num = (num << 2) + (その位置のデータ);
hash = (int)(num % M);
for (;;) {
if (格納番地hashの局面 == 未使用) break; /* カラの格納場所発見 */
if (格納番地hashの局面 == 今の局面) break; /* 同型がすでにあった */
hash = (hash + 1) % M; /* 異なる局面で使用済 */
}
return hash;
}
４．幅優先探索で最小手順を見つける
|
Ｃ言語ソースリスト
Javaアプレットの実行 |
ペアで用います。バックトラックが仮定から仮定へと強引に突き進むのに対し、
幅優先探索は１手で可能な総ての局面を作り出してハッシュ法で保存しておき、
次はその局面をひとつひとつ呼び戻して２手で可能な総ての局面を作り出して
同様に保存していくという、強引さの全くない堅実な方法で探索を進めます。
そうすれば、最初に見つけた解が最小手順のはずなので探索を終了します。
勿論、探索中に生成した局面が過去に保存済みなら無視すればいいのです。
なんとなく理解して頂けたと思いますが、この方法をどう具体的に実現すれ
ばよいのか。それには、待ち行列(キュー)を使うと簡単に実現出来ます。
待ち行列とは、列の先頭から順に出番が来て、あとから来た人は列の後ろへ
並びジッと自分の出番が来るのを待っています。そして、この列には局面を保
存した時の格納番地を入れておけばいいのです。
int QUEUE[M]; /* 待ち行列 */
int Qtop; /* 待ち行列の先頭位置 */
int Qend; /* 待ち行列の後ろ位置 */
while (Qtop < Qend) {
address1 = QUEUE[Qtop++]; /* キュー先頭より取る */
address1に保存してある局面を呼び出す;
for (１手加えて新たな局面を順次生成する) {
address2 = hash_func(); /* 格納番地を求める */
if (address2の中 == カラ) { /* 未登録なら登録 */
この局面をaddress2に保存する;
QUEUE[Qend++] = address2; /* キュー後ろに追加 */
}
if (解を発見した) return 発見しました;
}
}
return 解が在りません;