13. 近似アルゴリズム 1
13.1 近似アルゴリズムの種類 NP 困難な問題に対しては多項式時間で最適解を求めることは困難であるので 最適解に近い近似解を求めるアルゴリズムが用いられることがある このように 必ずしも厳密解を求めないアルゴリズムは 大きく分けて 2 つの範疇に分けられる 2
ヒューリスティックと近似アルゴリズム ヒュ- リスティクス ( 発見的解法 経験的解法 ) 遺伝的アルゴリズム (GA) アニ-リング ( 焼きなまし法 ) 精度保証無し タブサーチ実験的評価が主ローカルサーチニューラルネット等 近似アルゴリズム定数近似アルゴリズム (APX) 多項式近似スキーム (PTAS) 精度保証付き完全多項式近似スキーム (FPTAS) 理論的解析が主 ここでは 近似アルゴリズムについてみていく 3
α 近似アルゴリズム 最小化問題に対して いつも最適解のα 倍以下の解を入力サイズの多項式時間で求めるようなアルゴリズムをα 近似アルゴリズムという ここで α であり 1 α を近似率という すなわち 最適解を f と表し ( OPT x ) アルゴリズムの解の評価値を f ( AL xと表すと 常 ) に次の式を満足する fal( x) f OPT ( x ) OPT α f ( x ) α f ( x ) AL OPT 4
β 近似アルゴリズム 最大化問題に対して いつも最適解のβ 倍以上の解を入力サイズの多項式時間で求めるようなアルゴリズムをβ 近似アルゴリズムという ここで β であり 1 β を近似率という また βを近似保証ということもある すなわち 最適解をと表し アルゴリズムの解 f ( OPT x ) の評価値をと表すと 常に次の式を満足す f ( ) AL x る f AL ( x) β f OPT ( x) f ( x ) β f ( x ) AL OPT 5
APX α( あるいはβ) 定数であるようなアルゴリズムが存在するクラスを APX(APproXimation) p ) という 6
PTAS と FPTAS 近似率 α(β) を限りなく1に近づけることができるとき そのようなα 近似アルゴリズムをPTAS(Polynomial Time Approximation Scheme, 多項式時間近似スキーム ) という すなわち 任意の正数 ε > 0 に対して とできる入力サイズの多項式時間アルゴリズムを α = 1 + ε PTASという さらに 入力サイズと精度 n の多項 1 ε 式時間アルゴリズムFPTAS(Fully Polynomial Time Approximation Scheme, 完全多項式時間近似スキーム ) という 問題によっては PTASが存在しない ( 知られていない ) ものがある また 定数近似すら存在しない問題もある このようなアルゴリズムの出力は入力サイズに依存した近似値になってしまう 7
近似アルゴリズムの存在 近似アルゴリズムが存在するクラス APX が存在するクラス PTAS が存在するクラス FPTAS が存在するクラス 8
13-2. 巡回セールスマン問題 巡回セールスマン問題には ネットワーク型と 幾何型とがある ネットワーク型の巡回セールスマン問題では 入力は辺重み付きのグラフであり 出力は頂点を全て辿る閉路で重みの総和が最小のものである 5 2 2 9
三角不等式を満足しないようなネットワーク型の巡回セールスマン問題は 近似アルゴリズムを得ることすら NP- 困難である 具体的には 定数近似アルゴリズムが存在するとと NP 完全問題であるハミルトン閉路問題が多項式時間で解けてしまう つまり ハミルトン閉路問題をネットワーク型の定数近似巡回セールスマン問題に帰着できてしまう このことより ネットワーク型の巡回セールスマン問題には定数近似アルゴリズムは存在しないと考えられている 10
ハミルトン閉路問題と巡回セールスマン問題 名称 : ハミルトン閉路問題インスタンス : グラフ G 問い :G 中に 全ての頂点を丁度 1 度だけ通るような閉路は存在するか? 名称 : 巡回セールスマン (NTSP) インスタンス : ネットワークN 正数 K 問い : ネットワーク中の全ての頂点を通るような閉路で重みの総和がK 以下となるようなもの存在するか? 11
巡回セールスマン問題への帰着 ネットワーク型の巡回セールスマン問題を解くα 近似アルゴリズムが存在すると 次のようにハミルトン閉路問題を巡回セールスマン問題に帰着できる つまり ハミルトン閉路問題のインスタンスであるグラフGから巡回セールスマン問題のインスタンスである辺重み付きグラフ ( ネットワーク N) と整数 Kを定めればめることができる まず Gの辺に全て1の重みをつけてネットワークNを構 n 成する 次に Kとして K = として 巡回セールスマ α ン問題へ帰着する このとき αの定数近似であるapxが存在すると 多項式時間でハミルトン閉路の存在判定ができてしまう 以上のことより P NP である限り ネットワーク型の巡回セールスマン問題を解く多項式時間アルゴリズムはない 12
幾何巡回セールスマン問題 (GTSP) 実は 幾何巡回セールスマン問題には 定数近似アルゴリズムが存在する ネットワーク型と 幾何型での最大のちがいは 三角不等式が成り立つかどうかである ここで三角不等式とは 任意の xyz,, 対して 次が成り立つことである dxy (, ) dxz (, ) + dyz (, ) 13
2 次元 ( ユークリッド ) 平面上の点集合を考えれば 2 点間の距離は自動的に三角不等式を満たす このことは 利用できる情報 ( 三角不等式 ) が多くなったということであり ネットワーク型よりも幾何型の方が問題が簡単であることを意味する. 実際 幾何型の巡回セールスマン問題は FPTASを持つことが最近 (19 98 年 ) に示された このアルゴリズムは複雑なので ここでは2 近似アルゴリズムとそれを改善した1.5 近似アルゴリズムを示す 14
NTSP と GTSP 近似アルゴリズムが存在するクラス NTSP APX が存在するクラス PTAS が存在するクラス GTSP FPTAS が存在するクラス 15
2 近似アルゴリズム GTSPに対する2 近似アルゴリズム 1. 点集合を連結する最小全域木 MST Tを求める 2.Tの辺を辿りながら 全ての点を通る巡回路 C を求める (Tの辺を全て2 重化すればいい ) 3. C で一度通過した点をショートカットする順回路を求める C ' 次にこのアルゴリズムの動作を示す 16
2 近似アルゴリズムの動作入力 ( 点集合 ) 最小木 T 2 重化ショートカット 17
近似率の解析 最適な順回路をC OPT とし アルゴリズムで得られる順回路をC AL とする また COPT, CAL でそれぞれの長さを表すものとする 順回路 C OPT から任意に一本辺を除去すると 全域木が得られる よって 最小全域木 T の方が辺の重み総和は小さい ( そもそも 頂点を連結するもののなかで 重みが最小なものが最小全域木であった ) よって 次が成り立つ T C OPT 18
また アルゴリズムで得られる閉路では 最小木を2 重化したものより小さいので 次が成り立つ C 以上より AL C 2 T AL T 2 C AL 2 T C 2 C C C AL AL OPT 2 OPT C OPT 19
1.5 近似アルゴリズム GTSPに対する1.5 近似アルゴリズム 1. 点集合を連結する最小全域木 MST Tを求める 2.T において 次数が奇数の点からなる完全グラフを作り 最小重みマッチングMを求める 3.T+M はオイラーグラフであるのでグラフであるので 一筆書きに対応する順回路 Cを求める 4.3の順回路 Cからできるだけショートかっとして 順回路を構成する C ' 20
2 近似アルゴリズムの動作入力 ( 点集合 ) 最小木 T マッチング M ショートカット 21
近似率の解析 最適な順回路をC OPT とし アルゴリズムで得られる順回路をC AL とする また COPT, CAL でそれぞれの長さを表すものとする 2 近似アルゴリズムの解析と同様にして を得る T C OPT また C OPT 上で 次数が奇数の点 ( 奇点 ) を結ぶパスを考える C OPT 上で 奇点を結ぶパスを交互に選ぶことにより 上の辺集合を2つに分類する C OPT 22
奇点が偶数個しかないことに注意すると いつもきちんと 2 分割することができることがわかる C OPT このように C OPT の辺集合を と分割できる もちろん P1 2 P C OPT = P P 1 2 よって COPT = P + P2 1 23
また 三角不等式がなりたっているので パスで結ぶより直接辺でたどったほうが短い よって 最小マッチング M の重み総和に関して, 次が成り立つ M P P min {, } OPT 1 2 C = P + P 1 2 2min P, 2 M P { } 1 2 24
一方 アルゴリズムより C T + M AL 以上より C T + M AL C C AL opt C + = 3 2 opt C opt 1.5 1 2 C opt 25
このように いろいろな技法を組み合わせて 近似率の改善が行われる NP 完全問題に対しても 厳密解でななくてもよければ 近似アルゴリズムの適用を考えてみると良い 26
13-3. ナップザック問題 ナップザック問題の一般形は次のよう書ける P ナップザック x = 特徴ベクトル 1 2 最大化 n f( x) = vx i i 条件 n i= 1 sx i i i=1= 1 b t (,,, ) x1 x2 x n xi {0,1} 27
ナップザック問題における欲張り法 ( グリーディ法 Greedy 法 ) 連続ナップザック問題のように 単位価値の高い法から順に選んでいく方法を考察する このように 部分的に評価関数を改善するだけの方法を欲張り法 (Greedy y法 ) という ( 欲張り法でも近似アルゴリズムになっていることもある これらは 問題やアルゴリズムをきちんと解析しないとわからない ) 28
ナップザックに対する欲張り法 1. 単位価値の高い順にならべる すなわち 必要なら添え字を付け換えて v v v s s s 1 2 n とする 2. から まで順番に i = 1 1 2 n i 1 n x = 1 s b s x i j j j= 1 そうでないなら x i x = とする 0 なら i とし 29
欲張り法の性能 欲張り法で得られる解を x g = ( x g 1, x g 2,, x g n ) x o = ( o, o,, o ) とおく 最適解を x1 x2 x n とおき x g = 以下では x o x なら 欲張り法と最適解が一致している g x o のときを考えよう このときは 最適解には採用されたが 欲張り解には採用されなかった最初の要素を考えてその添え字をとする すなわち j g o 0 = x < x = 1 j j このとき 任意の i g o x x j j j 1 に対して である 30
よって n j j j g g g o g o f ( x ) = vx vx = vx + v ( x x ) i i i i i i i i i i= 1 i= 1 i= 1 i= 1 v v + = + j j j j j o j g o o j g 0 vx i i si( xi xi ) vx i i sx i i sx i i i= 1 i= 1 sj i= 1 sj i= 1 i= 1 という式が成り立つ ここで 次のようなことに注意する i j 任意の i j + 1 に対して である 欲張り法で j v s i が選ばれなかったことから j j 1 g g sx i i = sx i i > b sj i= 1 i= 1 v s j 最適解でも制約式を満たすので n i= 1 sx i o i b j n 0 0 sx i i b sx i i i= 1 i= j+ 1 31
以上より 次の関係式が導ける v s j j j j n g 0 v j o sx i i sx i i ( b sj) b sx i i i= 1 i= 1 s j i= j+ 1 v n n j o o sx i i s j vx i i vj s j i=+ j 1 i=+ j 1 j n g o vj ( ) o f x vx i i + sx i i s j i= 1 s j i= j+ 1 n o o o vx i i vj f( x ) vj f( x ) v i= 1 max なお ここで vmax は価値 vi の最大値である 32
欲張り法で悪い評価値を出すインスタンス A a 1 s 1 = 1 v = 1 2 a a 2 s = v = 1 2 2 2 s = v = a 3 3 1 3 2 B = 10 a 4 s 4 = 10 v 4 = 10 S = (1,1,1,10) V = (2, 2,2,10) 2 b = 10 x g = (1,1,1, (,,, 0) g f ( x ) = 6 x o = (0,0,0,1) o f ( x ) = 10 33
ナップザックの 1/2 近似アルゴリズム ナップザックに対する 1/2 近似アルゴリズム 1. 欲張り法によって解を求める 2. 価値が最大のものを一つだけ選ぶ a 3. 上の 2 つのうちで大きい方を解 x として出力する x g 34
近似率 アルゴリズムの出力 ( 解 ) が成り立つ a x とする このとき 以下の式 f x a ( ) f x g ( ) + vmax 1 2 2 f x o ( ) 以上より 1/2 近似アルゴリズムであることがわかる 35
ナップザック問題に対する FPTAS ナップザック問題に対しては 任意の正数 ε に対する近似保証のアルゴリズムが知られている ( 1 ε) ナップザックに対する FPTAS εv 1. 与えられた ε max に対して K = とおく n vi 2. 各要素 i に対して 価値を vi ' = と修正する K r 3. 修正した価値のもとで ナップザックの最適解 x を動的計画法で求める x r 4. 上記の解と最初の価値のもとでの最大値を比べて a 評価値の高いものをアルゴリズムの出力 ( 解 ) とする x 36
FPTAS の評価 v i ' v K i = とおいていることにより 0 v Kv ' < K x f '( x) よって 任意の解に対して, その修正後の評価値に関して次式が成立する 一方 また 0 f ( x) Kf '( x) < nk r x は修正した価値での最適解なので r o f '( x ) f '( x ) a f ( x ) v max i i 37
よって f ( x a ) f( x r ) Kf '( x r ) Kf '( x o ) f ( x ) nk = f ( x ) εv f ( x ) εf ( x ) o o o a max 以上より a o (1 + ε) f ( x ) f ( x ) a 1 o o f ( x ) f( ) > (1 ε) f( ) 1 + ε x x 38
計算時間 ステップ 3 の動的計画法の部分について考察しよう まず 動的計画法に基づくナップザックアルゴリズムとして 大きさが決まっているときの価値の最大値を表として構成していた この動的計画法に基づいた場合 Onb ( ) 時間のアルゴリズムが得られた ここでは この動的計画法を以下の方針に切り替える 価値が決まってているときに 大きさの最小値として構成する このような動的計画法も構成できることに注意する この場合 価値の最大値は v max であるので 評価値の最大値は である よって アルゴリズムの計算量は Onv ( ) max 2 max Onv ( ) 時間である FPTASでは修正した値を用いるので 結局 2 vmax 2 n 1 3 On ( ) = On ( ) = O( n) K ε ε 39
ナップザック問題の近似可能性 近似アルゴリズム ナップザック APX PTAS FPTAS 40