研究成果 > アルゴリズムのデモ > 最小カット問題
最小カット問題とは
例えば,100人の学生がいて,これを二つのグループに分けるとします.二人の学生の間には,出身地や趣味な どにより結びつきの強さが数値で表わされているとします.このとき,それぞれのグループ内における結びつき が強くなるように,言い換えると,二つのグループ間の結びつきの数値が最小になるようにしたいとします(グ ループ内の人数は同じでなくてよい).
この問題をグラフを使って表します.グラフとはいくつかの節点(点)の集まりと点と点をつなぐ枝(辺)の集 まりからなります.枝には数値がついています.グループ分けの例では,一人の学生が一つの節点に対応し,二 人の学生間の結びつきが,対応する 2節点間の枝の数値に対応します(結びつき度が 0であれば枝をつけないこ とにします).すると問題は,グラフの節点の集合を二つの集合に分けて,二つの集合間にまたがる枝の数値の 和を最小にする問題になります.このような分割を最小カットといいます.
デモの説明: 永持-茨木法
このデモでは永持,茨木により提案されたアルゴリズムを実行します(この方法は最小カットを正確に計算する 方法としては現在世界最速の計算性能を持っています).
まず,この方法は,グラフの節点に番号を 1,2,3,... とつけています. 最初に好きな節点に 1をつけ,その後は以下のルール M に従って節点を選んでいきます.
ルール M: 「残りの節点の中で,すでに選ばれた節点の集まりに最も結びつきの強い(枝の数値の和が最大である)節点を選ぶ」ルール M でつけられた番号を最大隣接順序と言います.
デモでは,最初の節点に選びたいところでクリックをすると,その節点の色が水色に変わり,1の番号がつきま す.もう一度クリックをすると,1番の節点に最も結びつきの強い節点が水色に変わり,2の番号がつきます.再 度クリックをすると,1, 2の節点に最も結びつきの強い節点が選ばれ 3の番号がつきます.クリックを繰り返す と最後の点にまで番号がつき,最大隣接順序が得られます.
最大隣接順序の性質
この番号付けにおいて,最後の二つの節点(A, Bとする)に対しては,節点 A と節点 B を別々のグループに分 けるような分割の中では,最後の節点1個とそれ以外の節点を分けるのが,最も分割の両側にまたがる枝の数値 和が小さくなることが証明されています.デモでは赤い枝としてこれらの枝が表示されます.
この性質では,最後の二つの節点を別々のグループに入れたらという条件のもとでの最小カットですので,求め たい最小カットではないかもしれません.そこで,いまの最小カットの値を保存しておきます(デモでは画面左 上に,A-BCDEF [140] のように表示がでます.これは,節点 A と節点 B, C, D, E, F に分割する最小カットの 値が 140であることを意味します.)
次にやるべきことは,最後の二つの節点(A, Bとする)が必ず同じグループに入るような分割の仕方を調べるこ とです.ここで,後の計算で,2節点A,Bが決して分離されないように,A と B とを 1個の節点にまとめてしま います.デモでは最大隣接順序が求まった後に,自動的に最後の番号の 2節点が 1個に併合されますのでこの様 子を確認してください.
以上で,アルゴリズムの1反復分の作業の説明が終わりました.後はこの作業を繰り返すだけです.つまり,
(1) 最大隣接順序を計算し,という作業をグラフがただ 一つの節点になるまで繰り返して,記録した値のうちで最も小さい値をもつものを (求めるべき)最小カットとすればよいだけです.
(2) 最後の2節点を分離する最小カットを記録し,
(3) この2節点を1個の節点に併合する
遊び方
好きな節点をクリックして 1番の節点として下さい.クリックを続けるとすべての節点に番号がつきます.節点 は番号に従って時計回りの位置に再配置されます.最後の節点とそれ以外の節点の間にまたがる枝が赤色で表示 されます.もう一度クリックをすると,最後の2節点が併合されます.これを繰り返してください.最後に求め るべき最小カットが画面右上の記録から選択され,もとのグラフにおいて赤い枝として表示されデモが終了しま す.
デモの動きの速度を変えるには画面中央下のからnormal(中速),quick(高速),slow(低速)を選択してください.
画面中央下にある Resetボタンを押すと最初のグラフに戻ります.