アルゴリズム講座/実践編/ハッシュ法(幅優先探索)
ホームページへ戻る 目次へ戻る
パズル問題解法のアルゴリズム講座

実践編

ハッシュ法(幅優先探索)

 思考アルゴリズムの王様バックトラックにも弱点があります。その弱点と克服法を考えてみます。ちょっと難しくなりますが「再帰」は使用しないので、ある意味ではむしろ人に分かり易いアルゴリズムなのかも知れません。

1.「15パズル」のミニ版「5パズル」を解く

    右図の5枚のパネルをランダムにシャッフル後、パネルを上下左右に
   スライドして元の順番通りになる様に最小の手順で並べ直して下さい。

    この問題に先ほどのバックトラックを使っても失敗します。何故なら
   「堂々巡り」という現象が発生してしまうからです。
    堂々巡りとは、局面Aから局面Bへと変化しさらに局面Cへと探索が
   進んでいったが、もしいつしか元の局面Aに変化してしまったらこれま
   での探索の過程が繰り返し実行されてしまいます。これでは無限地獄。
    これを防止するには、探索過程の総ての局面を保存しておいて過去に
   同じ局面がなかったかをチェックしながら
探索しなければなりません。
    そうなると次のことが問題となります。

     膨大な量の保存局面の中からいかに速く指定の局面を探し出すか?

    ひとつひとつ照合したのでは探索時間がバカになりません。ここで登場するのがハッシュ法です。

2.ハッシュ法

    ハッシュ法とは、局面の保存場所をある計算によって求め、ダイレクトにそこを探しに行くものです。
    局面を保存できる場所数がM個あるとして、先ず局面を何らかの規則で数値化しそれをMで割った
   余りを求める。この値をハッシュ値といい、これをその局面の保存場所(番地)とする。ここで大切なこと
   はハッシュ値(h)は、0≦h<Mの範囲に出来るだけ一様に分布することです。それでも異なる2つの
   局面が同じハッシュ値を持つことを覚悟しなければなりません。もし保存しようとした場所が他の局面の
   保存で既に使用済みなら、最も簡単な対処法として空き場所が見つかるまでh=(h+1)%Mの式で
   再計算します。対処法は他にもありますが、この方法が最も手軽な方法としてよく利用されます。

3.ハッシュ関数を作る

    ある局面をハッシュ値に変換する関数をハッシュ関数と言い、こんな方法がよく用いられます。
   局面のそれぞれの位置のデータを少しずつビット値をシフトして加算し一つの数値を作ります。

  /* ハッシュ関数 */
  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;
  }

4.幅優先探索で最小手順を見つける

C言語ソースリスト

Java言語ソースリスト

Javaアプレットの実行

    最小手順を効率良く発見するには「幅優先探索(横型探索)」をハッシュ法と
   ペアで用います。バックトラックが仮定から仮定へと強引に突き進むのに対し、
   幅優先探索は1手で可能な総ての局面を作り出してハッシュ法で保存しておき、
   次はその局面をひとつひとつ呼び戻して2手で可能な総ての局面を作り出して
   同様に保存していくという、強引さの全くない堅実な方法で探索を進めます。
    そうすれば、最初に見つけた解が最小手順のはずなので探索を終了します。
   勿論、探索中に生成した局面が過去に保存済みなら無視すればいいのです。

    なんとなく理解して頂けたと思いますが、この方法をどう具体的に実現すれ
   ばよいのか。それには、待ち行列(キュー)を使うと簡単に実現出来ます。
   待ち行列とは、列の先頭から順に出番が来て、あとから来た人は列の後ろへ
   並びジッと自分の出番が来るのを待っています。そして、この列には局面を保
   存した時の格納番地
を入れておけばいいのです。

    int QUEUE[M]; /* 待ち行列 */
    int Qtop;     /* 待ち行列の先頭位置 */
    int Qend;     /* 待ち行列の後ろ位置 */

    while (Qtop < Qend) {
        address1 = QUEUE[Qtop++];         /* キュー先頭より取る */
        address1に保存してある局面を呼び出す;
        for (1手加えて新たな局面を順次生成する) {
            address2 = hash_func();         /* 格納番地を求める */
            if (address2の中 == カラ) {     /* 未登録なら登録   */
                この局面をaddress2に保存する;
                QUEUE[Qend++] = address2;   /* キュー後ろに追加 */
            }
            if (解を発見した) return 発見しました;
        }
    }
    return 解が在りません;


目次へ戻る   前の頁へ戻る  次の頁へ進む