このページではシュタイナー木問題と呼ばれるNP困難な問題をイジングモデルで表現する方法について述べます。
問題の定式化 #
シュタイナー木問題は次数制約付き最小全域木問題に似た問題です。 無向グラフ \(G = (V, E)\) が与えられます。 また、このグラフの各辺 \(uv \in E\) には重み \(c_{uv}\) が定まっているとします。 与えられた頂点部分集合 \(U \subset V\) に対して、その最小な全域木を求めたいです。
次数制約付き最小全域木問題と比べると、次数制約がない代わりに最小全域木に用いる辺として \(U\) に含まれない頂点を端点とする辺が使用可能であることが問題を難しくしています。 この問題はNP困難な問題として知られています。
問題の具体例 #
格子点上に以下の図のような位置関係で７個の頂点が存在しています。
図の左側で、赤い頂点は必ず辺でつなぐ必要のある頂点を、水色の頂点は必ずしも辺でつなぐ必要のない頂点を表します。
このときのシュタイナー木は図の右側です。
図の右側でオレンジ色に変化した頂点は、必ずしも辺でつなぐ必要のない頂点のうちシュタイナー木に含まれた頂点を表します。
イジングモデルへの変形 #
この問題を解くためのエネルギー関数は以下のように構築されます。
考察するエネルギー関数は、次数制約付き最小全域木問題と非常に似たものになります。 ただ、以下のバイナリ変数 \(y_v\) の部分が異なります。 \(v \notin U\) に対して、 \(y_v\) なるバイナリ変数は、その頂点 \(v\) が求める全域木に含まれるか否かを表す変数であるとします。
他の変数は次数制約付き最小全域木問題と同じです。 念のため確認しておきましょう。 \(N = |V|\) とします。
頂点 \(v \in V\) と自然数 \(i \in \{ 0, 1, \ldots, N \}\) に対して、 \(x_{v,i}\) は出来上がる全域木において頂点 \(v\) が 根から深さ \(i\) の位置にあるときに１をとるバイナリ変数とします。 なお、全域木に含まれない頂点についてはこの変数は０をとることにします。 さらに、辺 \(uv \in E\) と自然数 \(i \in \{ 0, 1, \ldots, N \}\) に対して、 \(x_{uv, i}\) は出来上がる全域木において辺 \(uv\) が根から深さ \(i\) の位置にあるときに１をとるバイナリ変数とします。 なお、全域木に含まれない辺についてはこの変数は０をとることにします。 また、辺 \(uv \in E\) に対して、 \(y_{uv}\) は出来上がる全域木に辺 \(uv\) が含まれるときに１をとるバイナリ変数とします。 \(A,B\) は正の定数とします。 この時、エネルギー関数は以下のようになります。
\[ H = H_A + H_B \] \[ H_A = H_{A_1} + H_{A_2} + H_{A_3} + H_{A_4} + H_{A_5} + H_{A_6} \] \[ H_{A_1} = A \left( 1 - \sum_{v \in V} x_{v,0} \right)^2 \] \[ H_{A_2} = A \sum_{v \in U} \left( 1 - \sum_{i=0}^{N/2} x_{v,i} \right)^2 \] \[ H_{A_3} = A \sum_{v \notin U} \left( y_v - \sum_{i=0}^{N/2} x_{v,i} \right)^2 \] \[ H_{A_4} = A \sum_{v \in V} \sum_{i=1}^{N/2} \left( x_{v,i} - \sum_{uv \in E} x_{uv,i} \right)^2 \] \[ H_{A_5} = A \sum_{uv, vu \in E} \sum_{i=1}^{N/2} x_{uv, i} (2 - x_{u, i-1} - x_{v,i}) \] \[ H_{A_6} = A \sum_{uv \in E} \left( y_{uv} - \sum_{i=1}^{N/2} (x_{uv,i} - x_{vu,i}) \right)^2 \] \[ H_B = B \sum_{uv \in E} \sum_{i=1}^{N/2} c_{uv} x_{uv,i} \]
エネルギー関数の最小化により問題が解けるのは何故か #
上で定義したエネルギー関数はどのような制約を課しているのでしょうか。
まず、 \(H_{A_1}\) について考えます。 これは、ただ一つの頂点が存在して深さが０となる、すなわち根であるという制約を課しています。
次に、 \(H_{A_2}\) について考えます。 これは \(U\) に含まれる各頂点について、ちょうど一つの根からの深さ \(i\) が存在して \(x_{v,i} = 1\) となるという制約を課しています。
次に、 \(H_{A_3}\) について考えます。 これは \(U\) に含まれない各頂点について以下の制約を課しています。 まず \(y_v = 1\) 、すなわち頂点 \(v\) が全域木に含まれているとき、ちょうど一つの根からの深さ \(i\) が存在して \(v\) が深さ \(i\) になる（ \(x_{v,i} = 1\) )という制約を課しています。 一方 \(y_v = 0\) 、すなわち頂点 \(v\) が全域木に含まれないとき、全ての根からの深さ \(i\) に対して \(v\) は深さ \(i\) にならない（ \(x_{v,i} = 0\) ）という制約を課しています。
次に、 \(H_{A_4}\) について考えます。 これは各頂点 \(v\) と根からの深さ \(i \in \{ 1, \ldots, N/2 \}\) について以下の制約を課しています。 まず \(v\) が根からの深さが \(i\) である時、ちょうど一つの辺 \(uv\) が存在して、その辺の根からの深さが \(i\) になる （ \(x_{uv,i} = 1\) ）という制約を課しています。 一方で \(v\) の根からの深さが \(i\) でないときは、全ての辺 \(uv\) に対して、その辺の根からの深さは \(i\) にはならないという制約を課しています。
次に、 \(H_{A_5}\) について考えます。 これは各辺 \(uv\) と根からの深さ \(i \in \{ 1, \ldots, N/2\}\) に対して 辺 \(uv\) の根からの深さが \(i\) ならば、頂点 \(u\) と \(v\) はそれぞれ根からの深さが \(i-1\) と \(i\) になるという制約を課しています。
次に、 \(H_{A_6}\) について考えます。 これは各辺 \(uv\) について以下の条件を課しています。 まず、その辺 \(uv\) が全域木に含まれるならば、 ちょうど一つの根からの深さ \(i \in \{ 0, \ldots, N \}\) が存在して、 辺 \(uv\) か辺 \(vu\) のどちらか片方だけが根からの唯一の深さ \(i\) の位置にあるという条件を課しています。 一方で、その辺が全域木に含まれないならば、全ての根からの深さ \(i\) について、 辺 \(uv\) と \(vu\) は根からの深さ \(i\) の位置には無いという条件を課しています。
以上の６つの制約により、得られる木が制約を満たす全域木であることが保証されます。
最後に、 \(H_B\) について考えます。 これは、得られる木の重さを最小にするためのものです。 実際、これは得られる木の重みの総和になっています。 したがって、これを最小化することで重みを最小化していることになります。
もちろん、制約を満たす全域木であることは、最小性よりも優先する条件ですから、 \(A > Bmax(c_{uv})\) でなくてはいけません。
参考文献 #
A. Lucas, “Ising formulations of many NP problems” (open access)