パズルでプログラミング

●6 パズルの高速化

それでは、二分探索木を使って 6 パズルの高速化に挑戦しましょう。6 パズルの場合、データの総数が決まっているので、二分探索木は配列を使って表すことにします。また、キューとの兼ねあいから配列を使った方が簡単にプログラムできます。節とキューの定義は次のようになります。

/* 節の定義 */
typedef struct {
  char board[SIZE];
  int  right;
  int  left;
} NODE;

/* キュー */
NODE state[MAX_STATE + 1];       /* +1 はワーク領域 */
char space_position[MAX_STATE];
char move[MAX_STATE];

配列を使う場合、節の連結はポインタの代わりに配列の添字で表すことができます。したがって、子を格納する left と right は int で定義します。子がないことを表す値として、NULL の代わりに NIL をマクロで定義します。これは配列の範囲外の値であれば何でもいいのですが、このプログラムでは -1 としました。ルートは初期値を格納する state[0] とします。キューは構造体 NODE の配列で表すことができるので、局面の生成はいままでと同じように行うことができます。二分探索木は節の連結により構成されるので、このように配列を使って実現することもできるのです。

次は局面を二分探索木へ登録する関数 insert_tree を作ります。二分探索木のなかから state[i] と同じ局面を検索し、見つからなければ二分探索木へ登録します。プログラムは次のようになります。

リスト : 二分探索木への登録

int insert_tree( int i )
{
  int r, n = 0, *np = &n;
  while( *np != NIL ){
    r = memcmp( state[i].board, state[*np].board, SIZE );
    if( r == 0 ){
      return FALSE;
    } else if( r < 0 ){
      np = &(state[*np].left);
    } else {
      np = &(state[*np].right);
    }
  }
  state[i].left = NIL;
  state[i].right = NIL;
  *np = i;
  return TRUE;
}

節の連結はポインタではなく添字で行っていることに注意してください。変数 np は、節を格納する変数 right か left のアドレスを表します。最初はルートを指し示す変数 n のアドレスで初期化します。二分探索木には初期状態の局面が登録されているので、n の値が実際に書き換えられることはありません。このため、n を局所変数として定義しても問題ありません。あとの処理は、例題で示した関数 search と同じです。

最後に幅優先探索を行う関数 search を改造します。

リスト : 6 パズルの最長手数を求める

int search( void )
{
  int front = 0, rear = 1;
  memcpy( state[0].board, init_state, SIZE );
  state[0].right = NIL;
  state[0].left = NIL;
  space_position[0] = 6;
  move[0] = 0;
  while( front < rear ){
    int i, n, s = space_position[front];
    for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
      memcpy( state[rear].board, state[front].board, SIZE );
      state[rear].board[s] = state[rear].board[n];
      state[rear].board[n] = 0;
      if( insert_tree( rear ) ){
        space_position[rear] = n;
        move[rear] = move[front] + 1;
        rear++;
      }
    }
    front++;
  }
  print_answer( rear );
}

まず初期状態の局面を state[0] にセットします。left と right を NIL に初期化することをお忘れなく。あとは同一局面をチェックする関数を新しく作った insert_tree に変更します。二分探索木に登録できれば新しい局面なので、それをキューに登録します。変更はこれだけです。

それでは実行結果を表 1 に示します。

線形探索に比べ実行時間は約 50 倍の高速化となりました。比較回数も 1 / 100 になっています。二分探索木の効果が十分に出ていますね。

• プログラムを読む

●8 パズル

次はもう少し規模の大きい「8 パズル」に挑戦してみましょう。

              図 8 : 8 パズル

15 パズルは 4 行 4 列の盤ですが、8 パズルは 3 行 3 列と盤を小さくしたパズルです。8 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、9! = 362880 通りあります。ところが 15 パズルや 8 パズルの場合、参考文献 [5] によると 『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にした移行できない』 ことが証明されているそうです。図 8 (2) は 7 と 8 を入れ替えただけの配置です。この場合、交換の回数が奇数回のため完成形に到達することができない、つまり解くことができないのです。したがって、完成形に到達する局面の総数は 9! / 2 = 181440 個となります。

