2008年10月20日

四色問題

こんにちは、ナカムラです。

四色問題というものをご存じでしょうか?
現在公開中のある映画で、キーワードの1つとして説明されているので、ご存じの方もおられるとは思いますが、簡単に説明してみます。

四色問題とは、数学界の中で提示された、難解な証明問題です。

「どんな地図も、四色で塗り分けることが可能である」という命題が正しいかどうかを検証する問題なのですが、この場合の地図とは実在の地図とは限らず、架空のものも含みますので、その境界線には無限のバリエーションがあります。

20081020_4color.png


実はこの命題、既に正しいことが証明されています。
ただ、その証明方法がいささか力業なので、人によっては「美しくない」と言う人もいます。


領域を分ける線(地図でいう国境線)のパターンには限りがあることを証明し(それでも100パターン以上!)、その全てが4色で塗り分け可能であることを、コンピュータを使って全て実際に塗ってみたアート


という証明方法です。
「コンピュータを使って実際に全パターンを試す」
という点が、力業で美しくないと言われる要因だと思いますが、ゲームプログラミングでは似たようなこと、結構やります。
膨大な作業を繰り返すというのは、コンピュータの得意技手(チョキ)ですからね。


例えばゲーム中頻繁に行われる当たり判定にしたって、(最も単純な方法では)総当たりによるチェックをしますから。


もっと単純に、
「数多く存在する点の内、指定した座標vに最も近い点を探す」
という処理ではどうでしょう?
指定された座標vと、全ての点との距離を計算し比較する、といういわゆる総当たりチェックでもいいと思います。
ただし、点の総数がある程度以下の数であるならば。
この方法ですと、点の総数に比例して検索時間が長くなってしまいますので、点の数が膨大な状況では、あまり得策ではありません。

点の存在する領域をある程度区分けしておき、予めどの点がどの領域に所属するのかを判定しておく。
こういう前準備を行っておけば、実際の検索に費やす時間は短く済みます。
どの領域に点が存在するのかを特定できれば、あとはその領域内の点に限定して検索すれば済みます。

20081020_box.png


この考え方を極限まで推し進めたのが、ボロノイ図という図を用いた手法です。
点1つ1つの「縄張り」を予め計算しておくことで、領域さえ特定すれば最近点が得られるという方法です。
実際のゲームでは、ここまで厳密に縄張りを計算することは(今のところ)無いと思います。

http://ja.wikipedia.org/wiki/%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3

このボロノイ図とは、計算幾何学という学問で使われる概念です。
計算幾何学とは、図形に関する処理をコンピュータで解決する上で、最も効率的な方法を探し出す学問で、1970年代頃に生まれた比較的新しい学問です。

ハードウェアの進化と共に扱うデータ量が飛躍的に増えグッド(上向き矢印)、またその精密さも問われる傾向が強くなってきてますから、今後のゲームプログラムには必要になってくるかもしれませんね。

