アルゴリズム入門 (8) ( 近似アルゴリズム ) 宮崎修一京都大学学術情報メディアセンター
近似アルゴリズムとは? 効率よく解ける問題 ( 多項式時間アルゴリズムが存在する問題 ) ソーティング 最短経路問題 最小全域木問題 効率よく解けそうにない問題 (NP 困難問題 ) 最小頂点被覆問題 MX ST MX CUT 本質的に問題が難しいのだが 何とか対応したい 幾つかのアプローチ ( 平均時間計算量 指数時間アルゴリズム 確率アルゴリズム 近似アルゴリズム ) 2
指数時間アルゴリズム 最適解 ( 正しい解 ) を得たい 指数時間かかることは仕方ない しかし 指数時間の中でも できるだけ高速であって欲しい ( 例 ) 3ST (3CNF 式の充足可能性問題 ) 1.618 n [Monien,Speckenmeyer,79] n 1.362 [Paturi et al.,98] n 1.334 [Schoening,99] n 1.3302 [Hofmeister et al.,02] n 1.3290 [aumer,schuler,03] n 1.3280 [Rolf,03] n n 1.3238 (1.3227 )[Iwama,Tamaki,04] n 1.32216 [Rolf,05] n 1.32113 [Iwama, Takai, Seto, Tamaki,10] n 1.32065 [Hertli, Moser, Scheder, 10] n 1.30704 [Hertli,11] 3
近似アルゴリズム 指数時間かかるのは困る 多項式時間で解が欲しい 代わりに 解の質をあきらめる ( 最適解でなくてよい ) でも できるだけ良い解が欲しい 近似アルゴリズムの良さ例えば最小化問題 アルゴリズム の近似度が r である ( は r- 近似アルゴリズムである ) どんな入力に対しても アルゴリズム の出す解のコストは最適解のコストの r 倍以内である 近似度 r は 1 以上 小さいほど良い 最適は 1 4
最小頂点被覆問題 枝 : 道路頂点 : 交差点交差点にガードマンを配置して 全ての道を警備したい できるだけ少ないガードマンで済ませるには どこに配置したら良いか? 74 個の頂点 問題 : 最適は? ちなみに 3 個では無理 問題 : なぜ? 最小頂点被覆問題は NP 困難 ( 多項式時間アルゴリズムが存在しそうにない ) 5
頂点被覆問題に対する近似度 2のアルゴリズム問題 : どうしてこれは近似度 2? log log N 2-2 log N 1 2 -Θ( ) log N [Monien & Speckenmeyer 1985] [Karakostas 2004] 6
近似アルゴリズムに対するアプローチ 上限の研究 問題に対する c- 近似アルゴリズムを開発する c の値を小さくしていく方向 下限の研究 (P NP の仮定の下で ) 問題が c- 近似アルゴリズムを持たないことを示す c の値を大きくしていく方向 例 :MX 3ST 上限 : 8/7- 近似アルゴリズムは存在する 下限 : P NP ならば (8/7-ε)- 近似アルゴリズムは存在しない (ε: 任意の正定数 ) [Hastad 1997] ちなみに 最小頂点被覆問題は 上限: 1 2 -Θ( ) [Karakostas 2004] log N 下限: 10 5-21 1.362 [Dinur, Safra 2002] 7
安定結婚問題 ( の最適化問題 ) General 2 [easy] log N ( 2 - c ) [Iwama, Miyazaki, Okamoto 2004] N ( 2 - c 1 ) [Iwama, Miyazaki, Yamauchi 2005] N 1.875 [Iwama, Miyazaki, Yamauchi 2007] 1.667 [Kiraly 2008] One-sided ties 1.667 [Irving, Manlove 2008] 1.5 [McDermid 2009] 1.5 [Kiraly 2008] [McDermid 2009] 1.4706 [Iwama, Miyazaki, Yanagisawa 2010] 1.4667 [Huang Kavitha 2014] 1.4643 [Radnai 2014] 1.4616 [Dean Jalasutram 2015] 1.333 (under UGC) [Yanagisawa 2007] 1.25 (under UGC) [Halldorosson, Iwama, 1.137 (unless P=NP) [Yanagisawa 2007] Miyazaki, Yanagisawa 2007] 1.105 (unless P=NP) [Halldorosson, Iwama, Miyazaki, Yanagisawa 2007] PX-hard: There is no (1+ε)-approximation algorithm. [Halldorosson, Iwama, Miyazaki, Morita 2002] 8 NP-hard [Iwama, Manlove, Miyazaki, Morita 1999]
MX CUT 入力 : グラフ G 出力 :G の頂点集合の 2 分割間にある枝数が出来るだけ多くなるように 例 45 本 MX CUT も NP 困難問題 9
MX CUT に対する局所探索法 近傍 :=1 頂点だけを反対側のグループへ移す 適当な初期解から出発して 解のサイズが改善される近傍がある限り その近傍に移り続ける これ以上移動できなくなったら 今の解を出力する 10
アルゴリズムが終了した時の性質 どの頂点も 自分のグループへの枝数 相手のグループへの枝数 さもなければ その頂点を移動させたら さらに良い解が得られる 11
両端が 内にある枝数 : 両端が 内にある枝数 : 間にまたがる枝数 : E, E, E, 全ての枝数 : E E = E, + E, + E, 12
v 頂点 vからへの枝数 e v への枝数 e v とすると v ならばe v e v v ならばe v e v 13
v 頂点 vからへの枝数 e v への枝数 e v とすると v ならばe v e v v ならばe v e v 14
v v ならばe ならばe v v e e v v v の全ての頂点 vについて e E E 2,,. v e v を足し合わせると 15
v v ならばe ならばe v v e e v v v の全ての頂点 vについて e 2 E, E,. v e v を足し合わせると 16
17. 2 2,,,,,,, E E E E E E E + より と.. 2,,,,,, E E E E E E E E E E + + = 一方 最適解つまり なので よって このアルゴリズムは 2- 近似アルゴリズム
MX CUT に対する貪欲アルゴリズム Step 1: 頂点を適当に選び どちらかに適当に入れる 18
MX CUT に対する貪欲アルゴリズム Step 1: 頂点を適当に選び どちらかに適当に入れる 19
MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選び これまで既に入っている頂点とのカットがより大きくなる方に入れる 20
MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選び これまで既に入っている頂点とのカットがより大きくなる方に入れる 21
MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選び これまで既に入っている頂点とのカットがより大きくなる方に入れる 22
MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選び これまで既に入っている頂点とのカットがより大きくなる方に入れる 23
MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選び これまで既に入っている頂点とのカットがより大きくなる方に入れる 24
MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選び これまで既に入っている頂点とのカットがより大きくなる方に入れる 25
MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選び これまで既に入っている頂点とのカットがより大きくなる方に入れる 26
近似度の解析 27
近似度の解析 左へ入れた場合 利得 28
近似度の解析 29
近似度の解析 右へ入れた場合 利得 30
近似度の解析 アルゴリズムは この 2 つのうち 大きい方 ( 小さくない方 ) の利得を得るように動く ( このうち 半分は得る ) 31
近似度の解析 MX CUT の現在最良の近似度は 1.138 この部分を 全部の頂点について足し合わせたら ちょうど全ての枝 アルゴリズムは 全枝の半分はカットする ( 前と同じ議論で ) 近似度 2 32
巡回セールスマン問題京都駅から出発して 観光して 京都駅に戻って来たい 同じところは 2 度通らない できるだけ短い経路で回る 33
応用 : コンビニの配送計画自動販売機のジュース補給配送計画集積回路 (VLSI) の配線ロボットのアームの動き最適化 TSPLI 様々なベンチマーク集合に対する 解法競争が行われている http://comopt.ifi.uni-heidelberg.de/software/tspli95/ 34
TSPLI のベンチマークの 1 つ日本の 9847 都市 35
その最適解 36
アメリカ 13509 都市 37
38
きっちり定式化すると入力 : 完全グラフ G=(V, E) 各枝 ee EE に対して 長さ cc(ee) ( 頂点は観光スポットに対応 枝の長さは移動距離に対応 ) 出力 : G の各頂点を 1 度ずつ通る閉路 ただし 使われた枝の長さの合計が最小となるもの ( 同じ頂点を 2 度通ってはいけないことに注意 ) 39
単純なアルゴリズム : 頂点数をnとする それぞれの回り方 (n! 通りの順列 ) に対して 総距離を計算し 最も短い経路を出力する 確かに最適解が得られるが n! 時間かかる (n! > 2 n) 実際 NP 困難であることが証明されている 近似アルゴリズム 距離空間が三角不等式を満たす場合の 2- 近似アルゴリズム 1.5- 近似アルゴリズム ユークリッド平面の場合( 例えば先程の京都市の例 ) は 近似度が限りなく1に近いアルゴリズム (PTS) が知られている 40
2- 近似アルゴリズムステップ 1: 最小全域木を求める ( そのコストを T とする ) ( 巡回セールスマンの最適解のコストを OPT とすると T<OPT ) 問題 : なぜ? 41
2- 近似アルゴリズムステップ 2: 最小全域木沿いにツアーを組む ( 同じ枝を 2 度なぞる ) このツアーの長さを P とすると P=2T 42
2- 近似アルゴリズムステップ 3: 同じところを 2 度通らないように飛ばす このツアーの長さを L とすると L P ( 三角不等式より ) 43
2- 近似アルゴリズムステップ 4: 得られたツアーを出力する 近似度の解析 L P=2T<2OPT 44
1.5- 近似アルゴリズムステップ 1 までは一緒 T<OPT 45
1.5- 近似アルゴリズムステップ 2: 奇数次数の頂点を選ぶ ( 偶数個ある ) 問題 : なぜ? 46
1.5- 近似アルゴリズムステップ 3: 緑の頂点間の最小重みマッチングを求める ( 枝の長さの総和が最小のもの ) 元あった枝と合わせて 全ての頂点の次数が偶数 47
1.5- 近似アルゴリズムステップ 4: オイラー回路を求める 青のツアー長 =T+ 48
1.5- 近似アルゴリズムステップ 5: 先程のオイラー回路で 2 度目の頂点を飛ばす 得られた緑のツアーを出力する 緑のツアー長 青のツアー長 青のツアー長 =T+ T<OPT の全長 0.5OPT を言う 49
奇数次数 ( 緑 ) の頂点だけのツアーで最短のものを考えよう 水色のツアー長 OPT ( 例えば OPT のツアーで 赤色頂点を飛ばせば良い ) 50
そのツアー上の 1 つとびの枝集合 2 組 の全長 + = の全長のツアー長 51
そのツアー上の 1 つとびの枝集合 2 組 の全長とのうち短い方を の全長とする の全長 1/2 の全長 52
そのツアー上の 1 つとびの枝集合 2 組 の枝集合はマッチングの枝集合は最小マッチングの全長 の全長 1/2 の全長 1/2 OPT 示したかったこと 53
近似アルゴリズムの限界 では よりも良い近似度の多項式時間近似アルゴリズムは存在しない というのは どういう風に示すのか? 判定問題の時と同様に リダクション ( 還元 ) を使う 前の例は 判定問題 (Yes/No を答える ) から判定問題へのリダクションだった 今回は 判定問題から最適化問題 ( 最適値を答える ) へのリダクションであるところが違う 54
グラフのハミルトン閉路各頂点を ちょうど 1 度ずつ通る閉路 7 10 1 11 2 4 6 9 13 14 3 5 8 12 与えられたグラフがハミルトン閉路を持つか否かを問う問題 ( ハミルトン閉路問題 ) は NP 完全 55
ハミルトン閉路問題 ( 判定問題 ) から巡回セールスマン問題 ( 最適化問題 ) へリダクションをする ハミルトン閉路問題の入力グラフ G 巡回セールスマン問題の入力グラフ H H の作り方 H の頂点集合は G と同じ H は完全グラフ G で枝のある所 H では枝の重み ( 長さ )1 G で枝のない所 H では枝の重み n+1 56
例 G H 重み 1 重み 6 57
G が YES の例題 (G にハミルトン閉路がある ) H は重み 1 の枝だけを使って一周することができる 総距離 n で一周できる 最適の 1.8 倍悪い解でも 1.8n 以下で収まる G が NO の例題 (G にハミルトン閉路がない ) H を一周するどんな経路も 重み n+1 の枝を使う 総距離は少なくとも (n-1)+(n+1)=2n 最適解は 2n 以上 58
巡回セールスマン問題に 1.8- 近似アルゴリズム が存在したとする を使って G を解くことを考える ハミルトン閉路問題 入力 G YES NO の答を見れば G が YES か NO か分かる ハミルトン閉路問題が解けてしまう 巡回セールスマン問題入力 H 最適値はn 最適値は 2n の答 1.8n 2n 対偶を取ると ハミルトン閉路問題が難しいならば巡回セールスマン問題に 1.8- 近似アルゴリズムは存在しない 59
ポイントは YES NO の答 の答 1.8n 2n この 2 つが重ならないこと n 1.8n 2n YES NO 最適値は n 最適値は 2n この n と 2n のギャップが 近似度の下限を与えた より大きなギャップを作る還元を設計することで 近似度のより大きな下限が言える 60
問題 : 最初の方で巡回セールスマン問題に対する 1.5- 近似アルゴリズムを見たが 1.8- 近似アルゴリズムが存在しないことが示せてしまった これは矛盾ではないのか? 61