ｽﾗｲﾄﾞﾀｲﾄﾙなし

Size: px

Start display at page:

Download "ｽﾗｲﾄﾞﾀｲﾄﾙなし"

みさきおおばま
5 years ago
Views:

1 アルゴリズム入門 (8) ( 近似アルゴリズム ) 宮崎修一京都大学学術情報メディアセンター

2 近似アルゴリズムとは? 効率よく解ける問題 ( 多項式時間アルゴリズムが存在する問題 ) ソーティング最短経路問題最小全域木問題効率よく解けそうにない問題 (NP 困難問題 ) 最小頂点被覆問題 MX ST MX CUT 本質的に問題が難しいのだが何とか対応したい幾つかのアプローチ ( 平均時間計算量指数時間アルゴリズム確率アルゴリズム近似アルゴリズム ) 2

3 指数時間アルゴリズム最適解 ( 正しい解 ) を得たい指数時間かかることは仕方ないしかし指数時間の中でもできるだけ高速であって欲しい ( 例 ) 3ST (3CNF 式の充足可能性問題 ) n [Monien,Speckenmeyer,79] n [Paturi et al.,98] n [Schoening,99] n [Hofmeister et al.,02] n [aumer,schuler,03] n [Rolf,03] n n ( )[Iwama,Tamaki,04] n [Rolf,05] n [Iwama, Takai, Seto, Tamaki,10] n [Hertli, Moser, Scheder, 10] n [Hertli,11] 3

4 近似アルゴリズム指数時間かかるのは困る多項式時間で解が欲しい代わりに解の質をあきらめる ( 最適解でなくてよい ) でもできるだけ良い解が欲しい近似アルゴリズムの良さ例えば最小化問題アルゴリズムの近似度が r である ( は r- 近似アルゴリズムである ) どんな入力に対してもアルゴリズムの出す解のコストは最適解のコストの r 倍以内である近似度 r は 1 以上小さいほど良い最適は 1 4

5 最小頂点被覆問題枝 : 道路頂点 : 交差点交差点にガードマンを配置して全ての道を警備したいできるだけ少ないガードマンで済ませるにはどこに配置したら良いか? 74 個の頂点問題 : 最適は? ちなみに 3 個では無理問題 : なぜ? 最小頂点被覆問題は NP 困難 ( 多項式時間アルゴリズムが存在しそうにない ) 5

6 頂点被覆問題に対する近似度 2のアルゴリズム問題 : どうしてこれは近似度 2? log log N 2-2 log N 1 2 -Θ( ) log N [Monien & Speckenmeyer 1985] [Karakostas 2004] 6

7 近似アルゴリズムに対するアプローチ上限の研究問題に対する c- 近似アルゴリズムを開発する c の値を小さくしていく方向下限の研究 (P NP の仮定の下で ) 問題が c- 近似アルゴリズムを持たないことを示す c の値を大きくしていく方向例 :MX 3ST 上限 : 8/7- 近似アルゴリズムは存在する下限 : P NP ならば (8/7-ε)- 近似アルゴリズムは存在しない (ε: 任意の正定数 ) [Hastad 1997] ちなみに最小頂点被覆問題は上限: 1 2 -Θ( ) [Karakostas 2004] log N 下限: [Dinur, Safra 2002] 7

8 安定結婚問題 ( の最適化問題 ) General 2 [easy] log N ( 2 - c ) [Iwama, Miyazaki, Okamoto 2004] N ( 2 - c 1 ) [Iwama, Miyazaki, Yamauchi 2005] N [Iwama, Miyazaki, Yamauchi 2007] [Kiraly 2008] One-sided ties [Irving, Manlove 2008] 1.5 [McDermid 2009] 1.5 [Kiraly 2008] [McDermid 2009] [Iwama, Miyazaki, Yanagisawa 2010] [Huang Kavitha 2014] [Radnai 2014] [Dean Jalasutram 2015] (under UGC) [Yanagisawa 2007] 1.25 (under UGC) [Halldorosson, Iwama, (unless P=NP) [Yanagisawa 2007] Miyazaki, Yanagisawa 2007] (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]

9 MX CUT 入力 : グラフ G 出力 :G の頂点集合の 2 分割間にある枝数が出来るだけ多くなるように例 45 本 MX CUT も NP 困難問題 9

10 MX CUT に対する局所探索法近傍 :=1 頂点だけを反対側のグループへ移す適当な初期解から出発して解のサイズが改善される近傍がある限りその近傍に移り続けるこれ以上移動できなくなったら今の解を出力する 10

11 アルゴリズムが終了した時の性質どの頂点も自分のグループへの枝数相手のグループへの枝数さもなければその頂点を移動させたらさらに良い解が得られる 11