posted by 管理人 at 10:57 | Comment(2) | 研究・開発
この記事へのコメント
更に考えてみましたので、感想をお寄せください。4色問題とは、平面球面上のあらゆる図形は、4色で塗り分けられるかと言う問題です。5面のみで5色を必要とする図形は以前説明した通り、5面が残り4面にそれぞれ接する必要があります。4本足蛸(頭と4本足で5面)の4本の足を、平面上で残り3本の足に接触することは出来ません。蛸がボールを抱えた状態でも出来ません。即ち球面上でも出来ません。ドーナッツ上の面には描く事が出来ます。(横ドーナッツの面を縦に3等分し、内一面を横に3等分した形・横ドーナッツの面を横に3等分し、内一面を縦に3等分した形)それでは、4色以下が必要な図形同士を組み合わせ、5色目を必要とする図形が出来るでしょうか。4色必要な図形とは、4面が残りの3面に接している形か、1面の周囲を奇数面が取り巻いている形です。前者は3分割ドーナッツです。後者は5以上の奇数分割ドーナッツです。後者は、周囲の面を2色で順に塗った時、最初と最後が同色になるので4色目が必要です。3分割ドーナッツTの周囲をABCの3面とし、穴をDとします。別のドーナッツUの周囲をXYZの3面とし、穴をWとします。T及びUのドーナッツは接触していない場合、それぞれ4×3×2×1=24通りの塗り方があります。可能な限り面同士を接触させた場合、何通りになるでしょうか。ABCをXに接します。Bは完全に囲まれるのでAC2面しかYに接触出来ません。ZはC一面としか接触出来ません。XはABC3色と接する為、その3色の可能性は無くなります。4-3でAはD1色になります。YはAC2色と接している為3-2でB1色です。ZはCと接しているので2-1でA1色です。WはABCDと接しないので1-0でC1色になります。その状態で今度は、XYZをCに、XYをAに、XをBに接します。するとCは3色と接する為4-3で1色になります。Aは2色と接触するため3-2で1色になります。Bは1色と接触する為1色になります。Wはいずれの色とも接触しないので、残りの1色に決まります。(○を縦棒で2分割し半円の中に○を2つ書き、○から縦棒に向かって3本の線を左右それぞれ工夫して描くことで可能です。)ドーナッツT・Uの8面の色は一組に限定されました。一つの3分割ドーナッツは他の3分割ドーナッツの1面から3色を奪い、もう1面から2色を奪い、更に1面から1色を奪い塗り方を1通りに限定します。3つの3分割ドーナッツは最大でも、3つの3分割ドーナッツの色の塗り方を1つに限定するのみです。4つなら4つです。幾ら数を増やしても、この計算では最低でも1通りで塗れます。但し3つ以上の場合は、3色奪った面と2色奪った面と1色奪った面の接触が切れてしまうので、塗り方はもっと多くなります。奇数個に分割したドーナッツを、3分割ドーナッツUに接触させます。7分割したドーナッツの例で説明すると、7面全てとXを接し、残り2面とYを接し、残り1面をZと接しないと、3色をXに、2色をYに、1色をZに接触させることは出来ません。第3色目は周囲の7つの何処でも良いからです。従って、性質は3分割ドーナッツと全く同じです。次に3色を必要とする図形です。これは、2分割ドーナッツです。周囲をアイの2面、穴をウとします。これをドーナッツUに接触させます。アイをXに、更にアイをY面に、Zはアに接触させます。塗り方は(4-2)×(3-2)×(2-1)×1=2通りあります。2色必要とする図形◎をドーナッツUに接触させた場合、(4-1)×(3-1)×(2-1)×1=6通りあります。5色目が必要なのは、0通りとなる時です。それは@黄赤青白4面を1面に接触させると、5色目の黒を必要とする。A黄赤青3面が1面に接触する形が2つあり、接触された2面が接触すると白と黒を必要とする。B黄赤2面が1面に接触する形が3つあり、接触された3面がY字状に接すると青白と黒を必要とする。C黄1面が1面に接する形が4つあり、接触された4面がそれぞれ他の3面と接触すると赤青白と黒を必要とする場合の4通りです。3分割ドーナッツの周囲の面は3色なので@は不可能です。Aの3面をそれぞれ2面に付けるのも不可能です。Bの同じ面2つを3面にそれぞれ接触させることは出来ません。Cは4本足の蛸の例からしても不可能です。3分割ドーナッツは以上4通りあるいずれの要件も満たしません。全ての図形は1から複数に分割されたドーナッツを組み合わせて接触させ、穴を無くし(性質は同じです)、線を伸縮曲げ伸ばしして加工することで描けます。平面を球面にするには、平面上の図形の周囲にある無限に広がる面を収縮させ一面とすれば、球面になります。そうしても性質は変わりません。以上の説明の通り、平面上及び球面上で4色以下で塗り分けられる図形を幾ら組み合わせても、5色目を必要としません。5面で5色を必要とする図形もありません。従って、全ての平面上及び球面上の図形は4色で塗り分けられると言えます。
Posted by catbird at 2010年01月09日 06:38
コメントありがとうございます。
非常に熱心に取り組んでおられることが伝わってきました。
これからも、ヘキサドライブ日記をよろしくお願いします。
Posted by ヘキサドライブ ナカムラ at 2010年01月12日 11:48
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
※ブログオーナーが承認したコメントのみ表示されます。