近似アルゴリズム ――集合被覆問題を中心として 慶應義塾大学理工学部数理科学科４年 田村 明久研究室 山崎 康史 今日の内容 近似アルゴリズムの必要性 ＯＰＴの下界法（頂点被覆問題） 集合被覆問題 欲張り法 層別化法 ベンチマーク問題に対する結果 今後の課題 クラスNPとNP最適化問題 判定問題 答えが“yes”か“no”の問題 クラスNP “yes”の検証を多項式時間で出来る判定問題 NPであるどの問題からも多項式時間で変換できる問題 NP困難 NP最適化問題 実行可能解の中で、目的関数の値を最小（または 最大）にするものを見つける問題 （例）巡回セールスマン問題、ナップザック問題 など NP困難な問題は多項式時間 で解けないと考えられている 近似解を効率よく求める必要が ある 近似アルゴリズムの定義 近似解を効率よく求める： 近似アルゴリズム 近似アルゴリズムの定義（最小化問題） 最適解の目的関数値（最適値）をOPTで表す δ：Ｚ＋→Ｑ＋ 入力のサイズに関する関数（δ≧１） 多項式時間で近似解を出力 得られた任意の近似解sに対して （sの目的関数値）≦δ（入力のサイズ）・ＯＰＴ が成り立つとき、δ-近似アルゴリズムという。 この範囲の近似解を多項式時間で出力 0 OPT δ・OPT 目的関数値 OPTの下界法 近似保証を得るには、近似解とＯＰＴを比較 NP困難だとOPTを得ることも多項式時間では 難しい 近似保証が得られない？ OPTの下界法 よい下界を用いることで、近似保証を得る この範囲の近似解を出力すれば、 δ・OPT以下の近似解になっている 0 下界 δ・下界 OPTはどこにあるか分からない 目的関数値 δ・OPT 頂点被覆問題（１） 問題の定義 頂点被覆 （個数版）頂点被覆問題 頂点数が最小になるような頂点被覆を求めよ。 頂点被覆問題（２） マッチングとの関係 マッチングと極大マッチング 頂点被覆と極大マッチングの関係 極大マッチングの辺の、少なくとも一方の端点は、 頂点被覆に含まれる |極大マッチング|≦|頂点被覆| 頂点被覆問題（３） アルゴリズム アルゴリズム1 端点を共有しないように、辺を取れるだけ取ってく ることで、極大マッチングを得る 極大マッチングの両端点の集合を答えとして出力 する。 頂点被覆問題（４） 近似保証 アルゴリズム1は2-近似アルゴリズムである （証明） |極大マッチング|≦|頂点被覆|だから、 |極大マッチング|≦OPT （１） アルゴリズムの動きから、 |得られた近似解|＝２・|極大マッチング| ≦２・OPT （∵（１）） よって、2-近似アルゴリズム 集合被覆問題 集合被覆 台集合U、集合族S(⊆2U） Uの全ての要素を覆うような Sの部分族を集合被覆という。 ① ② ④ ⑤ ⑥ ⑦ ③ ⑧ 集合被覆問題 台集合U、集合族S、コスト関数c:S→Q+ コストの和が最小になるような集合被覆を求めよ。 欲張り法（１） アルゴリズム 効果対費用 すでにカバーされている集合をCとする 集合S∈Sに対して、c(S)/|S-C|を集合Sの効果 対費用という 効果対費用は、まだカバーしていない要素を集合 Sでカバーするのにかかる平均のコストといえる アルゴリズム２ 効果対費用の最も小さい集合を答えに加える すべてカバーされたら終了。そうでなかったら繰り 返す。 欲張り法（２） ① ② ④ ⑤ ⑥ ⑦ ① ② ④ ⑤ ⑥ ⑦ ③ 動作例 ■１÷２＝０．５ ■１÷１＝１ ■空集合 ■１÷２＝０．５ ■１÷１＝１ ■空集合 ⑧ ③ ■１÷３＝１/３ ■すでに選ばれた 選ばれる ■１÷２＝０．５ ■すでに選ばれた 選ばれる ■１÷２＝０．５ ■１÷１＝１ ■空集合 ■１÷３＝１/３ ■すでに選ばれた ⑧ ■１÷３＝１/３ ■１÷１＝１ ■空集合 選ばれる 終了 欲張り法（３） 近似保証について アルゴリズム２はHn-近似アルゴリズムである。 ただし、 Hn ＝１＋１/２＋・・・＋１/n （証明のアイディア） 要素をカバーされた順にe1,・・・,enとする。 カバーされたときの効果対費用をprice(ek)と すると、price(ek)≦OPT/(n-k+1) コストの総和はprice(ek)の総和に等しく、 （１＋１/２＋・・・＋１/n）・OPTになる。 層別化法（１） 準備 頻度 要素が集合族Sに現れる回数 個数定倍コスト ｔ(S)＝ｋ|S|で表される関数ｔ：S→Q＋ 個数定倍最大コスト c(S)≧t(S)を満たす最大の個数定倍コスト 残余コスト コスト関数から個数定倍最大コストを引いた残り 層別化法（２） アルゴリズム アルゴリズム３ 集合族から空集合を取り除く。 集合族が空なら答えを出力して終了。 残余コストを計算して、残余コストが０の集合を答 えに加え、集合族から取り除く。 コスト関数を残余コストで更新。 集合族の各集合から、答えでカバーされた要素を 取り除き、最初に戻る。 層別化法（３） アルゴリズムのイメージ 空集合 残余コスト ０の集合 答えとして 出力 残余コスト ０の集合 残余コスト ０の集合 空集合 ・ ・ ・ ・ ・ ・ 空集合 空集合 層別化法（４） ① ④ ② ③ 動作例 個数定倍最大コスト：|S|/３ 個数定倍最大コスト：|S|/６ 個数定倍最大コスト：なし ■コスト：１、残余コスト：１/３ ■コスト：１/３、残余コスト：１/６ ■コスト：１/６、空集合 ⑤ ■コスト：１、残余コスト：１/３ ■コスト：１/３、残余コスト：１/６ ■コスト：１/６、空集合 ⑥ ⑦ ⑧ ① ② ③ ④ ⑥ 選ばれる ■コスト：１、残余コスト：１/３ ■コスト：１/３、残余コスト：０ ■すでに選ばれた 選ばれる ■コスト：１、残余コスト：１/３ ■コスト：１/３、空集合 ⑤ ⑦ ■コスト：１、残余コスト：０ ■すでに選ばれた ⑧ ■コスト：１、残余コスト：０ ■すでに選ばれた 選ばれる ■コスト：１、残余コスト：０ ■すでに選ばれた 終了 選ばれる 層別化法（５） 近似保証について アルゴリズム３はf-近似アルゴリズムである。 ただし、fは最大頻度。 （証明のアイディア） Tを得られた近似解、T*を最適解とする。 各i層において、ti(Si)≦f・ti(Si∩T*) c(T)≦∑ti(Si) ≦ｆ・∑ti(Si∩T*) ≦ｆ・OPT よって、ｆ-近似アルゴリズム ベンチマーク問題を用いた検証 CPU: PentiumM 1GHz メモリ: 1GB Cコンパイラ: gcc-4.1.1-r1 台集合のサイズ 17800 58600 126000 集合族のサイズ 450 945 1534 最適値 420 900 1475 欲 張 り 法 コスト 430 915 1496 精度 1.024 1.017 1.014 時間 8 sec 91 sec 427 sec 層 別 化 法 コスト 438 930 1515 精度 1.043 1.033 1.027 時間 9 sec 91 sec 424 sec ※各数字は平均に近い値 ※精度は（コスト）÷（最適値） まとめ・今後の課題 集合被覆問題に対して、Hn-近似アルゴリズ ムである欲張り法と、f-近似アルゴリズムであ る層別化法が得られた。 何を下界として近似保証を得たのかが曖昧。 線型計画問題（LP）の双対性の理論から眺め ていくことで、欲張り法・層別化法がそれぞれ 何を下界としているのかをハッキリさせていく ことが、今後の課題。 参考文献 「近似アルゴリズム」 V.V.ヴァジラーニ 著 ベンチマーク問題（Web） http://www.nlsde.buaa.edu.cn/~kexu/benchm arks/set-benchmarks.htm
© Copyright 2024 ExpyDoc
