このページでは、精密被覆問題というNP完全な問題をイジングモデルで表現する方法について述べます。
問題の定式化 #
精密被覆問題とは、以下のような問題です。 \(n\) 点集合 \(U = \{ 1, 2, \cdots, n\}\) と、その \(N\) 個の部分集合 \(V_i \subseteq U\) が与えられます。 ただし、 \(V_i\) は \(U\) を被覆しているとします。 すなわち、 \[ U = \cup_{i=1}^N V_i \] であるとします。 このとき、 \(V_i\) たちの中からいくつか選んできて部分集合 \(R \subseteq \{ V_i \}\) を作って、 \(R\) の要素が交わりを持たず、かつ \(R\) の要素すべての和集合が \(U\) を被覆するようなものが存在するでしょうか？ すなわち、以下を満たす \(R \subseteq \{ V_i \}\) は存在するでしょうか？ \[ \forall V_i, V_j \in R, V_i \cap V_j = \emptyset, \qquad U = \cup_{V_i \in R} V_i \]
問題の具体例 #
集合
\(U=\{1,2,3,4,5,6,7,8,9\}\)
と部分集合
\(V_1=\{1,2,3,6,9\} ,V_2=\{1,2,5,8\} ,V_3=\{3,4,7\} ,V_4=\{4,5\} ,V_5=\{6,9\}\)
を考えます。下の図に分かりやすく図示しました。このとき、
\(V_2,V_3,V_5\)
によって
\(U=\{1,2,3,4,5,6,7,8,9\}\)
の要素が重複することなく一回ずつ登場することが分かるので、この問題の答えはYESです。
イジングモデルへの変形 #
この問題を解くエネルギー関数は以下のように構築されます。
各部分集合 \(V_i\) に対して対応するバイナリ変数 \(x_i\) を導入しておきます。 また、 \(A\) を正の定数とします。 するとエネルギー関数は、 \[ H_A = A \sum_{\alpha = 1}^n \left( 1 - \sum_{i: \alpha \in V_i }x_i \right)^2 \] となります。 \(\alpha\) は \(U\) の要素を表します。
精密被覆問題は判定問題ですが、最適化問題バージョンを考えることも容易にできます。 すなわち、条件を満たす \(R\) のうち要素数最小のものを求める問題です。（この問題はNP困難になります。） そのためにはエネルギー関数を以下のようにしてあげれば良いです。 \(B\) を正の定数として、 \[ H = H_A + H_B =A \sum_{\alpha = 1}^n \left( 1 - \sum_{i: \alpha \in V_i }x_i \right)^2+ B \sum_{i=1}^n x_i \]
エネルギー関数の最小化により精密被覆問題が解けるのは何故か #
エネルギー関数を最小化することで本当に精密被覆問題が解けているのでしょうか？ これは以下のようにして確かめることができます。
エネルギー関数 \(H_A\) を最小化することで \(H_A = 0\) となったとしましょう。 このとき、各 \(\alpha\) に対して \(\sum_{i: \alpha \in V_i }x_i = 1\) になっています。 すなわち、 \(N\) 個の \(V_i\) のうち \(\alpha\) を含んでいるものの中から、ただ一つの \(V_i\) だけが \(x_i = 1\) になっているということがわかります。 すると結局、最小化によって \(x_i = 1\) となった \(V_i\) を集めて \(R\) を作れば、そのようなRの要素は交わりを持たず、かつ \(U\) を被覆することがわかります。 したがって、精密被覆問題が解けたことになります。このとき、要素数の最小化よりも制約を守ることを優先するために \(A>nB\) である必要があります。
参考文献 #
A. Lucas, “Ising formulations of many NP problems” (open access)