最大カット問題

最大カット問題 (MAX-CUT)は、あるグラフのノードを二つのグループに分ける場合に、エッジを切る数（エッジに重みがある場合は切るエッジの重みの総和）が最大となる分け方を求めるという問題です。 グラフに関する典型的な最適化問題で画像処理や通信網・交通網などのネットワーク計画などに応用されます。

上図のグラフの場合、Aの場合がカット数=5となり最大となります。 Bの場合はカット数=2で最小であり、これを求める最小カット問題 (MIN-CUT)も存在します。

グラフ$~G=(V,E)~$において、各エッジ$~(i,j)\in E~$に重み$~w_{i,j} (>0)~$があるとします。このとき、

を最大にする$~V_1,V_2 (V=V_1\cup{V_2})~$を求めるのが最大カット問題です。

アニーリングマシンで解くためにこれをイジングモデルの形式で定式化します。
まず、分割したときにノード$~v_i \in V$がどちらの部分集合に属するかを表す変数$~s_i~$を定義します。

このとき、カット値（切るエッジの重みの総和）$~C~$は以下の式で表すことができます。

一般にアニーリングマシンはエネルギー関数の最小値を探索するため、最大化問題は$-1$を掛けて最小化問題にすることで解くことができます。したがって、アニーリングマシンに入力するイジングモデルのエネルギー関数$~H~$は以下のようになります。

ここでは最大カット問題をアニーリングで解くシミュレーションを体験できます。

シミュレーションのサンプルとして、最適解が自明である2-正則グラフを用います。

ノード数とステップ数を可変として実行してみます。グラフ上の赤い直線が最適解（=ノード数）となります。