12 両端が内にある枝数 : 両端が内にある枝数 : 間にまたがる枝数 : E, E, E, 全ての枝数 : E E = E, + E, + E, 12

13 v 頂点 vからへの枝数 e v への枝数 e v とすると v ならばe v e v v ならばe v e v 13

14 v 頂点 vからへの枝数 e v への枝数 e v とすると v ならばe v e v v ならばe v e v 14

15 v v ならばe ならばe v v e e v v v の全ての頂点 vについて e E E 2,,. v e v を足し合わせると 15

16 v v ならばe ならばe v v e e v v v の全ての頂点 vについて e 2 E, E,. v e v を足し合わせると 16

17 ,,,,,,, E E E E E E E + よりと.. 2,,,,,, E E E E E E E E E E + + = 一方最適解つまりなのでよってこのアルゴリズムは 2- 近似アルゴリズム

18 MX CUT に対する貪欲アルゴリズム Step 1: 頂点を適当に選びどちらかに適当に入れる 18

19 MX CUT に対する貪欲アルゴリズム Step 1: 頂点を適当に選びどちらかに適当に入れる 19

20 MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選びこれまで既に入っている頂点とのカットがより大きくなる方に入れる 20

21 MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選びこれまで既に入っている頂点とのカットがより大きくなる方に入れる 21

22 MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選びこれまで既に入っている頂点とのカットがより大きくなる方に入れる 22

23 MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選びこれまで既に入っている頂点とのカットがより大きくなる方に入れる 23

24 MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選びこれまで既に入っている頂点とのカットがより大きくなる方に入れる 24

25 MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選びこれまで既に入っている頂点とのカットがより大きくなる方に入れる 25

26 MX CUT に対する貪欲アルゴリズム Step 2 以降 : 頂点を適当に選びこれまで既に入っている頂点とのカットがより大きくなる方に入れる 26

27 近似度の解析 27

28 近似度の解析左へ入れた場合利得 28

29 近似度の解析 29

30 近似度の解析右へ入れた場合利得 30

31 近似度の解析アルゴリズムはこの 2 つのうち大きい方 ( 小さくない方 ) の利得を得るように動く ( このうち半分は得る ) 31

32 近似度の解析 MX CUT の現在最良の近似度はこの部分を全部の頂点について足し合わせたらちょうど全ての枝アルゴリズムは全枝の半分はカットする ( 前と同じ議論で ) 近似度 2 32

33 巡回セールスマン問題京都駅から出発して観光して京都駅に戻って来たい同じところは 2 度通らないできるだけ短い経路で回る 33

34 応用 : コンビニの配送計画自動販売機のジュース補給配送計画集積回路 (VLSI) の配線ロボットのアームの動き最適化 TSPLI 様々なベンチマーク集合に対する解法競争が行われている 34

35 TSPLI のベンチマークの 1 つ日本の 9847 都市 35

36 その最適解 36

37 アメリカ都市 37

38 38

39 きっちり定式化すると入力 : 完全グラフ G=(V, E) 各枝 ee EE に対して長さ cc(ee) ( 頂点は観光スポットに対応枝の長さは移動距離に対応 ) 出力 : G の各頂点を 1 度ずつ通る閉路ただし使われた枝の長さの合計が最小となるもの ( 同じ頂点を 2 度通ってはいけないことに注意 ) 39

40 単純なアルゴリズム : 頂点数をnとするそれぞれの回り方 (n! 通りの順列 ) に対して総距離を計算し最も短い経路を出力する確かに最適解が得られるが n! 時間かかる (n! > 2 n) 実際 NP 困難であることが証明されている近似アルゴリズム距離空間が三角不等式を満たす場合の 2- 近似アルゴリズム 1.5- 近似アルゴリズムユークリッド平面の場合( 例えば先程の京都市の例 ) は近似度が限りなく1に近いアルゴリズム (PTS) が知られている 40

41 2- 近似アルゴリズムステップ 1: 最小全域木を求める ( そのコストを T とする ) ( 巡回セールスマンの最適解のコストを OPT とすると T<OPT ) 問題 : なぜ? 41

42 2- 近似アルゴリズムステップ 2: 最小全域木沿いにツアーを組む ( 同じ枝を 2 度なぞる ) このツアーの長さを P とすると P=2T 42

43 2- 近似アルゴリズムステップ 3: 同じところを 2 度通らないように飛ばすこのツアーの長さを L とすると L P ( 三角不等式より ) 43

44 2- 近似アルゴリズムステップ 4: 得られたツアーを出力する近似度の解析 L P=2T<2OPT 44

45 1.5- 近似アルゴリズムステップ 1 までは一緒 T<OPT 45