これから作るプログラムでは、6 パズルと同様に 8 パズルが完成するまでにいちばん手数がかかる配置を求めることにします。8 パズルは 6 パズルのプログラムを改造することで簡単に作ることができます。まず隣接リストを定義します。座標は図 9 のように定義しました。

リスト : 隣接リストの定義

/* 定数 */
#define SIZE  9
#define MAX_STATE 181440

/* 隣接リスト */
const char adjacent[SIZE][5] = {
  1, 3,-1,-1,-1,
  0, 4, 2,-1,-1,
  1, 5,-1,-1,-1,
  0, 4, 6,-1,-1,
  1, 3, 5, 7,-1,
  2, 4, 8,-1,-1,
  3, 7,-1,-1,-1,
  4, 6, 8,-1,-1,
  5, 7,-1,-1,-1,
};

/* 初期状態 */
char init_state[SIZE] = {
  1, 2, 3, 4, 5, 6, 7, 8, 0
};

マクロ定義の定数 SIZE と MAX_STATE を変更します。あとは、初期状態とキューの初期化を変更します。空白の位置を示す配列 space_position の初期値の修正をお忘れなく。修正はこれだけです。詳細は ソースファイル eight1.c を参照してください。実行結果は図 10 のようになりました。

      図 10 : 31 手で解ける局面

手数は 31 手で局面は 2 つありました。実行時間は約 13 秒、結構時間がかかっていますね。そこで、もうひとつ工夫をしてみます。8 パズルの場合、同じ駒を続けて動かすと、駒を元の場所に戻すことになってしまいます。これは元の局面に戻ることなので、わざわざ検索する必要はありません。いまのプログラムでは、このチェックを行っていないため無駄な検索が行われています。同じ駒を続けて動かさないようにすればもう少し速くなるでしょう。

プログラムの改造は簡単です。動かした駒の種類を配列 move_piece に格納します。駒を動かすときは、move_piece と違う種類の駒を動かすようにすればいいわけです。実際に改造を行ったプログラムが eight2.c です。実行結果は約 8.5 秒と速くなりましたが、それでも時間がかかりますね。

二分探索木でデータを探す場合、最下層のデータを見つける場合が最悪で、木の高さと同じ回数だけ比較が行われます。したがって、二分探索木はできる限り木の高さを低くするように構成した方が、探索効率は良くなります。木の高さは、データ数を n とすると、データがランダムに挿入されれば、log n 程度におさまります。ところが、ソートされたデータを二分探索木に挿入していくと、データは右側の木にしか挿入されず、連結リストと同じく線形探索になってしまいます。このプログラムではデータの総数が 181440 個なので、木の高さが 18 程度に収まっていれば最高の性能を発揮するのですが、実際に木の高さを求めると 73 という結果になりました。大きくバランスが崩れていることがわかります。

このように、二分探索木はバランスが崩れると性能が劣化する欠点があるのです。これを補うために、木のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは、AVL 木、2-3 木、B 木、B* 木などがあります。これらの平衡木は、原理そのものは簡潔明瞭なのですが、実際のプログラムはとても大変で、Ｃ言語初心者には荷が重過ぎます。そこで、高速検索アルゴリズムの本命である「ハッシュ法」を使うことにします。

●ハッシュ法

ハッシュ法は、コンパイラやインタプリタなどで予約語や関数名、変数名などの管理に使われている方法です。また、Tcl や Perl など連想配列をサポートしているスクリプト言語がありますが、その実装にはハッシュ法が使われています。Perl で連想配列をハッシュと呼ぶのは、アルゴリズムの名称からきているのです。

ハッシュ法は、設計をうまく行えば 1 回の比較でデータを見つけることができます。実際、コンパイラの予約語のように探索するデータが固定されている場合は、そのように設計することが可能です。不特定多数のデータが探索対象になる場合は、すべてのデータを 1 回の比較で見つけることはできませんが、数回程度の比較で見つけるように設計することは可能です。

