A. Lucas, Front. Phys. (2014) 掲載例題の実装と解説 ー 最小頂点被覆問題¶
本サンプルコードでは、論文 A. Lucas, "Ising formulations of many NP problems", Front. Phys. (2014) で紹介されている『最小頂点被覆問題』に Fixstars Amplify を用いて取り組みます。同論文に紹介されている他の NP 完全・NP 困難な問題も以下で解説しています（カッコ内は論文内で問題に対応する節番号）。
- グラフの分割問題（2.2節）
- 最大クリーク問題（2.3節）
- 厳密被覆問題（4.1節）
- 集合パッキング問題（4.2節）
- 最小頂点被覆問題（4.3節）
- 充足可能性問題（SAT）（4.4節）
- 最小極大マッチング問題（4.5節）
- グラフ彩色問題（6.1節）
- クリーク被覆問題（6.2節）
- 整数長ジョブスケジューリング問題（6.3節）
- ハミルトン閉路問題（7.1節）
- 有向帰還頂点集合問題（8.3節）
- 最小帰還辺集合問題（8.5節）
- グラフ同型性判定問題（9節）
最小頂点被覆問題¶
グラフ $G$ に対して、$G$ の頂点の部分集合 $R$ であって、$G$ のどの辺についても少なくともどちらかの端点が $R$ に含まれているようなものを $G$ の 頂点被覆 といいます。$G$ の頂点被覆のうち要素数が最小のものを求める問題を 最小頂点被覆問題 といいます。
たとえば、以下のグラフにおいて、オレンジ色の頂点からなる集合は頂点被覆になっています。グラフ $G$ のどの辺も、オレンジ色の頂点に接続していることを確認してください。
ここでは、Amplify SDK を用いて、$G$ の最小頂点被覆を求めるプログラムを作成します。定式化は A. Lucas, Front. Phys. (2014) の 4.3 節のものに沿って行います。
問題の作成¶
最小頂点被覆問題を Fixstars Amplify を用いて解くために、例題として、NetworkX を使ってグラフ $G$ を作成します。
import networkx as nx
N = 6 # グラフの頂点数
G = nx.Graph()
G.add_nodes_from(range(N))
edge_list = [
(0, 1),
(0, 4),
(0, 5),
(1, 2),
(1, 4),
(2, 3),
(2, 4),
(2, 5),
(3, 4),
(4, 5),
]
G.add_edges_from(edge_list)
pos = nx.circular_layout(G)
# 作成したグラフの描画
nx.draw_networkx(G, node_size=600, font_color="w", pos=pos)
前述の通り、頂点 0, 頂点 2, 頂点 4 からなる集合は頂点被覆をなします。 また、集合 $R$ が頂点被覆となるためには、頂点 0 と頂点 1 のどちらか、頂点 2 と頂点 3 のどちらか、および頂点 4 と頂点 5 のどちらかが $R$ に含まれていなければならないので、頂点被覆の要素数の最小値は $3$ であることが分かります。
定式化¶
以下、$G$ の頂点の数を $N$ とします。
決定変数¶
$N$ 個のバイナリ変数 $q$ を各頂点と対応付けて、それぞれの頂点が頂点被覆 $R$ に含まれるかどうかを表すことにします。$R$ に含まれるなら $1$ で含まれないなら $0$ です。
たとえば、以下の図において、$R$ がオレンジ色の頂点の集合のとき、決定変数 $q$ は下の表のようになります。
| 頂点 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| $q$ | 1 | 0 | 1 | 0 | 1 | 0 |
目的関数¶
$R$ の要素数をできるだけ少なくすれば良いので、目的関数は $\displaystyle \sum_{v = 0}^{N - 1}q_v$ となります。
制約条件¶
$q$ が頂点被覆を表すためには、以下が必要です。
- 条件 1：$G$ の各辺 $(u, v)$ について、$u$ または $v$ のどちらかが $R$ に含まれる。
これは、$u$ に対応するバイナリ変数と $v$ に対応するバイナリ変数のどちらかが $1$ であるという条件なので、
$$ (1 - q_u) (1 - q_v) = 0 \quad \text{for} \quad (u, v) \in E $$
で表せます。ただし、$E$ は $G$ の辺集合です。
逆に、条件 1 が成り立つとき、明らかに $R$ は $G$ の頂点被覆となります。
実装¶
上で作成した問題と定式化を使って、実際に問題を解いてみましょう。最初に、Fixstars Amplify SDK の BinarySymbolGenerator
を使って部分集合の数だけバイナリ変数 $q$ を作成します。
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", N)
目的関数を作成します。前述の通り、目的関数は、$R$ の要素数であり、$q$ の総和をとることで計算できます。
cost = q.sum()
条件 1 に対応する制約条件を作成します。条件 1 は、$G$ の各辺について、2 つの端点のどちらかが $R$ に含まれることを意味し、$(1 - q_u) (1 - q_v) = 0 ,\:\: (u, v) \in E$ で表されます。
from amplify import equal_to, sum as amplify_sum
constraints = amplify_sum(equal_to((1 - q[u]) * (1 - q[v]), 0) for u, v in G.edges)
作成した目的関数と制約条件をまとめて、組合せ最適化モデルを構築します。今回は必要ありませんが、問題設定次第では、制約条件に重みを掛ける必要がある場合があります。基本的な考え方として、目的関数の取り得る値と同等の値またはそれより少々大きめの値を推定して決定します。
model = cost + constraints
クライアントを設定して、Fixstars Amplify Annealing Engine (AE) で実行します。Amplify SDK
は制約条件をみたす解を自動でフィルターするので、result が空でなければ、制約条件をみたす解が見つかったと分かります。
from amplify import FixstarsClient, solve
from datetime import timedelta
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境等で使用する場合は、Fixstars Amplify AE のアクセストークンを入力してください。
client.parameters.timeout = timedelta(milliseconds=1000) # タイムアウトは 1000 ms
# 求解を実行
result = solve(model, client)
if len(result) == 0:
print("頂点被覆が見つかりませんでした。")
else:
print("頂点被覆が見つかりました。")
最後に、結果を可視化します。正しく最小頂点被覆になっていることが確認できます。様々なグラフ形状でも同様に求解してみましょう。
values = q.evaluate(result.best.values)
colors = ["C1" if value == 1 else "C0" for value in values]
nx.draw_networkx(G, node_size=600, font_color="w", node_color=colors, pos=pos)