46 1.5- 近似アルゴリズムステップ 2: 奇数次数の頂点を選ぶ ( 偶数個ある ) 問題 : なぜ? 46

47 1.5- 近似アルゴリズムステップ 3: 緑の頂点間の最小重みマッチングを求める ( 枝の長さの総和が最小のもの ) 元あった枝と合わせて全ての頂点の次数が偶数 47

48 1.5- 近似アルゴリズムステップ 4: オイラー回路を求める青のツアー長 =T+ 48

49 1.5- 近似アルゴリズムステップ 5: 先程のオイラー回路で 2 度目の頂点を飛ばす得られた緑のツアーを出力する緑のツアー長青のツアー長青のツアー長 =T+ T<OPT の全長 0.5OPT を言う 49

50 奇数次数 ( 緑 ) の頂点だけのツアーで最短のものを考えよう水色のツアー長 OPT ( 例えば OPT のツアーで赤色頂点を飛ばせば良い ) 50

51 そのツアー上の 1 つとびの枝集合 2 組の全長 + = の全長のツアー長 51

52 そのツアー上の 1 つとびの枝集合 2 組の全長とのうち短い方をの全長とするの全長 1/2 の全長 52

53 そのツアー上の 1 つとびの枝集合 2 組の枝集合はマッチングの枝集合は最小マッチングの全長の全長 1/2 の全長 1/2 OPT 示したかったこと 53

54 近似アルゴリズムの限界ではよりも良い近似度の多項式時間近似アルゴリズムは存在しないというのはどういう風に示すのか? 判定問題の時と同様にリダクション ( 還元 ) を使う前の例は判定問題 (Yes/No を答える ) から判定問題へのリダクションだった今回は判定問題から最適化問題 ( 最適値を答える ) へのリダクションであるところが違う 54

55 グラフのハミルトン閉路各頂点をちょうど 1 度ずつ通る閉路与えられたグラフがハミルトン閉路を持つか否かを問う問題 ( ハミルトン閉路問題 ) は NP 完全 55

56 ハミルトン閉路問題 ( 判定問題 ) から巡回セールスマン問題 ( 最適化問題 ) へリダクションをするハミルトン閉路問題の入力グラフ G 巡回セールスマン問題の入力グラフ H H の作り方 H の頂点集合は G と同じ H は完全グラフ G で枝のある所 H では枝の重み ( 長さ )1 G で枝のない所 H では枝の重み n+1 56

57 例 G H 重み 1 重み 6 57

58 G が YES の例題 (G にハミルトン閉路がある ) H は重み 1 の枝だけを使って一周することができる総距離 n で一周できる最適の 1.8 倍悪い解でも 1.8n 以下で収まる G が NO の例題 (G にハミルトン閉路がない ) H を一周するどんな経路も重み n+1 の枝を使う総距離は少なくとも (n-1)+(n+1)=2n 最適解は 2n 以上 58

59 巡回セールスマン問題に 1.8- 近似アルゴリズムが存在したとするを使って G を解くことを考えるハミルトン閉路問題入力 G YES NO の答を見れば G が YES か NO か分かるハミルトン閉路問題が解けてしまう巡回セールスマン問題入力 H 最適値はn 最適値は 2n の答 1.8n 2n 対偶を取るとハミルトン閉路問題が難しいならば巡回セールスマン問題に 1.8- 近似アルゴリズムは存在しない 59

60 ポイントは YES NO の答の答 1.8n 2n この 2 つが重ならないこと n 1.8n 2n YES NO 最適値は n 最適値は 2n この n と 2n のギャップが近似度の下限を与えたより大きなギャップを作る還元を設計することで近似度のより大きな下限が言える 60

61 問題 : 最初の方で巡回セールスマン問題に対する 1.5- 近似アルゴリズムを見たが 1.8- 近似アルゴリズムが存在しないことが示せてしまったこれは矛盾ではないのか? 61

Microsoft PowerPoint - 13.ppt [互換モード]

Microsoft PowerPoint - 13.ppt [互換モード] 13. 近似アルゴリズム 1 13.1 近似アルゴリズムの種類 NP 困難な問題に対しては多項式時間で最適解を求めることは困難であるので最適解に近い近似解を求めるアルゴリズムが用いられることがあるこのように必ずしも厳密解を求めないアルゴリズムは大きく分けて 2 つの範疇に分けられる 2 ヒューリスティックと近似アルゴリズムヒュ- リスティクス ( 発見的解法経験的解法 ) 遺伝的アルゴリズム

ｽﾗｲﾄﾞ ﾀｲﾄﾙなし

ｽﾗｲﾄﾞﾀｲﾄﾙなし