では、具体的に説明しましょう。ハッシュ法は、ハッシュ表と呼ばれるデータを格納する配列と、データを数値に変換するハッシュ関数を用意します。たとえば、ハッシュ表の大きさを n とすると、ハッシュ関数はデータを 0 から n - 1 までの整数値に変換するように作ります。この値をハッシュ値と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。

簡単な例題として、文字列を識別する処理を考えてみましょう。データが文字列の場合、次のハッシュ関数がよく使われます。

リスト : 文字列のためのハッシュ関数

int hash( char *string )
{
  int value = 0;
  while( *string != '\0' ){
    value += *string++;
  }
  return value % HASH_SIZE;
}

HASH_SIZE はハッシュ表の大きさを定義したマクロです。value を HASH_SIZE で除算した余りをハッシュ値としていることに注意してください。これでハッシュ値をハッシュ表の大きさに収めることができます。たとえば、HASH_SIZE を 100 とした場合、曜日を表す単語のハッシュ値は表 2 のようになります。

単語のハッシュ値はすべて異なっていますね。曜日を識別するだけの処理であれば、これらの文字列をハッシュ表に登録すればいいのです。文字列のハッシュ値を計算し、そこに登録されているデータと比較します。等しいデータであれば、曜日を表す文字列であることがわかります。異なるデータであれば、その文字列は曜日を表していません。また、ハッシュ表に文字列が登録されていなければ、それも曜日を表していないことがわかります。このように、ハッシュ法を使えば一回の比較でデータを見つけることができます。

ただし、これはデータが限定されている場合の話です。たとえば、単語の出現回数をカウントする処理を考えてみましょう。テキストファイルのなかに含まれる単語の種類は、テキストを読んでみないとわかりません。したがって、テキストから単語を切り出し、それをハッシュ表に登録する処理が必要になります。ハッシュ表には有限の大きさしか割り当てることができないので、単語の種類がそれより多いと、ハッシュ値が重なる場合が必ず発生します。また、ハッシュ表が十分に大きくても、不特定多数のデータに対し、すべて異なるハッシュ値を生成するハッシュ関数を作ることは不可能です。つまり、異なったデータに対し、同じハッシュ値が生成される場合があるのです。これをハッシュ値の衝突といいます。データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。

ひとつは空いている場所を探して、そこに入れる方法です。新しい場所を探すといっても、テーブルの先頭から線形探索するのではなく、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。これを空いている場所が見つかるまで繰り返します。この方法だと、データの最大数はハッシュ表の大きさに制限されます。

もうひとつは、ハッシュ表に複数のデータを格納することです。配列にはひとつのデータしか格納できないので、複数個のデータをまとめて格納しておく工夫が必要になります。このときによく利用されるデータ構造が「連結リスト」です。ハッシュ表にはデータをそのまま格納しないで、連結リストへのポインタを格納すればいいのです。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。

ただし、ハッシュ値の衝突が頻繁に発生すると、データを格納する連結リストが長くなるため、探索時間が余分にかかってしまいます。効率よく探索を行うためには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。また、連結リストの代わりに二分探索木を使ってもかまいません。今回は十分に大きなハッシュ表を用意できるので、連結リストを使って複数のデータを格納することにします。

●ちょっと寄り道

参考文献 [2] [5] には、順列を 1 対 1 に対応する数値に変換するアルゴリズムが紹介されています。つまり、ハッシュ値の衝突が起きないハッシュ関数とみなすことができます。この方法を使うことで、同一局面のチェックを高速に行うことができます。まあ、いつも都合のいいハッシュ関数が用意できるわけではありません。汎用的な方法を覚えておいた方がいろいろなプログラムに応用することができるでしょう。

●８パズル解法の高速化

それでは、ハッシュ法を使って 8 パズルの解法高速化に挑戦しましょう。このプログラムでも、連結リストを配列で表すことにします。セルとキューの定義は次のようになります。

