|
|
ときは1852年，英国London大学教授だったAugustus de Morganは，学生のFrederich Guthrieから質問された問題に悩んでいました。その問題とは「平面に描かれた地図の各国を，隣接する国とは別の色で塗り分ける場合，4色あれば十分であるか」というものでした。de Morganはこれを数学界の新しい命題だと考え，数学者として著名だったアイルランドDublin王立協会会長のWilliam Rowan Hamiltonに手紙を出したそうです。これが「4色問題」の誕生でした。
この問題は数学者達の心を捉え，多くの人が挑戦しました。3色では不十分だし5色なら塗り分けられるのがすぐわかりましたが，「4色だけですべての地図を塗り分けられるのかどうか」は，なかなか証明できませんでした。フェルマーの最終定理と並ぶ，数学界の難問とされていたのです。
光陰矢のごとし。ときは流れに流れて1976年，米国Illinois大学のKenneth AppelとWolfgang Hakenの2人がこの問題に挑戦しました。彼らはいままでの証明方法とはまったく違い，大型コンピュータを使うことで証明しようとしたのです。実に 1200時間以上かけて，すべての地図をしらみつぶしに探索したところ，すべての国の組み合わせが何千種類かのバリエーションに過ぎないことがわかり，4 色で塗り分けられることを確認しました。
4色問題は，100年以上にわたって人々が考えてきた問題が，コンピュータの助けで解くことができた著名な例です。今回はその浪漫に浸りながら，地図を塗り分けるアルゴリズムを解説します。
図をデータに置き換えて探索する
図形を扱うプログラムを作るときにはまず，プログラムで図形を扱いやすくするためのデータ構造を考えなくてはいけません。この問題の場合，「一つの色を塗るときにそのエリアの周りにある色と同じなら塗らない」「そのエリアにある色は本当に塗ってもいい色なのかを確認する」といった処理が必要になります。そこで「それぞれのエリアが互いにどう隣接しているのか」を示すデータを作ることにします。
こうしたデータにはいろいろな構造が考えられますが，ここでは単純な2次元配列にしてみました。リスト1にあるareapattern配列がそれです。
 |
| リスト1●エリアの隣接状態を定義した配列 [画像のクリックで拡大表示] |
地図上のA～Hの各エリアに番号を振り，それぞれについて隣接するエリアを配列の要素として並べています。リストでは配列の二つ目の添え字の値として6を指定していますが，これはたまたま図1の地図で六つ以上に隣接しているエリアが無かったからです。ほかの地図に適用するときは，一つの国が接している最大のエリア数＋1を二つ目の添え字の値にする必要があります（なぜ1を足すのかは後で説明します）。
 |
| 図1●A～Hの各エリアを隣接するエリアが同じ色にならないように塗り分ける |
この配列を使った場合，例えば，番号3のエリアに隣接するエリアは，area-pattern[3][0]，areapattern[3][1]， areapattern[3][2]…となるわけです。隣接するエリアの個数は各エリアによって異なるため，areapattern配列には「この先にエリアの番号がない」ことを示す「AREA_END」をそれぞれの並びの最後に置いておきます（これが先ほど1を足した理由です）。こうしておけば，カウンタ変数iを0，1，2…と増やしながらareapattern[エリアの番号][i]がAREA_ENDになるまで調べることで，隣接するすべてのエリアの番号を得られます。各エリアに塗った色は，areamapという別の1次元配列に保存しておきます。
リスト2のisusedcolor関数ではこの処理を行い，指定した色がエリアの周囲で使われているかどうかを調べています。この関数は指定した色が隣接したエリアですでに使われているならtrue，そうでなければfalseを返します。
 |
| リスト2●リスト1の配列を使って指定した色が周囲で使用済みかどうかを判別するコード |
行き止まりになったら手順を戻すバックトラック
コンピュータがなかったころ，この問題は手作業で解いていました。手法はこんな具合です。最初はどこかにどの色でもいいので1色を塗ります。次に別のエリアにまた色を塗ります。このとき，隣接するエリアにすでに色が塗ってある場合は，それとは別の色を塗るようにします。その次も同じようにして…と続けていくと，やがてどの色も塗れないエリアが出てくることがあります。その場合は，「一つ前の状態に戻ってそのときに塗ったエリアを別の色に塗り替える」ということをします。もしそれでも塗れなかったら，塗れるまで手順を戻して同じことを繰り返します。
これをそのままアルゴリズムとして採用したのが，本連載の第1回で紹介した「バックトラック」です。バックトラックの処理の流れを図2に示します。仮にエリアの番号順に色を塗っていくとすると，エリア0の塗り方は4色あるので4通り，そのそれぞれについてエリア1の塗り方が最大で4通り…，ということになります。この様子は，各エリアに塗る色の選び方でそれぞれ高々4通りに枝分かれするツリーとして描くことができます。
 |
| 図2●塗り分け処理の探索ツリー。丸で囲んだ数字は，各エリアを塗る色を表す。バックトラックでは，枝に振った青い数字の順に探索を行う |
この図を見れば，バックトラックがツリーをたどりながら正しい塗り方を探す，探索処理の一種であることがおわかりでしょう。バックトラックでは，「行き止まり」にならない限り，ツリーを深いほう，深いほうへと探索していきます。こうした探索方法を「深さ優先探索」や「縦型探索」などと呼ぶこともあります。
再帰処理を使ってバックトラックを実装する
バックトラックの実装には，関数の中で再度自分自身を呼び出す「再帰処理」をよく使います。リスト3がその例です＊1。関数そのものの働きは「エリアと色」を渡すと，「色が塗れなかったらfalse，塗れたらtrue」を返すというものです。そのとき，色が塗れたらそのエリアに色を塗って，次のエリアで塗れる色を探します。この「次のエリアで色が塗れるかどうか」を調べるために，また自分自身を呼び出すのです。
 |
| リスト3●再帰処理を使ってバックトラックを実装したコード |
関数呼び出しから戻ったとき，ローカル変数や引数には呼び出す前の値がそのまま保存されています。C言語では，関数を呼び出すたびにシステム・スタックと呼ばれる領域にメモリーを割り当て，そこにローカル変数や引数の値などを格納する仕組みになっているからです（図3）＊2。このため，再帰呼び出しの中でローカル変数の値が上書きされる心配はありません。
 |
| 図3●システム・スタックにローカル変数や引数の値が格納される様子。関数を呼び出すごとに別の領域に保存される |
colorsearch関数の先頭ではまず，引数colorに指定された色が周囲で使われているかどうかを，isusedcolor関数（リスト2）を使って調べています。指定された色で塗れない場合，colorsearch関数はfalseを返して即座に関数を終了します。
塗れる場合は，
areamap[area] = color;
としてグローバル変数areamapにそのエリアの色を格納した後，次の探索に備えてareaを一つ進め，4色ぶんループします。ここで colorsearch関数自身を再度呼び出しています。もし色を塗れたらtrueが返るので，そこでループを脱出して自身もtrueを返します。どの色も塗れなかったらfalseを返します。
areaを一つ進めたときにエリアの総数（AREA_LIMIT）に達していれば，全部を塗り終えたことになります。その場合は，trueを返して関数を抜けます。
