前回は再帰呼び出しとバックトラックという、パズルを解くのに必要となる基本的なテクニックを説明しましたが、理解できましたでしょうか。再帰呼び出しを前面に押し出したため、再帰嫌いの方にはわかりにくい内容だったかもしれません。ですが、慣れてしまうと再帰呼び出しほど簡単で役に立つテクニックはそうそうありません。これを機会に再帰嫌いの方もそうでない方も、再帰呼び出しをぜひマスターしてください。
今回は再帰嫌いの方でも大丈夫なはずの「幅優先探索」というアルゴリズムを説明します。
バックトラックによる探索は「深さ優先探索」や「縦形探索」とも呼ばれるように、ひとつの経路を先へ先へと進めていきます。このため最初に見つかる経路が最短経路であるとは限りません。幅優先探索はすべての経路について平行に探索を進めていくため、最初に見つかる経路が最短経路となります。それでは、前回と同じ経路図を使って幅優先探索を具体的に説明しましょう。
Ｂ------Ｄ------Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ------Ｅ------Ｇ
図 1 : 経路図
幅優先探索の様子を図 2 に示します。
[A] ─┬─ [A,B] ─┬─ [A,B,C] ・・・・
│ └─ [A,B,D] ─┬─ [A,B,D,F] 行き止まり
│ └─ [A,B,D,E]
└─ [A,C] ─┬─ [A,C,B] ・・・・
└─ [A,C,E] ─┬─ [A,C,E,G] GOAL
└─ [A,C,E,D]
（出発点） （２節点） （３節点） （４節点）
図 2 : 幅優先探索
まず、出発点 A からひとつ進んだ経路 (2 節点) をすべて求めます。この場合は、[A, B] と [A, C] の 2 つあり、これをすべて記憶しておきます。次に、これらの経路からひとつ進めた経路 (3 節点) をすべて求めます。経路 [A, B] は [A, B, C] と [A, B, D] へ進めることができますね。ほかの経路 [A, C] も同様に進めて、すべての経路を記憶します。あとは、この作業をゴールに達するまで繰り返せばいいのです。
図 2 では、4 節点の経路 [A, C, E, G] でゴールに達していることがわかります。このように幅優先探索では、最初に見つかった経路が最短距離 (または最小手数) となるのです。この性質は、すべての経路を平行に進めていく探索順序から考えれば当然のことといえるでしょう。このことから、バックトラックの縦形探索に対して、幅優先探索は「横形探索」と呼ばれます。このあとも探索を繰り返せばすべての経路を求めることができます。
完成までの最小手数を求めるパズルを解く場合、幅優先探索を使ってみるといいでしょう。ただし、探索を進めるにしたがって、記憶しておかなければならないデータの総数が爆発的に増加する、つまりメモリを大量消費することに注意してください。
図 2 の場合では、メモリを大量消費することはありませんが、問題によってはマシンに搭載されているメモリが不足するため、幅優先探索を実行できない場合もあるでしょう。したがって、幅優先探索を使う場合は、メモリの消費量を抑える工夫も必要になります。
経路の管理は、「キュー (queue) 」というデータ構造を使うと簡単です。たとえば、チケットを買うときには窓口に長い列ができますが、キューはそれと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。一番後ろに並んで順番を待たなければいけません。列の先頭まで進むと、ようやくチケットを購入することができます。これを表したのが図 3 です。
out in
──────────────
<= A B C D E . . . Z <=
──────────────
図 3 : キューの構造
このように、キューはデータを取り出すときは列の先頭から行い、データを追加するときは列の後ろへ行います。このため、キューは「待ち行列」とか「先入れ先出し (FIFO : first-in, first-out) 」と呼ばれます。
このキューと対になるデータ構造が「スタック (stack) 」です。少々脱線しますが、ついでにスタックの動作も説明しましょう。
|-----| |[ A ]| |[ B ]| |[ A ]| |-----|
| | | |-----| |[ A ]| |-----| | | |
| | | | | | |-----| | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
(1) 空の状態 (2) PUSH A (3) PUSH B (4) POP B (5) POP A
図 4 : スタックの動作例
図 4 は、バネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもうひとつ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。ひとつ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。
この容器の動作が、スタックの動作なのです。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。
Ｃ言語でスタックとキューを実現する場合、配列を使う方法がいちばん簡単です。たとえばスタックを実現する場合、データを格納するための配列と、バネの役割を果たすスタックポインタを使います。スタックポインタは、本当にポインタを使ってもいいのですが、添字を表す整数でもかまいません。
まず、配列 buffer とスタックポインタ sp を用意します。sp の値は 0 に初期化しておきます。データをプッシュするときは buffer[sp] にデータを格納してから sp の値をインクリメントします。逆にポップするときは、sp の値をデクリメントしてから、buffer[sp] にあるデータを取り出します。スタックを操作するたびに、sp の値は図 5 のように変化します。
データをプッシュしていくと、sp の値は配列の大きさと等しくなります。この状態になると、スタックは満杯となります。これ以上データをプッシュすることはできません。また、sp が 0 のときはスタックが空の状態なので、ポップすることはできません。Ｃ言語の場合、配列の範囲チェックはプログラマの責任です。実際にプログラムを作るときは、スタックの状態をチェックする処理を忘れないでください。
buffer 0 1 2 3 4 5 sp
(1) [ ] 0 空の状態
(2) [ A ] 1 PUSH A buffer[sp++] <= A
(3) [ A B ] 2 PUSH B buffer[sp++] <= B
(4) [ A ] 1 POP buffer[--sp] => B
(5) [ ] 0 POP buffer[--sp] => A
図 5 : 配列によるスタックの実現
キューも配列を使って簡単に実現できます。先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータを、キューに格納されているデータとするのがポイントです。図 6 を見てください。
0 1 2 3 4 5 6 7 8 9
rear = 0 ↓
QUEUE [ ] : QUEUE は空
front= 0 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : データの追加
front= 0 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : 10を取り出す
front= 1 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : 20,30を取り出す
front= 3 ↑
図 6 : キューの動作
まずキューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値をインクリメントします。データ 10, 20, 30 を追加すると、図 6 のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。
次に、データを取り出す場合、front の示すデータを取り出しから front の値をインクリメントします。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなると、キューは空になることに注意してください。
rear, front ともに値は増加していく方向なので、いつかは配列の範囲をオーバーします。このため、配列を先頭と末尾がつがっているリング状と考え、rear, front が配列の範囲を超えたら 0 に戻すことにします。これを「リングバッファ」と呼びます。一般に、配列を使ってキューを実現する場合は、リングバッファとするのが普通です。ですが、今回はリングバッファを使う必要がないので、説明は割愛いたします。興味のある方は参考文献を読んでください。
幅優先探索でのキューの動作を図 7 に示します。
(1) ───── QUEUE ──────
┌── [A]
│ ───────────────
│
└─→ キューからデータを取り出す
(2) ───── QUEUE ──────
←─┐
─────────────── │
│
[A] の経路を進め [A,B] ───┤
キューに追加する [A,C] ───┘
(3) ───── QUEUE ──────
┌── [A,B] [A,C] ←─┐
│ ─────────────── │
│ │
└─→ [A,B] の経路を進めキューに追加 │
[A,B,C] [A,B,D] ────────┘
(4) ───── QUEUE ──────
┌── [A,C] [A,B,C] [A,B,D] ←─┐
│ ─────────────── │
│ │
└─→ キューに経路がある間繰り返す ──┘
図 7 : 幅優先探索とキューの動作
最初は、(1) のように出発点をキューにセットしておきます。次に、キューから経路を取り出し、(2) のように経路 [A] をひとつ進めて、経路 [A, B] [A, C] を作り、それをキューに追加します。(3) では、経路 [A,B] を取り出して、ひとつ進めた経路 [A, B, C] と [A, B, D] をキューに追加します。あとはキューに経路があるあいだ処理を繰り返せばいいわけです。
キューは先入れ先出し (FIFO) の性質を持つデータ構造なので、距離の短い経路から順番に処理されるため、幅優先探索として機能するのです。
それではプログラムを作りましょう。経路図は前回と同じく隣接リストで表します。
/* 隣接リスト */
#define NODE 7
const char adjacent[NODE][4] = {
1, 2, -1, -1, /* A */
0, 2, 3, -1, /* B */
0, 1, 4, -1, /* C */
1, 4, 5, -1, /* D */
2, 3, 6, -1, /* E */
3, -1, -1, -1, /* F */
4, -1, -1, -1, /* G */
};
次に経路を格納するキューを定義します。
/* Queue */ #define SIZE 64 char path[SIZE][NODE]; char length[SIZE];
キューの大きさ SIZE は、データ溢れが起こらないように設定します。配列 path に経路を、その経路長を配列 length にセットします。front, rear は、探索を行う関数 search の局所変数として定義します。プログラムは次のようになります。
リスト : 幅優先探索
void search( int start, int goal )
{
int rear = 1, front = 0;
path[0][0] = start;
length[0] = 0;
while( front < rear ){
int len = length[front];
int node = path[front][len];
int i, n;
for( i = 0; (n = adjacent[node][i]) != -1; i++ ){
if( memchr( path[front], n, len + 1 ) == NULL ){
if( n == goal ){
print_path( front, goal );
} else {
memcpy( path[rear], path[front], len + 1 );
path[rear][len + 1] = n;
length[rear] = len + 1;
rear++;
}
}
}
front++;
}
}
まずスタート地点をキューの先頭にセットします。キューにデータをセットしたのですから、rear の値は 1 に初期化します。あとは条件 front < rear を満たしているあいだは、キューにデータがあるので経路の探索を繰り返します。
次に、キューからデータを取り出し、その経路の先頭の頂点を変数 node にセットます。これは経路長から簡単に求めることができます。あとは、バックトラックと同様に、隣接リストから次の頂点を選び、経路を進めていきます。このとき、経路に含まれる頂点を選ばないことも同じです。
選んだ頂点が goal であれば、経路を print_path で表示します。そうでなければ、経路を進めます。このときはキューから取り出した経路に頂点を追加してはいけません。この経路から複数の経路を作ることになるので、元の経路を書き換えるのではなく、新しく経路を作りそれをキューにセットします。標準ライブラリ関数 memcpy で元の経路を rear の位置にコピーし、その経路に新しい頂点を、配列 length に経路長をセットします。それから rear の値をインクリメントし、新しい経路をキューに追加します。
for ループを終了すると、front をインクリメントし、次の経路を処理します。これで、すべての経路を求めることができます。それでは、実際に実行してみましょう。
実行結果 A C E G A B C E G A B D E G A C B D E G
結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる経路が最長となります。当然ですが、経路の総数は 4 通りとなります。
/*
* keiro_b.c : 経路の探索 (幅優先探索)
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NODE 7
#define SIZE 64
/* 隣接リスト */
const char adjacent[NODE][4] = {
1, 2, -1, -1, /* A */
0, 2, 3, -1, /* B */
0, 1, 4, -1, /* C */
1, 4, 5, -1, /* D */
2, 3, 6, -1, /* E */
3, -1, -1, -1, /* F */
4, -1, -1, -1, /* G */
};
/* Queue */
char path[SIZE][NODE];
char length[SIZE];
/* 経路の表示 */
void print_path( int n, int goal )
{
int i;
int len = length[n];
for( i = 0; i <= len; i++ ){
printf("%c ", path[n][i] + 'A' );
}
printf("%c\n", goal + 'A' );
}
/* 幅優先探索 */
void search( int start, int goal )
{
int rear = 1, front = 0;
path[0][0] = start;
length[0] = 0;
while( front < rear ){
int len = length[front];
int node = path[front][len];
int i, n;
for( i = 0; (n = adjacent[node][i]) != -1; i++ ){
if( memchr( path[front], n, len + 1 ) == NULL ){
if( n == goal ){
print_path( front, goal );
} else {
memcpy( path[rear], path[front], len + 1 );
path[rear][len + 1] = n;
length[rear] = len + 1;
rear++;
}
}
}
front++;
}
}
int main()
{
search( 0, 6 );
return 0;
}