)
| [Japanese version] | [English version] |
| [一時的なミラーページ (高速 !)] | [オリジナルページ (最新 ?!)] |
地図の彩色問題は地図の領域を，となりあう領域がことなる色になるように， あらかじめきめられた数の色でぬりわける 制約充足問題 です．グラフ頂点の彩色も， 同様にグラフの頂点を辺でむすばれた頂点がことなる色になるように，あらか じめきめられた数の色でぬりわける制約充足問題です．制約充足 問題のおおくは効率のよい解法がしられていない NP 困難 (NP-hard) な 問題に属しますが，地図やグラフのぬりわけ問題もそのひとつです． 地図はそれと等価なグラフに 変換することができるので，これらの問題はおなじやりかたでとくことができ ます．ここではデモに適した平面地図のぬりわけをとりあげます．すべての 平面地図は，よく知られているように，4 色でぬりわけられることが証明されて います．
下記のアプレットは，初期状態のままでは動作がある程度目でおえるかたちで米国 本土の地図の 4 色ぬりわけのひとつの解をもとめます．(このアプレットが おおきすぎるときはこのちいさいアプレット をつかえばよいし，ちいさすぎるときはこの おおきいアプレットをつかえばよい.) アプレット上で，初期状態では ``Medium speed (20 rps)'' となっているオプションを ``Full speed'' に変更すれば最高速で 計算できます．(20 rps とは 1 秒間に 20 回 規則を適用する (rps = reductions per second) という意味．ただし， このアプレットにおいては 20 回よりすくなくなる.) ``Restart'' ボタンをおすことによって再度スタートさせることが できます．乱数をつかっているので，そのたびごとにことなる解がもとめられ ますし，計算時間もばらつきます．
[Java アプレットがみえない (実行できない) とき…]
``Variable catalyst rule'' とかかれたオプションを変更すると，使用する プロダクション規則を変更することができます．その詳細は 文献 [1]にかかれていますが， かんたんにいうと，``Single catalyst rule'' はよりせまい範囲の データをみる (つまり局所的な) ので解がもとまるまでの反応回数 (規則の適用回数) がおおくなるのに対して， ``Variable catalyst rule'' はよりひろい範囲のデータをみる (つまり非局所的な) ので解がもとまるまでの反応回数が すくなくなるということです．もっとも局所的な規則である ``No catalyst rule'' をつかうと，計算は停止しなくなります． (この規則と ``Full speed'' をあわせて選択すると計算をとめることが むずかしくなるので，このくみあわせは禁止しています.)
非局所的な規則をつかってうまく 解をもとめるには，シミュレーテッド・アニーリング (SA) に類似した方法をつかう 必要がでてきます．うえのアプレットでは，SA に類似しているが局所的な 情報だけをつかうフラストレーション蓄積法 (FAM) (文献 [1] または [2]) という方法を つかっています．``Frustration OFF'' (FAM をつかわない) という オプションを選択すると，``Variable catalyst rule'' のばあいには 解をもとめるのに失敗する (停止しなくなったり，解に到達せずに停止する) 確率がたかくなることがためせます (それでも，この問題のばあいには 解に到達せずに停止する確率はひくい)．計算が停止したときに解がもとめ られていれば ``MOD = 1'' と表示されますが，この値が 1 よりちいさいときは 解がもとまらないまま停止したことを意味します．
CCM にもとづく彩色の方法に興味があれば，
計算方法のページを参照してください．
(ここでも説明のためにアプレットを使用しています.
)
上記のアプレットで使用している地図座標の値は，1992 年に当時東大の学生だった 佐藤 譲 君 が手入力してくれたものです．感謝します．
注意事項などについては例題 ホームページの「参考文献など」を参照してください．
なお，上記のアプレットの原始プログラムは ここにあります．ただし，このアプレットはローディングの時間を短縮するために オブジェクト指向プログラミングとしては最低のものになっています． つまり，すべてがひとつのクラスのなかにつめこまれています．