当社はCookieを使用して、お客様が当社のWebサイトでより良い体験を得られるようにしています。引き続き閲覧する場合は、当社グループのプライバシーポリシー 
に同意したことになります。
Amplify を用いたグラフ彩色問題の解法について解説します。
グラフ彩色問題とは、あるグラフが与えられたときに、与えられた制約条件の下でその頂点などに色を割り当てる問題です。最も典型的な問題は頂点に対して隣接する頂点同士別の色で塗り分ける問題です。
平面グラフ (地図) においては、隣接する領域同士においてどんな場合でも四色あれば塗り分けられるという 四色定理 が知られています。しかしその塗り分け方法については自明ではありません。
グラフ彩色問題にはいくつかの応用例が知られており、例えば、会議室・機械・タスクなどの割り当てに関するスケジューリング問題や、コンパイラによるレジスタ割り付け、携帯電話網における周波数割り当て等が挙げられます。今回は日本の都道府県に対して、イジングマシンを用いた塗り分けを行います。
イジングマシンを用いるためにグラフの彩色状態に対して二値で表現する方法を考えます。次のように、各領域に対して四変数を用いて $0$ または $1$ を割り当てる事で表現が可能です。
| Region | Red | Green | Blue | Yellow |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 0 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 |
この例では領域 $1$ に青、領域 $2$ に緑、領域 $3$ に青、領域 $4$ に赤を割り当てることを意味しています。上記の表における各変数を領域のインデックス $i$ と色のインデックス $c$ を用いて、$q_{i,c}$ と表すことにします。よって必要な変数の数は領域数 $N$、 色数 $C$ に対して $NC$ となります。
塗り分け問題の定義から変数の間には次の制約条件が課せられます。
これらについて定式化を行うと次のように表されます。
制約条件
$$ \sum_{c = 0}^{C-1}{ q_{i,c} } = 1 \quad i \in \left\{0, 1, \cdots, N - 1 \right\} \\ \sum_{\left(i, j \right) \in E}{ q_{i,c} q_{j,c} } = 0 $$ここで $E$ はグラフ上の隣接している領域の組の集合を表します。後でプログラムコード化する都合により、変数のインデックスは $0$ からスタートしていることに注意してください。
from amplify import BinarySymbolGenerator
import japanmap as jm
colors = ["red", "green", "blue", "yellow"]
num_colors = len(colors)
num_region = len(jm.pref_names) - 1 # 都道府県数を取得
gen = BinarySymbolGenerator()
q = gen.array(num_region, num_colors)
制約条件の多項式に現れる係数は全て整数なので、amplify.BinarySymbolGenerator の代わりに
amplify.BinaryIntSymbolGenerator を用いる事も可能です。
次に制約条件を作成します。One-hot 制約は amplify.constraint.one_hot 関数、最小値0をとる制約については、
amplify.constraint.penalty 関数を用いて次のように書けます。
from amplify import sum_poly
from amplify.constraint import one_hot, penalty
# 各領域に対する制約
reg_constraints = [one_hot(q[i]) for i in range(num_region)]
# 隣接する領域間の制約
adj_constraints = [
# 都道府県コードと配列インデックスは1ずれてるので注意
penalty(q[i, c] * q[j - 1, c])
for i in range(num_region)
for j in jm.adjacent(i + 1) # j: 隣接している都道府県コード
if i + 1 < j
for c in range(num_colors)
]
constraints = sum(reg_constraints) + sum(adj_constraints)
隣接情報は japanmap.adjacent 関数に都道府県コードを入力すると隣接する都道府県コードを取得できます。q
に対するインデックスと都道府県コードには
$1$ だけ差分があるため注意してください。
最小値 $0$ をとる制約条件については、先に全ての条件の和を取ってから単一の制約条件オブジェクトを作成しても等価です。隣接する領域間の制約について次のようにも書けます。
# 隣接する領域間の制約
adj_constraints = [
# 都道府県コードと配列インデックスは1ずれてるので注意
penalty(sum_poly(q[i, c] * q[j - 1, c]) for c in range(num_colors))
for i in range(num_region)
for j in jm.adjacent(i + 1) # j: 隣接している都道府県コード
if i + 1 < j
]
以上で定式化に関する準備は完了です。
イジングマシンのクライアントを作成しパラメータを設定します。その後ソルバーを作成しクライアントを設定します。
from amplify import Solver
from amplify.client import FixstarsClient
client = FixstarsClient()
client.parameters.timeout = 5000 # タイムアウト5秒
solver = Solver(client)
制約条件から論理模型を作成し、次のようにしてイジングマシンを実行し結果を取得します。
from amplify import BinaryQuadraticModel
model = BinaryQuadraticModel(constraints)
result = solver.solve(model)
if len(result) == 0:
raise RuntimeError("Any one of constraints is not satisfied.")
values = result[0].values
もし result オブジェクトが空の場合、制約条件を満たす解が得られなかったことを意味します。この場合はイジングマシンのパラメータの変更が必要です。
values は入力変数と解の値のマッピングを表す辞書です。そのままでは評価しづらいので、次のようにして変数テーブル q と同一の形式にデコードします。
q_values = q.decode(values)
結果を {都道府県名: 色} の形式に変換します。まずは q_values の各行のうち値が1のインデックスを取得します。次のように
numpy の関数を使用します。その後、japanmap.pref_names を用いて都道府県名に変換し、対応する色を格納した辞書を作成します。
import numpy as np
color_indices = np.where(np.array(q_values) == 1)[1]
color_map = {
jm.pref_names[i + 1]: colors[color_indices[i]] for i in range(len(color_indices))
}
color_map
最後に得られた塗り分けを表示します。次のようにしてプロットされます。
%matplotlib inline
import matplotlib.pyplot as plt
plt.rcParams["figure.figsize"] = 6, 6
plt.imshow(jm.picture(color_map))
plt.show()
