このページでは、頂点被覆問題というNP困難な問題をイジングモデルによって表現する方法について述べます。
問題の定式化 #
無向グラフ \(G = (V, E)\) が与えられます。 頂点集合 \(V\) の部分集合であって、任意の辺の両端の頂点うち、いずれかの頂点がその部分集合に含まれるようなもので、要素数最小のものは何でしょうか？ すなわち、以下を満たす要素数最小の部分集合 \(R \subseteq V\) は何でしょうか？ \[ \forall uv \in E, u \in R \lor v \in R \]
問題の具体例 #
以下の図のようなグラフを用いて頂点被覆問題を考えます。図の右側のように３つの点を赤く塗ると、グラフ内の全ての辺が少なくとも１個の赤い点を端点に持つことが分かります。よってこの問題の答えはこの赤い点の集合です。
イジングモデルへの変形 #
この問題を解くエネルギー関数は以下のようにして構築されます。
まず、各頂点 \(u\) に対してバイナリ変数 \(x_u\) を導入しておきます。 また、 \(A, B\) を正の定数とします。 すると、エネルギー関数は以下のようになります。 \[ H = H_A + H_B = A \sum_{uv \in E} (1 - x_u) (1 - x_v) + B \sum_{v \in V} x_v \]
エネルギー関数の最小化により頂点被覆問題が解けるのは何故か #
エネルギー関数を最小化することで本当に頂点被覆問題が解けているのでしょうか？ これは以下のようにして確かめることができます。
バイナリ変数の値が１となっている頂点を集めて \(R\) をつくりましょう。 この \(R\) が頂点被覆問題の解となっていることを示します。
最小化により \(H_A = 0 \) となったとします。 このとき、全ての辺 \( uv \in E\) について、その両端点のうち少なくとも一方はバイナリ変数の値が１になっているはずです。 したがって、頂点被覆問題の制約が満たされています。
また、この時 \(H_B\) の値は最小化されています。 これは、 \(R\) の要素数が最小化されているということです。
すなわち、 \(R\) は頂点被覆問題の解となっていることがわかります。 もちろん、制約 \(H_A = 0\) を満たすことが \(H_B\) の最小化よりも優先されますから、正の定数 \(A,B\) は \(A > B\) を満たす必要があります。
参考文献 #
A. Lucas, “Ising formulations of many NP problems” (open access)