彩色問題とは #
彩色問題とは地図のような平面グラフにおいて、共通の境界線を持つ隣り合った領域が同じ色にならないようにしながら塗り分けるという問題です。たとえば下記は彩色問題を解いた例ですが、各領域は「赤・青・緑・黄」の4色のうちどれかの色をとり、隣り合う領域は別の色になっています。1
平面状の任意の塗りわけ問題は、四色で塗り分け可能なことが証明されています(四色定理2)。しかし、「実際にどのように塗り分けられるのか」、「三色以下で塗り分けが可能か」についてはとても難しい問題として知られています。ここでは彩色問題について、領域が取り得る色の組合せを最適化するという方針によりアニーリングマシンを用いて解いてみます。
例題: 日本地図 #
例題として最初に日本の地図の関東地方に着目して、四色で塗り分けることを考えます。3
関東地方には都道府県が7つ存在します。そのため、取り得る組合せの数は \(4^7\) あります。
コスト関数の作成 #
アニーリングマシンではイジング模型の形で入力を受け付けます。そのため、今回の彩色問題をどのようにしてイジング模型で表すかを考えていきます。
最初に、各領域が取り得る色を表す変数を用意する必要があります。最もシンプルな方法として、ある色で塗られているかどうかを表すビットを用意し、その色で塗られている場合には \(1\) 、そうでない場合は \(0\) をとることにします。よって四色で塗り分ける場合には、各領域を4ビットで表すことになります。領域数 \(M\) を \(k\) 色で彩色する場合には、全体として \(N = k M\) ビットが必要になります。
次に、どのようにイジング模型を構築したら良いかを考えます。イジング模型は最適化問題のコスト関数・目的関数に対応します。望ましい組合せの場合のみに、値(エネルギー)が小さくなるようにします。
先ほどの領域と色でラベル付けされた変数を用いてコスト関数を作るにあたり、望ましい組合せとして以下の2つの条件で考える必要があります。
- ひとつの領域はひとつの色でしか塗ることができない
- 隣り合う領域の色が同じになってはならない
1. ひとつの領域はひとつの色でしか塗ることができない #
ひとつの都道府県に着目してみます。ここでは 青・緑・赤・黄の四色のうち一色を使ってこの領域を塗ること考えます。
それぞれの色を、赤: \(r\) , 緑: \(g\) , 青: \(b\) , 黄: \(y\) という変数で表現することにします。
例えばもし \(b\) が \(1\) ならこの都道府県は青色で塗られることになります。 \(r, g, y\) も同様です。しかしこの中で1となって良い変数はただひとつだけであり、異なる変数が同時に \(1\) になったり、全ての変数が \(0\) になることは禁止されています。この制約をコスト関数で表すことを考えますが、結論だけ書くと下記で表すことが出来ます。
\[ rg+rb+ry+gb+gy+by - (r+g+b+y) / 2 \]実際に値を入れて確認してみると、変数のうちどれかひとつだけ \(1\) の状況でのみ最小値 \(-1/2\) になり、それ以外の組合せでは \(0\) 以上になっています。 この条件式を全ての領域に課す必要があるためこれら総和が最初の制約条件を表すコスト関数となります。
2. 隣り合う領域の色が同じになってはならない #
関東地方の彩色において、隣同士にある都道府県の色は別々の色になる必要があります。例えば、群馬県が青と場合に、栃木県と埼玉県は青になってはならない制約です。これを全ての色、全ての隣り合う領域同士について考える必要があります。この関係を矢印でつなげると下記のようなネットワークが構築されます。
実は、この矢印の繋がりそれぞれがコスト関数に対応します。上記の青色を例に具体的に考えていきます。
例えば、ある領域の青を表す変数を \(b_1\) と隣り合う別の領域の青色を表す変数 \(b_2\) とします。この二つの変数だけに着目した場合、同時に \(1\) をとる場合のみコストが上がり、それ以外の場合は等しく低くなれば良さそうです。これは下記の式で表されます。
\[ b_1 b_2 \]確かめてみると、 \((b_1,b_2)=(1,1)\) の時のみ値 \(1\) をとり、それ以外の時は \(0\) となります。
先ほどの図の矢印すべてについて考えると、二つ目の制約条件を満たすようなコスト関数が出来上がります。
以上より、これら二種類の制約を全ての領域・全ての領域間にコスト関数を足し合わせることでアニーリングマシンへの入力が構築できます。
結果 #
関東地方の7県について D-Wave の量子アニーリングマシンである D-Wave 2000Q を用いて解くことで、解の一つとして下記のように塗り分けることが出来ました。
確認してみると、彩色問題の条件を破ることなく塗り分けられており成功していることが分かります。
彩色問題のように制約を満たす解を探す場合には、いかにして制約をコスト関数で表すかが鍵となります。与えられた制約を満たす解が複数ある場合には、それぞれが等しくコスト関数が最小になります。実は今回の問題では、三色で塗り分け可能なため何度か繰り返すと三色で塗り分けられた答えが返ってくる場合もあります。
日本全国を塗り分ける #
次に、より大きな問題として日本全国の塗り分けに挑戦してみます。日本には都道府県が47個あるので47×4=188 変数を必要とします。
このサイズでは必ずしも D-Wave の量子アニーリングマシンで実行出来るとは限らないのですが、適切な問題の分割と境界条件を設定することで塗り分けを行いました。グループ化された都道府県については、先ほどの関東地方の場合と同様にコスト関数を作成しますが、隣接してるグループ間には境界条件を設定します。
結果は以下のようになりました。
綺麗に日本全国を塗り分けることができました。北海道と青森県、山口県と福岡県は、陸続きでは無いですが、新幹線でつながっているので異なる色になるようにしてみました。
海も加えてみる #
さらに問題を難しくするために、47都道府県に加えて、海も同時に塗り分けていきます。海は青色に固定されているものだと考えます。そのため、コスト関数を作成する際に海と海に面している都道府県の間に2.の条件を満たすような条件式を加える必要があります。
そのようにしてコスト関数を作成し、アニーリングマシンで解いてみた結果、以下のようになりました。
こちらも綺麗に塗り分けることができました。問題が複雑になったとしてもそれに対応してコスト関数を適切に再定義してやれば、条件に合う解が最適解として再設定されます。
日本全国は3色で塗れるか？ #
上で示したとおり、日本全国は4色で塗り分けることができました。では3色で塗り分けてみるとどうなるのでしょうか。
ここまではコスト関数を四色で構築していましたが、これを三色(赤・緑・黄)のみに変更します。コスト関数は異なるものを用意しますが、構築の考え方はこれまでと同様にそのまま適用できます。
コスト関数を再定義し、アニーリングマシンで解いた結果以下のようになりました。
長野県だけ黒になっています。これは色の候補に対応する変数がどれも \(0\) だったため長野県の色が決定出来なかったことを表します。長野県だけに注目してコスト関数を調べると、長野県の色を決めることが出来ない状況が最もコスト関数が小さい値になっていることがわかりました。つまり、解がない場合には、長野県が制約を破る状況が最も本当の最適解に近いことを示唆しています。
最後に #
今回は日本地図に着目してアニーリングマシンで彩色問題に取り組みました。単純な日本全国の四色塗り分け以外にも、さまざまな特殊化の条件を与えてアニーリングマシンで解くことを試みました。
特に、最後の「三色で塗れるか？」という問題では、制約条件を満たすためには長野県がネックになっているという興味深い結果が得られました。アニーリングマシンによる最適化では、条件を満たす最適化が本質的に不可能な場合に「どの条件を緩めれば充足するのか」「制約を満たさない箇所が最小の解はどれか」を得られる可能性を示唆しています。
このような調査は枝切りのような方法では調べることが出来ません。また厳密に得ようとすると、例えば上限と下限を評価したり、または全通り探索する必要が出てきます。複雑なアルゴリズムを構築せずに、準最適解を含めた情報が得られるのはアニーリングマシンの注目すべき性質のひとつだと考えられます。