４色塗り問題
問題
「ある平面のいくつかの区切られた領域を４色のうち１色を割り当て、隣り合わせの領域には同じ色を塗らないようにせよ」という問題です。最低４色あればどんなものでも塗り分けることができるらしいです。数学的には証明はされていないのですが、コンピュータを使っての証明はされています。数学的証明とコンピュータを使った証明とは何が違うのか謎ですが、多くの数学者がチャレンジし、未だに証明されていない難問です。
ニューラル表現
次のような領域を塗り分けてみる。
それぞれの領域に対して、色ニューロンを割り当てます。色ニューロンというのは、赤、黄、緑、青の４色だとし、今それ領域に緑を割り当てたいとすると、緑ニューロンを発火させて、そしてその他の色ニューロンを沈静化させておきます。これで、色の決定ができます。この例では、２０領域ありますから、４×２０のニューロンを用意すればいいことになります。次に領域の隣接しているかしていないかを表すための配列Ｄを用意します。配列Ｄは、（領域数）×（領域数）、つまりこの例では、２０×２０の配列です。形式は、領域Ｘと領域Ｙが隣接していたとすると
Ｄｘｙ＝Ｄｙｘ＝１
隣接していなかったとしたら
Ｄｘｙ＝Ｄｙｘ＝０
とします。また、ＤｘｘとＤｙｙは、便宜的に０とします。こうすると、領域Ｘと領域Ｙとが隣接しているかしていないかはＤｘｙの値を調べればわかるようになります。
動作式
Ｕｘｃつまり領域Ｘの色Ｃのニューロンの動作式を条件通りにたてると、
（赤＝１、黄＝２、緑＝３、青＝４としています）
となります。
第１項は、色ニューロンをただ一つ発火するようにします。色ニューロンが一つも発火していなければ、正の値を取り発火を促し、一つ発火していると０を取り条件の通りに、二つ以上発火していると負の値を取り鎮火の方向へ向かわせます。
第２項は、「隣接領域を同じ色で塗らない」という条件を表している。色Ｃについて領域Ｘに隣接しかつ発火している領域の合計個数です。つまり、この数が０ならば、条件通りであり、一つでもこれに該当する領域があったとすれば、そのニューロンを鎮火の方向へ向かわせます。上でＤｘｘつまりｙ＝ｘのときＤｘｘ＝０としてましたが、ここで便利がいいようにするためです。自分自身を数える必要がないのでＤｘｘ＝０としておけば、自分自身が発火していようがしてまいがカウントされなくなります。
動作式は、これで完璧と思いきや不完全なんです。それはなぜかというと、隣の領域がすべての色を使い切ってしまったら、たちまち動作式は、思い通りに動かなくなります。具体的にいうと、次のような花（？）を考えてみる。
真ん中の領域５は、周りの領域がすべての色を使っているのでどの色も塗ることができません。動作式の値は、第一項は色ニューロンを発火に導いていきますが、第２項は、鎮静を促していきますから結局のところ領域５は、どの色ニューロンも発火しないことになります。こういう状態に陥らないように正規化を行います。隣り合う領域が多い領域から、つまり他の領域への影響力の大きな領域から色を決定するようにします。正規化された動作式は、
となります。定数Ｄと領域の隣接条件のＤを取り違わないように。
第１項は、見ての通り前と同じです。
第２項は、∑Ｄｙｋを掛けることによって、多くの隣り合う領域を持った領域であればあるほど、よりその領域からの抑制を受けるようになります。
第３項は、ヒルクライミングターム項です。ヒルクライミングは、色ニューロンが一つも発火していなければ、発火を促します。後ろに掛けてあるのは、Ｄ∑Ｄｘｋは、領域Ｘの隣り合う個数、Ｅ∑∑ＤｘｙＤｙｋ／∑Ｄｘｋは、領域Ｘの隣接領域の隣接領域の平均個数です。これらの和をヒルクライミングターム項に掛けることによって隣接領域の多い領域つまり影響力の大きな領域から色を決定していくことができます。Ｄ∑Ｄｘｋは、子の数、Ｅ∑∑ＤｘｙＤｙｋ／∑Ｄｘｋは、孫の数といったようなイメージを持ってもらえればわかりやすいのではないかと思います。
大変見た目はわかりにくそうに見えますがじっくり式をおっていってください。
プログラミング
今回は、解がうまく出るようにするのに苦労しました。動作式通りやっても解がなかなか出ませんでした。ＡＢＣＤＥの定数値の調整やメインプロセスなどを工夫しました。具体的にはＡ＝３０、Ｂ＝Ｃ＝Ｄ＝Ｅ＝１に、また、メインプロセスの方では、色ニューロンの動作の順番をランダムに行うなどしました。
隣接条件は、別ファイルから読み込みます。書式は、
20
0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0
1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
1,1,1,0,1,0,1,1,1,1,0,0,0,1,0,0,0,0,0,0
1,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0
1,0,0,0,1,0,0,0,0,0,1,1,1,0,1,0,0,0,1,1
0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0
0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0
0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0
0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0
0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0
0,0,0,0,1,1,1,0,0,1,1,0,1,1,1,1,1,0,0,0
0,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1
0,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,0,0
0,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,1,1,1,1
0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0
0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1
0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1
0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0
のようにはじめに領域数、そのあとに隣接条件を”,”で区切って入れてください。
隣接条件は、斜めに対称なので片側だけの入力にしてもいいのですが、間違いをより防ぐために全部入力する形を取りました。対称でないデータが渡されるとはじくようになってます。
4Color.c ソースファイル
4Color.exe 実行形式ファイル
4C_00.dat 例の隣接条件データ
例の問題の解は、
また、４色でなくてｍ色で塗り分けたいとすれば、動作式を次のように変更するだけでいけます。
今回は、結構骨が折れました。本が結構うそっぱちを連発していたので。