最近 Windows 上で動作し、フリーで利用できる開発環境が増えてきています。Perl や Tcl/Tk といった海外で開発されたスクリプト言語だけではなく、日本で生まれたスクリプト言語である Ruby や HSP などが注目を集めています。Ruby は、まつもとひろゆき氏が開発したオブジェクト指向スクリプト言語で、HSP (Hot Soup Processor) は onion software (onitama 氏) が開発した BASIC に似たスクリプト言語です。このようにフリーで利用できる開発環境が増えると、自分の好みに合った言語を選ぶことができるので、昔に比べると Windows 上でも気軽にプログラミングを楽しめる環境が整ってきているように思います。
さて、プログラミングを楽しむにしても、それでは何を作ろうかと悩む方もいるでしょう。このような人にぴったりの題材が「パズルの解法」です。パズルを解くという明確な目標があり、そして何よりも実際にパズルを解いたときの喜びは大きく、プログラムを作る意欲をかき立ててくれます。では、どうやったらパズルを解くことができるのでしょう。また、パズルに限らず、教科書の例題は理解できても、そこから一歩でもはずれると、どうやってプログラムを作ったらよいのかわからない、という方もいると思います。
プログラミングの上達の秘訣は、実際にプログラムを作って動作を確認することです。このとき、プログラミング言語の文法を覚えることも必要ですが、それだけでは簡単なプログラムしか作ることができません。特に、最近の優秀なツールを使えば、部品を配置するだけで簡単にインタフェイスを作ることができます。ところが、見栄えがよくても中身がしっかりしていないと満足のいくアプリケーションにはなりません。
ここで重要なのが「アルゴリズム」です。アルゴリズムとは、ある問題を解く手順のことを意味し、この手順を特定のプログラミング言語で記述したものが、実際のプログラムとなります。プログラミング言語の文法を理解したとしても、アルゴリズムがわからないのではプログラムを作ることはできませんね。そして、もうひとつ重要なのが「データ構造」です。データ構造とは、データの表現方法のことですが、アルゴリズムがわかっていてもデータ構造の選択が間違っていると、処理に時間がかかりすぎて現実的な時間で答えを求めることができないということもあるのです。
特にパズルを解く場合、アルゴリズムとデータ構造の選択は重要です。パズルによっては、初めから巧妙な解法を思いつく人もいるのですが、筆者のような凡人に、天才的なひらめきを期待するのは無理というものです。しかしながら、基本的なアルゴリズムとデータ構造を使うことで、ベストではありませんが、そこそこのプログラムを作ることは可能です。
コンピュータ科学の歴史は半世紀ちょっとしかありませんが、いままでに数多くの優れたアルゴリズムやデータ構造が考案されています。たとえば、データの整列 (sort) にはクイックソートやマージソートなど、データの探索 (search) にはハッシュ法や二分探索木などがあり、ほかの分野にもさまざまな優れたアルゴリズムが知られています。これらをうまく使いこなすことができれば、あなたのプログラミングスキルもレベルアップすることは間違いありません。そして、このようなアルゴリズムを理解するのに適しているのが、パズルの解法なのです。つまり、
というわけです。使用するプログラミング言語はＣ言語としますが、アルゴリズムやデータ構造は、プログラミング言語に依存するものではありません。ほかの言語へ移植するのもプログラムの勉強になるでしょう。
さて、前置きが長くなりましたが、そろそろ本題に入りましょう。今回はパズルの解法で基本となるアルゴリズム「バックトラック」を説明します。
ところで、アルゴリズムとかパズルの解法というと、避けては通れないのが「再帰呼び出し」です。再帰呼び出しとは、関数定義の中で自分自身を呼び出すことです。簡単な例題として、階乗を計算する関数を考えてみましょう。階乗は次のように定義することができます。
n! の定義に (n - 1)! が使われていますね。このように、階乗は自分自身を使って再帰的に定義されています。つまり、n! を求めるためには (n - 1)! を計算すればいいわけです。そして、(n - 1)! を求めるためには (n - 2)! を計算し、(n - 2)! を求めるため (n - 3)! を計算する、というように最後には 0! を求めることになります。これは階乗の定義から 1 であることがわかります。結局 n! を求めるには、1 から n までの整数を乗算すればいいのですが、再帰呼び出しを使うと階乗の定義そのままにプログラムすることができます。
リスト：階乗の計算
int fact( int n )
{
if( n == 0 ){
return 1;
} else {
return n * fact(n - 1);
}
}
関数 fact は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出していますね。これが再帰呼び出しです。
関数定義の中で自分自身を呼び出すことができるなんて、何か特別な仕掛けがあるのではないか、と思ってしまうかもしれませんね。筆者も最初に再帰呼び出しを見たときは、関数を定義するのに自分自身を呼び出すなんて、ヘビが自分の尻尾を食べていくような奇妙な感覚に思えて、なかなか理解できませんでした。ところが、再帰呼び出しは特別なことではなく、近代的なプログラミング言語であれば、ほぼどれも再帰呼び出しを使うことができるのです。
階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムすることができますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換するとプログラムが複雑になってしまうものがあります。このような場合は、素直に再帰呼び出しを使ってプログラミングした方がわかりやすいプログラムとなり、間違いを犯す（バグを生み出す）危険性が少なくなります。難しいアルゴリズムでも、再帰呼び出しを使うと簡単にプログラムできる場合もあるのです。
一般に、再帰呼び出しは難しいテクニックと思われているようで、初心者の方は避けて通ることが多いように思います。ところが Lisp というプログラミング言語では、再帰呼び出しは初心者が覚えるべき基本テクニックのひとつに過ぎません。慣れるまでちょっと苦労するかもしれませんが、基本を理解すれば簡単に使いこなすことができるようになります。プログラミングに興味をお持ちの方は、ぜひ再帰呼び出しをマスターしてください。
それでは、再帰呼び出しのポイントを説明しましょう。図 1 を見てください。
Call:1 --> Call:2 --> Call:3 --> Call:4 --> Call:5
n:4 n:3 n:2 n:1 n:0
value 24 <-- value : 6 <-- value : 2 <-- value : 1 <-- value : 1
図 1 : fact の再帰呼び出し（n:引数の値, value:返り値）
図 1 は関数 fact(4) の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact を再帰呼び出しします。2 回目の呼び出しでは、引数 n の値に 3 が代入されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。
関数の引数は局所変数として扱われます。局所変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されているあいだだけ有効です。局所変数は、関数呼び出しが行われるたびに新しいメモリに割り当てられ、そこに値が代入されます。そして、関数の実行が終了すると、局所変数用に割り当てられたメモリは解放されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n に割り当てられるメモリが異なっているのです。ここが再帰呼び出しを理解するポイントのひとつです。
プログラムを見ると変数 n はひとつしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact(4) を実行しているときの n は 4 であり、fact(3) を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を代入するのです。現在のプログラミング言語では、局所変数はあって当然の機能です。再帰呼び出しを使いこなすためにも、局所変数の有効範囲はきちんと理解しておきましょう。
同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。ここが第 2 のポイントです。
停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Ｃ言語であればプログラムは暴走することになります。再帰呼び出しを使う場合は、この停止条件に十分注意してください。慣れないうちは、図を描いてみるのもいいでしょう。
fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行しているあいだ、引数 n の値は 1 ですね。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って計算し、最後に fact(4) の値 24 を求めることができるのです。関数 fact は自分自身を 1 回だけ呼び出しています。これを一重再帰と呼びます。このような再帰呼び出しは、繰り返しへ簡単に変換することができます。
もうひとつ簡単な数値計算の例を示しましょう。フィボナッチ関数も再帰的に定義される関数です。
フィボナッチ関数も再帰呼び出しを使えば簡単にプログラムできます。
リスト : フィボナッチ関数
int fibonacci( int n )
{
if( n == 0 || n == 1 ){
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
fibonacci は fact とは違い、自分自身を 2 回呼び出しています。このことを二重再帰といいます。fibonacci の呼び出しをトレースすると図 2 のようになります。
f(5) ┬ f(4) ┬ f(3) ┬ f(2) ┬ f(1)
│ │ │ │
│ │ │ └ f(0)
│ │ └ f(1)
│ └ f(2) ┬ f(1)
│ │
│ └ f(0)
│
└ f(3) ┬ f(2) ┬ f(1)
│ │
│ └ f(0)
└ f(1)
図 2 : fibonacci のトレース
同じ値を何回も求めているため、効率はとても悪いのです。この処理は、配列を使うと高速化することができます。何度も同じ計算をしないように、計算した値は配列に格納しておいて、2 回目以降は配列から計算結果を求めるようにします。また、フィボナッチ関数の値は、整数 (int) の範囲では高々 45 までしか求めることができません。あらかじめ 0 から 45 までの値を計算して配列に格納しておけば、もっと簡単に値を求めることができます。このような方法を「表引き」とか「表計算法」といいます。アルゴリズムによっては、表計算法を使うことで処理を劇的に高速化することができます。もちろん、パズルの解法にも応用することができますが、今回の主題である再帰呼び出しとバックトラックから脱線するので、この辺で話を打ち切ります。今後の楽しみにとっておきましょう。
次は「バックトラック(backtrack)」というアルゴリズムを説明します。バックトラックは、パズルの解法でよく使われる、王道というべきアルゴリズムです。たとえば、迷路を考えてみましょう。ある地点 A で道が左右に分かれていたとします。左の道を選んで先へ進むと、行き止まりになってしまいました。この場合、A 地点まで戻り右の道へ進まなければいけません。このように、失敗したら後戻りして別の選択肢を選び直す、という試行錯誤を繰り返してゴールにたどり着く方法がバックトラックなのです。バックトラックはパズルの解法だけではなく、いろいろな分野の問題に応用できるアルゴリズムです。そして、再帰呼び出しを使うと簡単にプログラムすることができます。
それでは、図 3 に示す簡単な経路図を使って、具体的にバックトラックを説明します。
Ｂ------Ｄ------Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ------Ｅ------Ｇ
図 3 : 経路図
点とそれを接続する線からなる図形を「グラフ (graph) 」といいます。点のことを「頂点 (vertex) 」とか「節 (node) 」と呼び、線のことを「辺 (edge) 」とか「弧 (arc) 」と呼びます。グラフには 2 種類あって、辺に向きがないものを「無向グラフ」といい、向きがあるものを「有向グラフ」といいます。有向グラフは一方通行の道と考えるとわかりやすいでしょう。図 3 ではアルファベットで頂点を表しています。今回は経路をグラフで表していますが、このほかにもいろいろな問題をグラフで表現することができます。
グラフをプログラムする場合、よく使われる方法が「隣接行列」と「隣接リスト」です。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行列で表すことができます。図 3 を隣接行列で表すと、図 4 のようになります。
| 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 図 4 : 隣接行列
A に接続している頂点は B と C なので、A 行の B と C に 1 をセットし、接続していない頂点には 0 をセットします。経路が一方通行ではない無向グラフの場合は、A 列の B と C にも 1 がセットされます。これをＣ言語でプログラムすると、次のようになります。
リスト : 隣接行列
#define N 7
char 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 次元配列 adjacent で表します。内容は図 4 の隣接行列と同じです。
隣接行列の欠点は、辺の数が少ない場合でも 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] 図 5 : 隣接リスト
図 5 は、頂点とそこに接続されている頂点を => と [ ] で表しています。この表記法は正式なものではなく、Perl のハッシュから拝借したものです。これをＣ言語で表すと、次のようになります。
リスト : 隣接リスト
const char adjacent[N][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 */
};
隣接行列と同様に、頂点 A から G を数値 0 から 6 に対応させます。-1 でデータの終端を表しています。ところで、隣接リストにも欠点があります。たとえば、E と G が接続しているか調べるには、データを順番に調べていくしか方法がありません。このため、接続の判定に時間がかかることがあるのです。まあ、頂点に接続されている辺の数が少なければ、処理速度が極端に遅くなることはないでしょう。
今回は隣接リストを使って、A から G までの経路をバックトラックで求めます。バックトラックを再帰呼び出しで実現する場合、経路を「進む」ことを再帰呼び出しに対応させるのがポイントです。経路を探索する関数を search としましょう。search は引数として現在地点の頂点を受け取ることにします。最初は search(A) と呼び出します。そして、A から B へ進むには search(B) と呼び出します。これで B へ進むことができます。それでは、A に戻るにはどうしたらいいのでしょう。search(B) は search(A) から呼び出されたので、search(B) の実行を終了すれば、呼び出し元である search(A) に戻ることができます。つまり、関数の実行を終了すれば、ひとつ手前の地点にバックトラックできるのです。このように再帰呼び出しを使うと、進むことと戻ることを関数呼び出しで簡単に実現することができます。
それでは具体的に説明します。経路は配列 path に頂点を格納して表すことにします。経路の探索を行う関数 search は、次のように定義します。
void search( int len, int node, int goal );
引数 len は経路長、node は現在地点、goal はゴールを表します。search は node に隣接している頂点をひとつ選び、経路を進めていきます。A から Gまでの経路を求めるには、次のように呼び出します。
/* A から G までの経路を求める */ search( 0, 0, 6 );
search は path[0] に A をセットし、A に接続されている頂点を選びます。隣接リストから順番に選ぶことにすると、次の頂点は B となります。B へ進むためには、次のように search を再帰呼び出しします。
/* B へ進む時の再帰呼び出し */ search( 1, 1, 6 );
経路長 len に 1 を加算することを忘れないでください。この関数の実行を終了すると、呼び出し元の関数である頂点 A の処理に戻ります。プログラムは次のようになります。
リスト : 経路の探索
void search( int len, int node, int goal )
{
path[len] = node;
if( node == goal ){
print_path( len );
} else {
int n, i;
for( i = 0; (n = adjacent[node][i]) != -1; i++ ){
if( memchr( path, n, len ) == NULL ){
search( len + 1, n, goal );
}
}
}
}
最初に現在地点を path に格納します。配列 path は大域変数として定義します。次に、ゴールしたかチェックします。これが再帰呼び出しの停止条件になります。ゴールしたら print_path で経路を表示します。ここで探索を終了することもできますが、バックトラックすることですべての経路を見つけることができます。パズルを解く場合、解の総数を求めることが多いので、すべての解をもれなく探索する必要があります。バックトラックを使えば、このような要求も満たすことができます。
ゴールしていない場合、隣接リストから次の頂点を選びます。隣接リストから順番に頂点を取り出して、変数 n にセットします。このとき、経路に含まれている頂点を選んではいけません。そうしないと、同じ道をぐるぐると回る巡回経路が発生し、ゴールまでたどり着くことができなくなります。標準ライブラリ関数 memchr で path 内に頂点 n がないことを確認し、search を再帰呼び出しします。
バックトラックしたときは、同じ経路を進まないために、違う頂点を選ぶことに注意してください。変数 i は局所変数なので、関数が実行されている間だけ有効です。たとえば、i が 0 のときに再帰呼び出しが行われてバックトラックしてきても、i の値は 0 のままです。それから、for 文の更新式 i++ によって i の値が 1 となり、隣接リストから次の頂点が取り出されます。つまり、局所変数の働きにより、バックトラックしても同じ頂点が選択されることはないのです。ここでも局所変数が役に立っているわけです。
実行結果は次のようになります。
A B C E G A B D E G A C B D E G A C E G
4 通りの経路を見つけることができました。バックトラックによる探索は、経路を先へ先へ進めるので、「縦形探索」とか「深さ優先探索」と呼ばれています。このため、結果を見てもわかるように、最初に見つかる経路が最短経路とは限りません。最短経路を求めるのに適したアルゴリズムが「幅優先探索」です。これは次回（第 2 回）で詳しく説明しましょう。
/*
* keiro.c : 経路の探索
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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 */
};
/* 経路 */
char path[NODE];
/* 経路の表示 */
void print_path( int len )
{
int i;
for( i = 0; i <= len; i++ ){
printf("%c ", path[i] + 'A' );
}
printf("\n");
}
/* 経路の探索 */
void search( int len, int node, int goal )
{
path[len] = node;
if( node == goal ){
/* 到達した */
print_path( len );
} else {
int n, i;
for( i = 0; (n = adjacent[node][i]) != -1; i++ ){
if( memchr( path, n, len ) == NULL ){
search( len + 1, n, goal );
}
}
}
}
int main()
{
/* A -> G */
search( 0, 0, 6 );
return 0;
}