今回は、地図上の A 地点から B 地点までの道順を求める、といった「経路の探索」と呼ばれる問題を取り上げます。「探索」にはいろいろな種類があります。たとえば、パズルを解く場合、あらゆる可能性の中から正解に行き着く手順を探すことですから、探索の一つと考えることができます。そして、探索でよく用いられる最も基本的な方法に「バックトラック (backtracking)」があります。
簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけませんね。つまり、失敗したら後戻りして別の道を選ぶ、という試行錯誤をゴールに行き着くまで繰り返すわけです。これがバックトラックの基本的な考え方です。
バックトラックは迷路を解くだけではなく、いろいろな問題に応用できる方法です。とくに、すべての解を求める場合、バックトラックが適しています。すべての解をもれなく見つけることができます。もちろん、経路の探索もバックトラックで解くことができます。
このほかに、もう一つ基本的な方法として「幅優先探索」があります。バックトラックの場合、失敗したら後戻りして別の道を選び直しますが、幅優先探索の場合は、全ての経路について並行に探索を進めていきます。幅優先探索は最短手順を求めるのに適したアルゴリズムですが、問題によっては必要となるメモリの量がとても多くなり、幅優先探索を使用することができない場合があります。このような場合、「反復深化」という方法を使うと、多少時間はかかりますが、少ないメモリで最短手順を求めることができます。今回はこの 3 つの方法で経路を求めてみましょう。
まず最初に「グラフ (graph)」というデータ構造を説明します。一般にグラフというと、 円グラフや折れ線グラフといった図表を思い出す人が多いと思います。数学の「グラフ理論」では、いくつかの点とそれを結ぶ線でできた図形を「グラフ」といいます。次の図を見てください。
頂点 辺
↓ ↓
●─────────●
│ │
│ │
│ │
●─────────●
図 : グラフの例
上図に示すように、グラフは点とそれを接続する線から構成されています。点のことを「頂点 (vertex)」や「節点 (node)」と呼び、線のことを「辺 (edge)」や「弧 (arc)」と呼びます。グラフには 2 種類あって、辺に向きの無いグラフを「無向グラフ」といい、辺に向きがあるグラフを「有向グラフ」といいます。有向グラフは一方通行の道と考えればいいでしょう。 次の図を見てください。
(1) Ａ──────────→Ｂ 有向グラフ
(2) Ａ←─────────→Ｂ 無向グラフ
図 : 有向グラフと無向グラフ
たとえば、図 (1) では A 地点から B 地点へ行くことができますが、一方通行のため B 地点から A 地点に戻ることはできません。これが有効グラフです。(2) の無効グラフでは、A 地点から B 地点へ行くことができるし、逆に B 地点から A 地点に戻ることもできます。
データ間のさまざまな関係を表す場合、グラフはとても役に立ちます。たとえば、下図のように経路をグラフで表すことができます。
Ｂ───Ｄ───Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ───Ｅ───Ｇ
図 : 経路図
上図ではアルファベットで頂点を表しています。この例では経路をグラフで表していますが、このほかにもいろいろな問題をグラフで表現することができます。
グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行列で表すことができます。経路図を隣接行列で表すと次のようになります。
│A B C D E F G ─┼─────── A│0 1 1 0 0 0 0 B│1 0 1 1 0 0 0 C│1 1 0 0 1 0 0 D│0 1 0 0 1 1 0 E│0 0 1 1 0 0 1 F│0 0 0 1 0 0 0 G│0 0 0 0 1 0 0 図 : 隣接行列
A に接続している頂点は B と C なので、A 行の B と C に 1 をセットし、接続していない頂点には 0 をセットします。経路が一方通行ではない無向グラフの場合は、A 列の B と C にも 1 がセットされます。これをＣ言語でプログラムすると、次のようになります。
リスト : 隣接行列
#define N 7
int adjacent[N][N] = {
{0, 1, 1, 0, 0, 0, 0}, // A
{1, 0, 1, 1, 0, 0, 0}, // B
{1, 1, 0, 0, 1, 0, 0}, // C
{0, 1, 0, 0, 1, 1, 0}, // D
{0, 0, 1, 1, 0, 0, 1}, // E
{0, 0, 0, 1, 0, 0, 0}, // F
{0, 0, 0, 0, 1, 0, 0}, // G
};
頂点 A から G を数値 0 から 6 に対応させるところがポイントです。隣接行列は 2 次元配列で表します。
隣接行列の欠点は、辺の数が少ない場合でも N 行 N 列の行列が必要になることです。つまり、ほとんどの要素が 0 になってしまい、メモリを浪費してしまうのです。この欠点を補う方法に隣接リストがあります。これはつながっている頂点を格納する方法です。
A => (B, C) B => (A, C, D) C => (A, B, E) D => (B, E, F) E => (C, D, G) F => (D) G => (E) 図 : 隣接リスト
これをＣ言語でプログラムすると次のようになります。
リスト : 隣接リスト
#define N 7
#define M 4
enum {S, A, B, C, D, E, F, G};
int adjacent[N + 1][M] = {
{S},
{B, C, S},
{A, C, D, S},
{A, B, E, S},
{B, E, F, S},
{C, D, G, S},
{D, S},
{E, S},
};
Ｃ言語で定数を記述するとき、伝統的にはマクロ記号を使いますが、ANSI C 規格 (C89/C90) から「列挙型 (enumerated type)」を利用できるようになりました。列挙型の宣言には enum を使います。
enum [タグ名] {name0, name1, name2, name3, name4, name5, ... }
Ｃ言語の場合、enum タグ名 で列挙型を宣言します。{ ... } の中の要素を「列挙定数」とか「列挙子」と呼びます。列挙子には整数値が順番に割り当てられます。デフォルトでは先頭の name0 に 0 が割り当てられ、name1 に 1 が、name2 に 2 が割り当てられます。
列挙子の値を指定することもできます。たとえば、name3 = n とすると、name3 の値は n になり、name4 には n + 1, name5 には n + 2 が割り当てられます。なお、定数を定義するだけでよければ、タグ名を省略してもかまいません。列挙子を整数として扱うことができます。
列挙子 S は隣接リストの終端を表すために使います。S の値は 0 になるので、頂点 A から G の値は 1 から 7 になります。今回は隣接リストを二次元配列で表します。終端 S も含めると隣接リストの長さは最大で 4 になります。これをマクロ M で定義しています。したがって、大きさは (N + 1) * M になります。もちろん、連結リストを定義して、それを使って隣接リストを実現することもできます。
ところで、隣接リストにも欠点があります。たとえば、E と G が接続しているか調べるには、データを順番に調べていくしか方法がありません。このため、接続の判定に時間がかかることがあるのです。まあ、頂点に接続されている辺の数が少なければ、処理速度が極端に遅くなることはないでしょう。
それではプログラムを作りましょう。今回は隣接リストを使って、A から G までの経路をバックトラックで求めます。バックトラックを再帰呼び出しで実現する場合、次の頂点へ進むことを再帰呼び出しに対応させるのがポイントです。たとえば、経路を探索する関数を search としましょう。search は引数として現在地点の頂点を受け取ることにします。最初は search(A) と呼び出します。そして、A から B へ進むには search(B) と呼び出します。これで B へ進むことができます。
それでは、A に戻るにはどうしたらいいのでしょう。search(B) は search(A) から呼び出されたので、search(B) の実行を終了すれば、呼び出し元である search(A) に戻ることができます。つまり、関数の実行を終了すれば、一つ手前の地点にバックトラックできるのです。このように再帰呼び出しを使うと、進むことと戻ることを関数呼び出しで簡単に実現することができます。
それでは具体的に説明しましょう。経路は配列 path に頂点を格納して表すことにします。プログラムは次のようになります。
リスト : 深さ優先探索
// 経路
int path[N];
bool visited[N + 1];
// 経路の表示
void print_path(int n)
{
for (int i = 0; i < n; i++)
printf("%c ", 'A' + path[i] - 1);
printf("\n");
}
// 深さ優先探索
void dfs(int n, int goal)
{
int x = path[n - 1];
if (x == goal) {
print_path(n);
} else {
for (int i = 0; i < M; i++) {
int y = adjacent[x][i];
if (y == S) break;
if (!visited[y]) {
path[n] = y;
visited[y] = true;
dfs(n + 1, goal);
visited[y] = false;
}
}
}
}
探索は関数 dfs で行います。引数 n が訪問した頂点の個数、goal がゴールを表します。最初に、path の末尾から現在地点 x を取り出します。そして、x がゴール goal かチェックします。これが再帰呼び出しの停止条件になります。ゴールに到達したら print_path で経路を表示します。ここで探索を終了することもできますが、バックトラックすることで全ての経路を見つけることができます。
ゴールに到達していない場合、adjacent から頂点 x の隣接リストを取り出します。for ループで adjacent[x] の要素を順番に取り出して変数 y にセットし、dfs を再帰呼び出しします。y の値が S ならば break で for ループを脱出します。
このとき、経路に含まれている頂点を選んではいけません。そうしないと、同じ道をぐるぐると回る巡回経路が発生し、ゴールまでたどり着くことができなくなります。このチェックを配列 visited で行います。visited[x] が true でなければ、path[n] に x をセットし、visited[x] を true に書き換えます。それから、dfs を再帰呼び出しして、戻ってきたら visited[x] を false に戻します。
最後に main から dfs を呼び出します。
リスト : 深さ優先探索 (sample1600.c)
int main(void)
{
path[0] = A;
visited[A] = true;
dfs(1, G);
return 0;
}
最初に、スタート地点 A を path[0] にセットし、visited[A] を true に書き換えます。あとは dfs(1, G) と呼び出すだけです。
実行結果は次のようになります。
$ clang sample1600.c $ ./a.out A B C E G A B D E G A C B D E G A C E G
4 通りの経路を見つけることができました。バックトラックによる探索は経路を先へ先へ進めるので、「縦形探索」とか「深さ優先探索 (depth first search)」と呼ばれています。このため、結果を見てもわかるように、最初に見つかる経路が最短経路とは限りません。最短経路を求めるのに適したアルゴリズムが「幅優先探索 (breadth first search)」です。
バックトラックによる探索は一つの経路を先へ先へと進めていきます。このため最初に見つかる経路が最短経路であるとは限りません。幅優先探索は全ての経路について平行に探索を進めていくため、最初に見つかる経路が最短経路となります。それでは、同じ経路図を使って幅優先探索を具体的に説明しましょう。
幅優先探索の様子を下図に示します。
[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]
（出発点） （２節点） （３節点） （４節点）
図 : 幅優先探索
まず、出発点 A から一つ進んだ経路 (2 節点) を全て求めます。この場合は、[A B] と [A C] の 2 つあり、これを全て記憶しておきます。次に、これらの経路から一つ進めた経路 (3 節点) を全て求めます。経路 [A B] は [A B C] と [A B D] へ進めることができますね。ほかの経路 [A C] も同様に進めて、全ての経路を記憶します。あとはこの作業をゴールに到達するまで繰り返せばいいのです。
上図では、4 節点の経路 [A C E G] でゴールに達していることがわかります。このように幅優先探索では、最初に見つかった経路が最短距離 (または最小手数) となるのです。この性質は、全ての経路を平行に進めていく探索順序から考えれば当然のことといえるでしょう。このことからバックトラックの縦形探索に対して、幅優先探索は「横形探索」と呼ばれます。このあとも探索を繰り返せば全ての経路を求めることができます。
完成までの最小手数を求めるパズルを解く場合、幅優先探索を使ってみるといいでしょう。ただし、探索を進めるにしたがって、記憶しておかなければならないデータの総数が爆発的に増加する、つまりメモリを大量消費することに注意してください。
今回の経路図の場合、メモリを大量消費することはありませんが、問題によってはマシンに搭載されているメモリが不足するため、幅優先探索を実行できない場合もあるでしょう。したがって、幅優先探索を使う場合は、メモリの消費量を抑える工夫も必要になります。
経路の管理はキューを使うと簡単です。幅優先探索でのキューの動作を下図に示します。
(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] ←─┐
│ ─────────────── │
│ │
└─→ キューに経路がある間繰り返す ──┘
図 : 幅優先探索とキューの動作
最初は、(1) のように出発点をキューにセットしておきます。次に、キューから経路を取り出し、(2) のように経路 [A] を一つ進めて、経路 [A B] [A C] を作り、それをキューに追加します。(3) では、経路 [A B] を取り出して、一つ進めた経路 [A B C] と [A B D] をキューに追加します。あとはキューに経路がある間、探索処理を繰り返します。
キューは先入れ先出し (FIFO) の性質を持つデータ構造です。距離の短い経路から順番に処理されるため、幅優先探索として機能するわけです。
それではプログラムを作りましょう。最初に経路を表す構造体 Path を定義します。
リスト : 構造体 Path の定義
typedef struct {
int path[N];
int len;
} Path;
メンバ変数 len が経路長 (訪問した頂点の個数) で、配列 path が経路を表します。
次は Path の操作関数を作ります。
リスト : Path の操作関数
// 現在地点を求める
int top(Path *p)
{
return p->path[p->len - 1];
}
// 経路に頂点が含まれているか
bool visited(Path *p, int x)
{
for (int i = 0; i < p->len; i++) {
if (p->path[i] == x) return true;
}
return false;
}
// 経路の表示
void print_path(Path *p)
{
for (int i = 0; i < p->len; i++)
printf("%c ", 'A' + p->path[i] - 1);
printf("\n");
}
関数 top は経路の末尾 (現在地点) から頂点を取り出して返します。関数 visited は引数 x が経路に含まれているか線形探索します。関数 print_path は経路を表示します。
次はキューを作ります。今回はキューをリングバッファで実装しますが、プログラムを簡単にするためキューの本体は外部変数に定義します。
リスト ; キューと操作関数の定義
#define Q 64
Path buff[Q];
int front, rear;
// 初期化
void init_queue(int start)
{
buff[0].path[0] = start;
buff[0].len = 1;
rear = 1;
}
// データの取り出し
Path *deq(void)
{
return &buff[front++];
}
// データの追加
void enq(Path *p, int x)
{
buff[rear] = *p;
buff[rear].path[p->len] = x;
buff[rear++].len++;
}
// キューは空か
bool is_empty(void)
{
return front == rear;
}
配列 buff に経路 Path を格納します。これがキューの本体になります。キューの大きさ Q はデータ溢れが起こらないように設定します。関数 init_queue は buff[0] に出発点 start をセットします。関数 deq はキューから Path を取り出して返します。関数 enq は引数の経路 p を buff[rear] にコピーして、そこに頂点 x を追加します。構造体 Path のメンバ変数には配列が含まれていますが、buff[rear] = *p で値をコピーすることができます。
簡単な例を示しましょう。
リスト : 構造体のコピー (test.c)
#include <stdio.h>
typedef struct {
int buff[8];
} Foo;
int main(void)
{
Foo a;
for (int i = 0; i < 8; i++) a.buff[i] = i;
Foo b = a;
for (int i = 0; i < 8; i++) printf("%d\n", b.buff[i]);
return 0;
}
$ clang test.c $ ./a.out 0 1 2 3 4 5 6 7
最後に、幅優先探索を行う関数 bfs を作ります。
リスト : 幅優先探索
void bfs(int start, int goal)
{
init_queue(start);
while (!is_empty()) {
Path *p = deq();
int x = top(p);
if (x == goal) {
print_path(p);
} else {
for (int i = 0; i < M; i++) {
int y = adjacent[x][i];
if (y == 0) break;
if (!visited(p, y)) enq(p, y);
}
}
}
}
最初に init_queue でスタート地点を格納した経路をキューに追加します。あとは、キューに経路がある間、while ループで探索を行います。キューから経路を取り出して変数 p にセットします。そして、top(p) で現在位置を求め、それを変数 x にセットします。x が goal と等しければ print_path で経路を表示します。そうでなければ、経路を一つ進めます。頂点 y が経路 p に含まれていなければ、p に y を追加した経路を enq でキューに追加します。これで全ての経路を求めることができます。
それでは、実際に実行してみましょう。
リスト : 幅優先探索 (sample1601.c)
int main(void)
{
bfs(A, G);
return 0;
}
$ clang sample1601.c $ ./a.out A C E G A B C E G A B D E G A C B D E G
結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる経路が最長となります。当然ですが、経路の総数は 4 通りとなります。
幅優先探索は最短手数を求めるのに適したアルゴリズムですが、生成する局面数が多くなると大量のメモリを必要とします。このため、メモリが不足するときは、幅優先探索を使うことができません。深さ優先探索の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らないという問題点があります。
それでは、大量のメモリを使わずに最短手数を求める方法はないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限値を設定し、解が見つかるまで上限値を段階的に増やしていく、という方法です。
たとえば、1 手で解が見つからない場合は、2 手までを探索し、それでも見つからない場合は 3 手までを探索する、というように制限値を 1 手ずつ増やしていくわけです。このアルゴリズムを「反復深化 (iterative deeping)」といいます。
反復深化は最短手数を求めることができるアルゴリズムですが、幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。ただし、同じ探索を何度も繰り返すため実行時間が増大するという欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。
それでは、同じ経路図を使って反復深化を具体的に説明しましょう。反復深化のプログラムはとても簡単です。設定した上限値まで深さ優先探索を行う関数を作り、上限値を１手ずつ増やしてその関数を呼び出せばいいのです。プログラムは次のようになります。
リスト : 反復深化
// 反復深化
void dfs(int n, int goal, int limit)
{
int x = path[n - 1];
if (limit == n) {
if (x == goal) print_path(n);
} else {
for (int i = 0; i < M; i++) {
int y = adjacent[x][i];
if (y == 0) break;
if (!visited[y]) {
path[n] = y;
visited[y] = true;
dfs(n + 1, goal, limit);
visited[y] = false;
}
}
}
}
void ids(int start, int goal)
{
path[0] = start;
visited[start] = true;
for (int limit = 2; limit <= N; limit++) {
printf("---- %d -----\n", limit);
dfs(1, goal, limit);
}
}
関数 dfs の引数 limit が上限値を表します。経路の長さが上限値 limit に達したら探索を打ち切ります。このとき、ゴールに到達したかチェックします。あとは、limit の値を増やしながら dfs を呼び出せばいいわけです。この処理を関数 ids で行っています。
それでは実行結果を示しましょう。
リスト : 反復深化 (sample1602.c)
int main(void)
{
ids(A, G);
return 0;
}
$ clang sample1602.c $ ./a.out ---- 2 ----- ---- 3 ----- ---- 4 ----- A C E G ---- 5 ----- A B C E G A B D E G ---- 6 ----- A C B D E G ---- 7 -----
結果を見ればおわかりのように、最初に見つかる解が最短手数になります。このプログラムでは全ての経路を求めましたが、最短手数を求めるだけでよい場合は、解が見つかった時点で探索を終了すればいいでしょう。
#include <stdio.h>
#include <stdbool.h>
enum {S, A, B, C, D, E, F, G};
#define N 7
#define M 4
// 隣接リスト
int adjacent[N + 1][M] = {
{S},
{B, C, S},
{A, C, D, S},
{A, B, E, S},
{B, E, F, S},
{C, D, G, S},
{D, S},
{E, S},
};
// 経路
int path[N];
bool visited[N + 1];
// 経路の表示
void print_path(int n)
{
for (int i = 0; i < n; i++)
printf("%c ", 'A' + path[i] - 1);
printf("\n");
}
// 深さ優先探索
void dfs(int n, int goal)
{
int x = path[n - 1];
if (x == goal) {
print_path(n);
} else {
for (int i = 0; i < M; i++) {
int y = adjacent[x][i];
if (y == 0) break;
if (!visited[y]) {
path[n] = y;
visited[y] = true;
dfs(n + 1, goal);
visited[y] = false;
}
}
}
}
int main(void)
{
path[0] = A;
visited[A] = true;
dfs(1, G);
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
enum {S = 0, A, B, C, D, E, F, G};
#define N 7
#define M 4
// 隣接リスト
int adjacent[N + 1][M] = {
{S},
{B, C, S},
{A, C, D, S},
{A, B, E, S},
{B, E, F, S},
{C, D, G, S},
{D, S},
{E, S},
};
// 経路
typedef struct {
int path[N];
int len;
} Path;
// 現在地点を求める
int top(Path *p)
{
return p->path[p->len - 1];
}
// 経路に頂点が含まれているか
bool visited(Path *p, int x)
{
for (int i = 0; i < p->len; i++) {
if (p->path[i] == x) return true;
}
return false;
}
// 経路の表示
void print_path(Path *p)
{
for (int i = 0; i < p->len; i++)
printf("%c ", 'A' + p->path[i] - 1);
printf("\n");
}
// キュー
#define Q 64
Path buff[Q];
int front, rear;
// 初期化
void init_queue(int start)
{
buff[0].path[0] = start;
buff[0].len = 1;
rear = 1;
}
// データの取り出し
Path *deq(void)
{
return &buff[front++];
}
// データの追加
void enq(Path *p, int x)
{
buff[rear] = *p;
buff[rear].path[p->len] = x;
buff[rear++].len++;
}
// キューは空か
bool is_empty(void)
{
return front == rear;
}
// 幅優先探索
void bfs(int start, int goal)
{
init_queue(start);
while (!is_empty()) {
Path *p = deq();
int x = top(p);
if (x == goal) {
print_path(p);
} else {
for (int i = 0; i < M; i++) {
int y = adjacent[x][i];
if (y == 0) break;
if (!visited(p, y)) enq(p, y);
}
}
}
}
int main(void)
{
bfs(A, G);
return 0;
}
#include <stdio.h>
#include <stdbool.h>
enum {S, A, B, C, D, E, F, G};
#define N 7
#define M 4
// 隣接リスト
int adjacent[N + 1][M] = {
{S},
{B, C, S},
{A, C, D, S},
{A, B, E, S},
{B, E, F, S},
{C, D, G, S},
{D, S},
{E, S},
};
// 経路
int path[N];
bool visited[N + 1];
// 経路の表示
void print_path(int n)
{
for (int i = 0; i < n; i++)
printf("%c ", 'A' + path[i] - 1);
printf("\n");
}
// 反復深化
void dfs(int n, int goal, int limit)
{
int x = path[n - 1];
if (limit == n) {
if (x == goal) print_path(n);
} else {
for (int i = 0; i < M; i++) {
int y = adjacent[x][i];
if (y == 0) break;
if (!visited[y]) {
path[n] = y;
visited[y] = true;
dfs(n + 1, goal, limit);
visited[y] = false;
}
}
}
}
void ids(int start, int goal)
{
path[0] = start;
visited[start] = true;
for (int limit = 2; limit <= N; limit++) {
printf("---- %d -----\n", limit);
dfs(1, goal, limit);
}
}
int main(void)
{
ids(A, G);
return 0;
}