Graph Coloring

Amplify を用いたグラフ彩色問題の解法について解説します。

グラフ彩色問題の定式化

グラフ彩色問題とは、あるグラフが与えられたときに、与えられた制約条件の下でその頂点などに色を割り当てる問題です。最も典型的な問題は頂点に対して隣接する頂点同士別の色で塗り分ける問題です。

https://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Petersen_graph_3-coloring.svg/200px-Petersen_graph_3-coloring.svg.png

平面グラフ (地図) においては、隣接する領域同士においてどんな場合でも四色あれば塗り分けられるという 四色定理 が知られています。しかしその塗り分け方法については自明ではありません。

グラフ彩色問題にはいくつかの応用例が知られており、例えば、会議室・機械・タスクなどの割り当てに関するスケジューリング問題や、コンパイラによるレジスタ割り付け、携帯電話網における周波数割り当て等が挙げられます。今回は日本の都道府県に対して、イジングマシンを用いた塗り分けを行います。

イジングマシンを用いるためにグラフの彩色状態に対して二値で表現する方法を考えます。次のように、各領域に対して四変数を用いて \(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\) となります。

塗り分け問題の定義から変数の間には次の制約条件が課せられます。

  • 一領域を一色で塗る

  • 隣接する領域に対して同色で塗らない

これらについて定式化を行うと次のように表されます。

制約条件

\[\begin{split}&\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\end{split}\]

ここで \(E\) はグラフ上の隣接している領域の組の集合を表します。後でプログラムコード化する都合により、変数のインデックスは \(0\) からスタートしていることに注意してください。

問題の作成

日本地図を扱うために Python の japanmap モジュールを使用します。都道府県コード ( \(1 \sim{} 47\)) を用いて都道府県名や隣接情報などを取得できます。

まずは色の定義を行い、変数テーブルを用意します。

from amplify import BinaryPoly, gen_symbols
import japanmap as jm

colors = ["red", "green", "blue", "yellow"]
num_colors = len(colors)
num_region = len(jm.pref_names) - 1  # 都道府県数を取得

q = gen_symbols(BinaryPoly, num_region, num_colors)

>>> q
[[q_0, q_1, q_2, q_3], [q_4, q_5, q_6, q_7], [q_8, q_9, q_10, q_11], [q_12, q_13, q_14, q_15],
 [q_16, q_17, q_18, q_19], [q_20, q_21, q_22, q_23], [q_24, q_25, q_26, q_27], [q_28, q_29, q_30, q_31],
 [q_32, q_33, q_34, q_35], [q_36, q_37, q_38, q_39], [q_40, q_41, q_42, q_43], [q_44, q_45, q_46, q_47],
 [q_48, q_49, q_50, q_51], [q_52, q_53, q_54, q_55], [q_56, q_57, q_58, q_59], [q_60, q_61, q_62, q_63],
 [q_64, q_65, q_66, q_67], [q_68, q_69, q_70, q_71], [q_72, q_73, q_74, q_75], [q_76, q_77, q_78, q_79],
 [q_80, q_81, q_82, q_83], [q_84, q_85, q_86, q_87], [q_88, q_89, q_90, q_91], [q_92, q_93, q_94, q_95],
 [q_96, q_97, q_98, q_99], [q_100, q_101, q_102, q_103], [q_104, q_105, q_106, q_107],
 [q_108, q_109, q_110, q_111], [q_112, q_113, q_114, q_115], [q_116, q_117, q_118, q_119],
 [q_120, q_121, q_122, q_123], [q_124, q_125, q_126, q_127], [q_128, q_129, q_130, q_131],
 [q_132, q_133, q_134, q_135], [q_136, q_137, q_138, q_139], [q_140, q_141, q_142, q_143],
 [q_144, q_145, q_146, q_147], [q_148, q_149, q_150, q_151], [q_152, q_153, q_154, q_155],
 [q_156, q_157, q_158, q_159], [q_160, q_161, q_162, q_163], [q_164, q_165, q_166, q_167],
 [q_168, q_169, q_170, q_171], [q_172, q_173, q_174, q_175], [q_176, q_177, q_178, q_179],
 [q_180, q_181, q_182, q_183], [q_184, q_185, q_186, q_187]]

Note

制約条件の多項式に現れる係数は全て整数なので、 BinaryPoly の代わりに BinaryIntPoly を用いる事も可能です。

次に制約条件を作成します。One-hot 制約は equal_to() 関数、最小値0をとる制約については、 penalty() 関数を用いて次のように書けます。

from amplify import sum_poly
from amplify.constraint import equal_to, penalty

# 各領域に対する制約
reg_constraints = [
    equal_to(sum_poly([q[i][c] for c in range(num_colors)]), 1)
    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\) だけ差分があるため注意してください。

Note

最小値 \(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.url = "http://xxx.xxx.xxx.xxx"
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
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

Note

もし result オブジェクトの長さが 0 の場合、制約条件を満たす解が得られなかったことを意味します。この場合はイジングマシンのパラメータの変更が必要です。

結果の解析

values は入力変数と解の値のマッピングを表す辞書です。そのままでは評価しづらいので、次のようにして変数テーブル q と同一の形式にデコードします。

from amplify import decode_solution

q_values = decode_solution(q, values, 1)

>>> q_values
[[0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 1, 0],
 [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0], [1, 0, 0, 0],
 [0, 0, 1, 0], [0, 1, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 1, 0, 0],
 [0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0],
 [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 0, 1], [1, 0, 0, 0],
 [0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0], [1, 0, 0, 0],
 [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 0, 1],
 [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]]

結果を {都道府県名: 色} の形式に変換します。まずは 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
{'北海道': 'green', '青森県': 'green', '岩手県': 'yellow', '宮城県': 'green', '秋田県': 'red',
 '山形県': 'yellow', '福島県': 'blue', '茨城県': 'green', '栃木県': 'red', '群馬県': 'green',
 '埼玉県': 'blue', '千葉県': 'yellow', '東京都': 'red', '神奈川県': 'yellow', '新潟県': 'red',
 '富山県': 'blue', '石川県': 'green', '福井県': 'blue', '山梨県': 'green', '長野県': 'yellow',
 '岐阜県': 'red', '静岡県': 'red', '愛知県': 'blue', '三重県': 'green', '滋賀県': 'yellow',
 '京都府': 'red', '大阪府': 'yellow', '兵庫県': 'green', '奈良県': 'blue', '和歌山県': 'red',
 '鳥取県': 'blue', '島根県': 'green', '岡山県': 'yellow', '広島県': 'red', '山口県': 'blue',
 '徳島県': 'green', '香川県': 'yellow', '愛媛県': 'red', '高知県': 'blue', '福岡県': 'yellow',
 '佐賀県': 'blue', '長崎県': 'red', '熊本県': 'green', '大分県': 'red', '宮崎県': 'yellow',
 '鹿児島県': 'red', '沖縄県': 'red'}

最後に得られた塗り分けを表示します。次のようにしてプロットされます。

import matplotlib.pyplot as plt

plt.rcParams["figure.figsize"] = 6, 6
plt.imshow(jm.picture(color_map))
plt.show()
_images/coloring_figure1.png