/* 連結リスト */
typedef struct {
  char board[SIZE];
  int  next;
} CELL;

/* キュー */
CELL state[MAX_STATE + 1];       /* +1 はワーク領域 */
char space_position[MAX_STATE];
char move_piece[MAX_STATE];
char move[MAX_STATE];

二分探索木と同様に、セルの連結はポインタの代わりに配列の添字で表すため、next は int で定義します。終端はマクロ NIL (-1) で表します。次にハッシュ表を定義します。

/* ハッシュ表 */
#define HASH_SIZE 19997
int hash_table[HASH_SIZE];

ハッシュ表もセルを指し示すので int で定義します。大きさは HASH_SIZE で表します。参考文献 [2] によると 『この値が素数だと安心である』 とのことなので、連結リストの長さが 10 より小さくなるように 19997 としました。ハッシュ関数も簡単です。

リスト : ハッシュ関数

int hash_value( int n )
{
  int i, value = 0;
  for( i = 0; i < SIZE; i++ ){
    value = value * 10 + state[n].board[i];
  }
  return value % HASH_SIZE;
}

局面 board を 10 進数の数字とみなし、それを HASH_SIZE で割った余りをハッシュ値としています。最後にデータを登録する関数 insert_hash を作ります。

リスト : ハッシュ表への登録

int insert_hash( int i )
{
  int h = hash_value( i );
  int n = hash_table[h];
  while( n != NIL ){
    if( memcmp( state[i].board, state[n].board, SIZE ) == 0 ){
      return FALSE;
    }
    n = state[n].next;
  }
  state[i].next = hash_table[h];
  hash_table[h] = i;
  return TRUE;
}

最初にハッシュ値を求め、ハッシュ表に格納されている連結リストを線形検索します。見つからない場合は、連結リストの先頭に登録します。とても簡単ですね。

あとは、プログラムを改造するだけです。関数 search では、初期状態をハッシュ表に登録するため insert_hash を呼び出し、局面のチェックする処理を insert_hash に変更します。最後に関数 main でハッシュ表を NIL に初期化する処理を追加します。これで プログラム (eight3.c) は完成です。

実際に実行してみると、時間は約 2.5 秒で約 3 倍程度の高速化となりました。ところで、ハッシュ法はハッシュ関数によって、性能が大きく左右されます。HASH_SIZE の選び方ひとつでも、実行時間は大きく異なります。たとえば、データ数のちょうど 1/10 である 18144 とすると、実行時間は約 8.5 秒と遅くなります。それよりも少ない 16384 では、逆に約 2.5 秒と遅くはなりません。このように、ハッシュ法では適切なハッシュ関数を用意するのが結構大変なのです。

ハッシュ法はデータを高速に検索できる優れたアルゴリズムです。データを検索するだけならば、二分探索木よりもハッシュ法が優れています。ですが、二分探索木にはハッシュ法にはない長所があります。二分探索木はデータの大小関係で構成されているので、左の木をたどることで最小値を、右の木をたどることで最大値を簡単に求めることができます。ハッシュ法で最大値や最小値を求めるには、すべてのデータを調べなければいけません。また、二分探索木では通りがけ順でデータを出力すれば、ソートされた結果を得ることができます。データの大小関係を処理する場合は、ハッシュ法よりも二分探索木を選ぶといいでしょう。

●まとめ

パズルを例題にして、3 回にわたり基本的なアルゴリズムとデータ構造を説明しました。解を探索するアルゴリズムではバックトラックと幅優先探索が基本です。データを高速に検索するには、二分探索木やハッシュ法を検討してみるといいでしょう。このほかにも、スタック、キュー、連結リスト、木構造、グラフなど基本的なデータ構造を使いました。これらのアルゴリズムやデータ構造は、パズルを解くだけではなく、ほかのプログラムを作るときにも必ず役に立ちます。ぜひ、活用してみてください。

次回は、もう少し複雑なパズルに挑戦してみましょう。お楽しみに。