【追実験】D-Wave LeapのDQMを使って地図の塗り分け問題を最少の色で解く

はじめに

AIREV株式会社の上里です。
以前に投稿したDiscrete Quadratic Model（DQM）で地図の塗り分け問題を解く記事で、カナダの州を4色で塗り分けてみました。こちらはD-Waveの公式ドキュメントの例題を使わせていただいたのですが、塗り分け結果の地図をまじまじ見ていると、「3色でも塗り分けられそうな地図じゃないか？」ということに気が付いてしまいました。今回はより少ない色で地図の塗り分けを行うように問題定式化を工夫し、実際に3色で塗り分けができるか、追実験をしてみたいと思います。

前回の問題定式化のおさらい

ここでは簡単におさらいをしますが、DQMの基礎的な知識やD-Wave Leapの利用方法などについては省きますので、適宜公式ドキュメントや前回の記事を参照してください。

例題：カナダの13州の地図塗り分け問題

カナダの全13の州（準州を含む）に、地図上で隣り合っている州に同じ色を塗らないように4つの色を割り当てる方法を量子アニーリングを利用して探し出します。

13の州のリストを provinces 、隣り合っている州のペアのリストを borders 、4つの色のリストを colors とします。

provinces = [
  "AB", "BC", "ON", "MB", "NB", "NL", "NS",
  "NT", "NU", "PE", "QC", "SK", "YT"
]
borders = [
  ("BC", "AB"), ("BC", "NT"), ("BC", "YT"), ("AB", "SK"), ("AB", "NT"),
  ("SK", "MB"), ("SK", "NT"), ("MB", "ON"), ("MB", "NU"), ("ON", "QC"),
  ("QC", "NB"), ("QC", "NL"), ("NB", "NS"), ("YT", "NT"), ("NT", "NU")
]
colors = [0, 1, 2, 3]

変数の設定

DQMのインスタンスを生成し、変数を追加します。それぞれの州に対してどの色が割り当てられたかを示すように変数を作成していきます。具体的には、 colors の {0, 1, 2, 3} の色の値をとることができる変数をそれぞれの州ごとに作成します。

import dimod

dqm = dimod.DiscreteQuadraticModel()
for p in provinces:
  dqm.add_variable(len(colors), label=p)

目的関数のペナルティの設計

地図上で隣り合っている2つの州が同じ色を割り当てられてしまうケースに対してペナルティ 1 を与えます。

for p0, p1 in borders:
  dqm.set_quadratic(p0, p1, {(color, color): 1 for color in colors})

ここまでが前回の記事の定式化になります。

色の種類にペナルティを設定

前回の定式化で、色を整数のリスト [0, 1, 2, 3] として表現していました。1 の色を使うごとにペナルティ 1 を、 2 の色を使うごとにペナルティ 2 を与える、といった具合に、色の値をそのままペナルティとするようにDQMの set_linear メソッドでペナルティを設定し、数値の大きい色をなるべく使わないように最適化させます。3 や 2 の色を相対的に使いづらくなるので、結果として 3 を使わずに3色で塗り分ける解が最適解として導かれることを期待しています。

colors = [0, 1, 2, 3]

for p in provinces:
  dqm.set_linear(p, colors)

このとき、隣り合った州が同じ色を割り当てられてしまう場合のペナルティの値と色の種類によるペナルティの値の相対的な大小関係が問題になります。今回は隣り合った州に同じ色を割り当てないことを最優先とし、その上でなるべく少ない数の色を使った解を導きたいので、隣り合った州に同じ色を割り当てたときのペナルティを相対的に大きく設定します。
具体的には、色の種類に対するペナルティの最大の合計値 max(colors) * len(provinces) より大きい値を隣り合った州に同じ色を割り当てたときのペナルティとして設定します。

adj_penalty = max(colors) * len(provinces) + 1

for p0, p1 in borders:
  dqm.set_quadratic(p0, p1, {(color, color): adj_penalty for color in colors})

解いてみる

実際に解いてみた結果は次のとおりです。

7.0 # Energy
{'AB': 1, 'BC': 0, 'MB': 1, 'NB': 0, 'NL': 0, 'NS': 1, 'NT': 2, 
 'NU': 0, 'ON': 0, 'PE': 0, 'QC': 1, 'SK': 0, 'YT': 1} # Sample

（0: 青, 1: 赤, 2: 緑）

隣り合った州に同じ色を割り当てずに3色で塗り分けられています。
今回の定式化では利用した色の値をペナルティとしているので、 1 の色を5回、 2 の色を1回利用した結果、エネルギーの値が 1 * 5 + 2 * 1 = 7.0 となっています。
また最も値の小さい 0 の色が7回利用されており、 3 の色は一度も利用されていません。
「数値の大きい色をなるべく使わないように最適化する」という今回の定式化の狙いの通りの結果が得られていることがわかります。

2色では塗り分けられないのか

本当に隣り合う州に同じ色が割り当てられない解が得られる最少の色の数は3色なのでしょうか。
念の為、色の値によるペナルティを組み込んでいない前回の記事の定式化で、色のリストを colors = [0, 1] に変更し、2色だけで塗り分けられるかを検証してみます。

colors = [0, 1]

dqm = dimod.DiscreteQuadraticModel()
for p in provinces:
  dqm.add_variable(len(colors), label=p)

for p0, p1 in borders:
  dqm.set_quadratic(p0, p1, {(color, color): 1 for color in colors})

結果は下記のようになります。

２.0 # Energy
{'AB': 1, 'BC': 0, 'MB': 1, 'NB': 0, 'NL': 0, 'NS': 1, 'NT': 1, 
 'NU': 0, 'ON': 0, 'PE': 1, 'QC': 1, 'SK': 0, 'YT': 0} # Sample

（0: 青, 1: 赤）

エネルギーの値が 2.0 となっており、2箇所で隣り合った州が同じ色を割り当てられてしまっています。
（前回の記事の定式化を利用しているので、色の値によるペナルティは加算されません。）
したがって、3色がカナダの州を塗り分けられる最少の色の数であることが確認できました。
今回の定式化は想定どおりに最少の色で塗り分けを行えているようです。

まとめ

今回は最少の色でカナダの州の塗り分けを行う問題をDQMで定式化してみました。
結果として3色での塗り分けが可能であることがわかりました。
今後はより実用的な問題設定でのアニーリングの適用を試してみたいと考えています。