第4章 多分割カットと k-カット 作: 牧山幸史 これまでのあらすじ • • • • 現実で遭遇する最適化問題の多くは「NP困難」 厳密解を求めるのに、膨大な計算時間が必要 近似解ならば、求めることができるかも。 個々の問題に対する近似アルゴリズムを調査する (第Ⅰ部): 第1章: 個数版点カバー問題 (近似率2) 第2章: 集合カバー問題 (近似率 Hn) 第3章: シュタイナー木とTSP (近似率2と1.5) 第4章: 多分割カットと k-カット 多分割カットと k-カット(目次) • (寄り道) 最小 s-t カット問題 • 多分割カット問題 • 最小 k-カット問題 ふじ祭り(吉祥寺) • 北九州八幡西区吉祥寺町 • 明治37年に樹齢50年位 たったフジを植えたのがは じまり • フジが咲き揃った様は豪華 絢爛 • 4月下旬から5月上旬にか けて見頃 • フジの開花期間は夜10時 までライトアップされ夜も花 見ができる ふじ祭り(吉祥寺) ◆ 開花時期 には多くの 見物客が訪 れる ふじ祭り(吉祥寺) ◆ ふじ祭り期間には 参道にたくさんの 店がでる ある露店にて フ ァ ミ コ ン ジ ュ ー ス ぬ い ぐ る み せ ん べ い た わ し お か し 糸切り 1回 100円 ある露店にて フ ァ ミ コ ン ジ ュ ー ス ぬ い ぐ る み せ ん べ い た わ し お か し 糸切り 1回 100円 ちょっとした提案 店のにーちゃん 100円 100円 100円 100円 100円 目隠し フ ァ ミ コ ン ジ ュ ー ス ぬ い ぐ る み せ ん べ い た わ し 糸切り 1回 100円 ちょっとした提案 店のにーちゃん 店のにーちゃん 450円 100円 100円 100円 100円 100円 100円 250円 10円 50円 120円 フ ァ ミ コ ン ジ ュ ー ス ぬ い ぐ る み せ ん べ い た わ し 糸切り 1本 100円 450円 10円 300円 200円 1000円 ファミコン ちょっとした提案 店のにーちゃん 店のにーちゃん 450円 100円 250円 10円 50円 120円 フ ァ ミ コ ン ジ ュ ー ス ぬ い ぐ る み せ ん べ い た わ し 糸切り 1本 100円 450円 10円 300円 200円 1000円 ファミコン ちょっとした提案 店のにーちゃん 450円 250円 700円 370円 100円 10円 50円 120円 450円 610円 10円 300円 200円 1000円 ファミコン 430円 1000円 最小 最小 s-t カット問題 • 辺に重みを持つ連結なグラフ G が与えられ、2つの 頂点 s, t が指定されたとき、次の性質を持つ辺集 合のうちで、重みの総和が最小となるものを見つけ よ: • その辺集合に属する辺をすべて取り除くと、グラフ G は s を含む部分グラフと t を含む部分グラフとに 分割される。 • このような辺集合を s-t カット という。 最小 s-t カット問題 s 店のにーちゃん 450円 100円 250円 10円 50円 120円 450円 300円 250 100 10 50 120 10円 200円 450 10 300 200 1000円 ファミコン 450 1000 t 最小 s-t カット問題 s 店のにーちゃん 450円 100円 250円 10円 50円 120円 450 100 450円 10 50 120 10円 300円 200円 250 10 300 200 1000円 ファミコン 450 1000 610 (100+50+10+450) t 最小 s-t カット問題 s 店のにーちゃん 450円 100円 250円 10円 50円 120円 450 100 450円 120 300円 1000円 ファミコン 10 50 10円 200円 250 450 10 300 200 最小 370 (100+10+10+250) 1000 t 最小 s-t カット問題 • 一般のグラフが与えられたとき、最小 s-t カットを求 める多項式時間アルゴリズムは存在するか? • 答え: 存在する • なぜならば、最大フローを求める多項式時間アルゴ リズム(Goldberg-Tarjan Algorithm)が存在する からである。 最大フロー最小カット定理 (maxflow-mincut thm.) 重み付きグラフ(ネットワーク)の最大フローと最小カット の値は一致する。 ネットワークの最大フロー • ネットワークの重みを、単 位時間にその辺へ流すこ とのできる最大の水量と みなす。 • このとき、頂点 s から t へ流すことのできる最大 の水量を最大フローとい う。 s 450 250 50 100 120 10 450 10 300 200 1000 t ネットワークの最大フロー • ネットワークの重みを、単 位時間にその辺へ流すこ とのできる最大の水量と みなす。 • このとき、頂点 s から t へ流すことのできる最大 の水量を最大フローとい う。 150 450 100 120 100 s 250 50 10 450 10 300 200 100 1000 t ネットワークの最大フロー • ネットワークの重みを、単 位時間にその辺へ流すこ とのできる最大の水量と みなす。 • このとき、頂点 s から t へ流すことのできる最大 の水量を最大フローとい う。 120 150 450 100 120 100 s 250 20 50 +10 10 250 450 10 300 200 100 1000 t ネットワークの最大フロー • ネットワークの重みを、単 位時間にその辺へ流すこ とのできる最大の水量と みなす。 • このとき、頂点 s から t へ流すことのできる最大 の水量を最大フローとい う。 120 150 450 100 120 100 370 s 250 20 50 10 10 200 100 +10 260 250 450 260 300 370 1000 t 370 最大フロー最小カット定理 s 450 100 50 120 250 10 100 450 120 100 10 200 120 150 450 370 s 250 20 50 10 10 300 260 250 450 260 300 最小 200 最小カットに含まれる辺には 100 370 1000 1000 最大フローでは容量一杯に 370 水が流れている。 t t 370 最大フロー最小カット定理 • 最大フローと最小カットの値は一致する。 ⇒ 容量一杯に水が流れている辺をうまく取ると、最小 カットになる。 370 s 250/250 100/100 10/10 370 t 10/10 容量一杯に水が流れている辺 最小 s-t カット問題(まとめ) • 辺に重みを持つ連結なグラフ G が与えられ、2つの 頂点 s, t が指定されたとき、 s-t カットのうちで、重 みの総和が最小となるものを求めよ。 • 最小 s-t カット問題は、最大フローアルゴリズムを用 いて、多項式時間で解くことができる。 多分割カットと k-カット(目次) • (寄り道) 最小 s-t カット問題 • 多分割カット問題 • 最小 k-カット問題 多分割カット問題 • 辺に重みを持つ連結なグラフ G が与えられ、k 個 の頂点 s1, s2, …, sk が指定されたとき、次の性質 をもつ辺集合のうちで、重みの総和が最小となるも のを求めよ: • その辺集合に属する辺をすべて取り除くと、グラフ G は s1 を含む部分グラフ,s2 を含む部分グラ フ,・・・,sk を含む部分グラフというように、k 個の部 分グラフに分割される。 • このような辺集合を多分割カット という。 多分割カット問題 重み付きグラフ G 重み付きグラフ G s S1 S2 S4 t S3 多分割カット問題 • 多分割カット問題を解く多項式時間アルゴリズムは 存在するか? • 答え: たぶん存在しない 多分割カット問題は「NP困難」 P=NPでない限り、この問題を解く多項式時間 アルゴリズムは存在しない。 多分割カット問題 とにかく考えてみる S2 5 10 2 2 1 2 10 1 10 1 5 2 2 S1 10 2 5 1 1 3 3 5 S4 3 1 1 S3 多分割カット問題 • ムリ • 第Ⅰ部の主旨: – NP困難な問題に対して、ナイーブなアルゴリズ ムの近似率を解析する。 ⇒ 最小の多分割カットを求めることは諦めて、無駄 はあるかもしれないが、とりあえず多分割カットとな る辺集合を求める。 多分割カット問題 (ナイーブなアルゴリズムを考える) • 「最小 s-t カットを求めるアルゴリズム」を使った3 つの単純なアルゴリズム: A) どんどん分割型アルゴリズム B) 孤立カット-削除型アルゴリズム C) 孤立カット-全体型アルゴリズム 多分割カット問題 (A)どんどん分割型アルゴリズム 重み付きグラフ G S2 S1 S3 S5 S4 多分割カット問題 (B)孤立カット-削除型アルゴリズム 重み付きグラフ G S2 S1 孤立カット S3 S5 S4 多分割カット問題 (C)孤立カット-全体型アルゴリズム S2 の孤立カット 重み付きグラフ G S2 20 S3 の孤立カット 30 S1 S3 S1 の孤立カット 18 S5 の 孤立カット 15 S5 S4 S4 の孤立カット 9 多分割カット問題 (ナイーブなアルゴリズムを考える) • 「最小 s-t カットを求めるアルゴリズム」を使った3 つの単純なアルゴリズム: A) どんどん分割型アルゴリズム B) 孤立カット-削除型アルゴリズム C) 孤立カット-全体型アルゴリズム p.40 アルゴリズム 4.3 ① ② ③ ④ 最小重み孤立カットを求めるアルゴリズム アルゴリズム(C)の近似率は2-2/k タイトな例 アルゴリズム(A)と(B)に対するコメント 多分割カット問題 (孤立カットを求める) • 「最小重み孤立カット」を求めるアルゴリズムを考え る: • 孤立させたいターミナル(指定された頂点)を s とし たとき、s 以外のターミナルを同一視したグラフを作 り(その頂点を t とする)、最小 s-t カットを求める。 • このときの最小 s-t カットが、 s に対する「最小重み 孤立カット」となる。 孤立カットを求める S2 5 10 2 2 1 1 3 2 10 5 1 1 10 1 5 2 2 S1 10 2 5 1 1 5 S1 の最小孤立カットS4 3 3 3 1 1 S3 孤立カットを求める • 本当に最小孤立カットになっているか? • S1 以外のターミナルを同一視したグラフ G’ の s-t カットは、もとのグラフ G の孤立カットである。 G s G’ s t 孤立カットを求める • 本当に最小孤立カットになっているか? • S1 以外のターミナルを同一視したグラフ G’ の s-t カットは、もとのグラフ G の孤立カットである。 • G の孤立カットは、すべて G’ における s-t カットで ある。 G s G’ s t 孤立カットを求める • 本当に最小孤立カットになっているか? • S1 以外のターミナルを同一視したグラフ G’ の s-t カットは、もとのグラフ G の孤立カットである。 • G の孤立カットは、すべて G’ における s-t カットで ある。 • G の孤立カットの集合 = G’ の s-t カットの集合 • 最小 s-t カット = 最小孤立カット 多分割カット問題 • 最小 s-t カットを求めるアルゴリズムにより、最小孤 立カットを求めることができた。 • 次は、アルゴリズム 4.3 の近似率が 2-2/k となるこ とを示す。 アルゴリズム 4.3 1. 各 i=1,…,k に対して、si に対する最小重み孤立カット Ci を求める; 2. これらのカットで重み最大のものを1つ除いて、残りのカッ トの和集合をとり、それを C として出力する. 多分割カット問題 (アルゴリズム 4.3) C = C1 ∪C2 ∪C4 ∪C5 S2 最大 S1 C2 C1 C3 C5 S5 C4 S4 S3 多分割カット問題 (アルゴリズム4.3の近似率) 最小多分割カットを A とする。 S2 最適解 A cost(C)≦(2-2/k)cost(A)? S1 S3 S5 S4 多分割カット問題 (アルゴリズム4.3の近似率) 最小多分割カットを A とする。 S2 の孤立カット A2 S2 最適解 A S3 の孤立カット A3 S1 S3 S1 の孤立カット A1 S5 S5 の孤立カット A5 S4 S4 の孤立カット A4 多分割カット問題 (アルゴリズム4.3の近似率) • Ai の直和集合には、 A の要素が2つづつ含まれる。 • つまり、A = {e1, e2, … , em } とおくと、 ∑1≦i≦k Ai = {e1, e1, e2, e2, … , em , em } となる。 • したがって、 Ai のコストの総和は、 A のコストの2 倍となる。すなわち、 ∑1≦i≦k cost(Ai ) = 2・cost(A) が成り立つ。 多分割カット問題 (アルゴリズム4.3の近似率) • アルゴリズム4.3 の出力は C = ∪1≦i≦k Ci ー Cmax ただし、 Ci はターミナル Si の最小孤立カット、 Cmax は Ci の中でコストが一番高いものである。 • すべての i に対して cost(Ci) ≦ cost(Ai) が成り立 つので、 cost(C) ≦ ∑1≦i≦k cost(Ci ) ≦ ∑1≦i≦k cost(Ai ) が成り立つ。 = 2・cost(A) 多分割カット問題 (アルゴリズム4.3の近似率) • 最大重みの孤立カット Cmax のコスト は、Ci のコスト の総和の平均以上である。すなわち、 cost(Cmax) ≧ 1/k ・∑1≦i≦k cost(Ci ) である。したがって、 cost(C) ≦ ∑1≦i≦k cost(Ci ) ー cost(Cmax) ≦ (1-1/k) ・∑1≦i≦k cost(Ci ) ≦ (1-1/k) ・ ∑1≦i≦k cost(Ai ) = (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A) 多分割カット問題 (アルゴリズム4.3の近似率) cost(C) ≦ (2-2/k) ・cost(A) • アルゴリズム4.3によって得られた解のコストは、最 適解のコストの (2-2/k) 倍以下となることがわかっ た。 • アルゴリズム4.3の近似率は、これ以上改善されな いのか? • 答え: されない ∵ タイトな例が存在 多分割カット問題 (アルゴリズム4.3に対するタイトな例) S2 S1 2-ε 2-ε 1 1 Sk 1 2-ε 2-ε 1 1 2-ε Sk-1 2-ε Sk-2 S3 多分割カット問題 (アルゴリズム4.3に対するタイトな例) k=4 の場合 S1 C1 S2 2-ε 2-ε 1 1 2-ε 1 1 2-ε 2-ε 2-ε S4 S3 多分割カット問題 (アルゴリズム4.3に対するタイトな例) k=4 の場合 S1 C1 S2 C2 2-ε 2-ε 1 C = C1 ∪C2 ∪C3 1 1 2-ε C4 S4 1 cost(C) = 3・(2-ε) = (k-1)・(2-ε) 2-ε C3 S3 多分割カット問題 (アルゴリズム4.3に対するタイトな例) k=4 の場合 S1 S2 2-ε 1 2-ε cost(A) = 4 = k 1 最適解 A 1 2-ε S4 1 2-ε S3 多分割カット問題 (アルゴリズム4.3に対するタイトな例) • 一般の k に対して、 cost(C) = (k-1)・(2-ε) 及び cost(A) = k が成り立つことがわかった。したがって、 cost(C) / cost(A) = (1–1/k)・(2–ε) = (2–2/k) –ε(1–1/k) となる。これは、アルゴリズム 4.3 が (2–2/k) より小さい近似 率を達成できないことを示している。 • (どんなに小さい正数δに対しても、近似率 (2–2/k) –δを達 成できたとすると、ε<δ/ (1–1/k) が成り立つようにεを取れ ば、上式により、cost(C) / cost(A) > (2–2/k) –δが成り立 つようなインスタンスを作ることができ、矛盾が生じる。) 多分割カット問題 (アルゴリズム4.3に対するタイトな例) • • アルゴリズム4.3 の近似保証は (2–2/k) であるこ とがわかった。 最後に、ナイーブなアルゴリズム(A)と(B)の近似 率について考察する。 A) どんどん分割型アルゴリズム B) 孤立カット-削除型アルゴリズム • アルゴリズム4.3 に対するタイトな例に対して、こ れらのアルゴリズムを適用してみる。 多分割カット問題 (A)どんどん分割型アルゴリズム k=4 の場合 S1 S2 2-ε 1 2-ε アルゴリズム4.3 と 1 1 同じ解が得られた 2-ε S4 1 2-ε S3 多分割カット問題 (B)孤立カット-削除型アルゴリズム k=4 の場合 S1 S2 2-ε 2-ε 1 1 2-ε 1 1 2-ε 2-ε 2-ε S4 S3 多分割カット問題 (B)孤立カット-削除型アルゴリズム k=4 の場合 S2 2-ε 1 1 2-ε 1 1 2-ε 2-ε S4 S3 多分割カット問題 (B)孤立カット-削除型アルゴリズム k=4 の場合 S1 S2 2-ε 1 2-ε アルゴリズム4.3 と 1 1 同じ解が得られた 2-ε S4 1 2-ε S3 多分割カット問題 (ナイーブなアルゴリズム(A)と(B)について) • アルゴリズム 4.3 に対するタイトな例に対して、ナ イーブなアルゴリズム(A)及び(B)を適用すると、 どちらもアルゴリズム 4.3 と同じ解を出力した。 • アルゴリズム(A)と(B)の近似率が解析できたとし ても、 (2–2/k) より良い近似率を得ることはできな い。 注:(A)に関しては、グリーディにカットしていくと、近似率 (2–2/k) が達成されると述べられている(演習問題 4.2)。 多分割カット問題(まとめ) • 多分割カット問題に対して、最小 s-t カットアルゴリ ズムを用いたナイーブなアルゴリズムが、(2–2/k) の近似率を保証していることがわかった。 • 多分割カット問題に対する、より良い近似保証を持 つアルゴリズムは存在するか? • 答え: 存在する ⇒ 第Ⅱ部 第19章にて解説 多分割カットと k-カット(目次) • (寄り道) 最小 s-t カット問題 • 多分割カット問題 • 最小 k-カット問題 最小 k-カット問題 • 自然数 k と、辺に重みを持つ連結なグラフ G が与 えられたとき、次の性質をもつ辺集合のうちで、重み の総和が最小となるものを求めよ: • その辺集合に属する辺をすべて取り除くと、グラフ G は、k 個の連結成分に分割される。 • このような辺集合を k-カット という。 最小 k-カット問題 多分割カット問題 S1 k=4 S2 S4 S3 最小 k-カット問題 最小 k-カット問題 • 最小 k-カット問題を解く多項式時間アルゴリズムは 存在するか? • 答え: たぶん存在しない 最小 k-カット問題は「NP困難」 P=NPでない限り、この問題を解く多項式時間 アルゴリズムは存在しない。 最小 k-カット問題 とにかく考えてみる 5 10 2 2 k=4 1 10 2 2 10 1 10 1 5 2 2 5 1 1 5 3 3 3 1 1 最小 k-カット問題 • やっぱりムリ • 第Ⅰ部の主旨: – NP困難な問題に対して、ナイーブなアルゴリズ ムの近似率を解析する。 ⇒ 最小の k-カットを求めることは諦めて、無駄はあ るかもしれないが、とりあえず k-カットとなる辺集合 を求める。 最小 k-カット問題 • ナイーブなアルゴリズム? • 多項式時間でできること: – 最小 s-t カットを求める – 最小孤立カットを求める – 多分割カット問題の (2-2/k) 近似解を求める • これらのアルゴリズムは、ターミナルの概念を含ん でいる。 ⇒ もっと道具が必要 最小 k-カット問題 • これからの道筋 – Gomory-Hu 木 – Gomory-Hu 木を用いた k-カットアルゴリズム – アルゴリズムの近似率解析 – タイトな例 Gomory-Hu 木 • G=(V,E) を重み付き連結グラフとする。このとき、 G の頂点上をわたる重み付きの木 T=(V,F) が G に対する Gomory-Hu 木であるとは、次の2つの 条件を満たすときである: 1. 任意の u,v∈V に対して、G の最小 u-v カット の重みと T の最小 u-v カットの重みが等しい。 2. T における辺 e∈F の重みは、e によって分割さ れる頂点集合を、G 上で分割する際のコスト (カットの重み)と等しい。 Gomory-Hu 木 G の頂点上をわたる木 T=(V,F) 重みつきグラフ G=(V,E) b c 4 5 10 2 a 2 3 d 4 2 8 7 f 3 e Gomory-Hu 木 G の頂点上をわたる木 T=(V,F) b c d a f e Gomory-Hu 木 G の頂点上をわたる木 T=(V,F) 重みつきグラフ G=(V,E) b c 4 5 10 2 a 2 3 d 4 2 8 7 f 3 もとのグラフ G に 無い辺があっても良い e Gomory-Hu 木 18 (10+8) b 1. 任意の u,v∈V に対して、G の最小 u-v カットの重みと T の最小 u-v カットの重みが等しい。 4 5 10 a c 2 3 8 b 7 c f 18 a d 17 15 14 13 f e d 2 4 2 3 e Gomory-Hu 木 1. 任意の u,v∈V に対して、G の最小 u-v カットの重みと T の最小 u-v カットの重みが等しい。 a b c 13 (4+2+2+3+2) b c 4 5 10 2 4 2 d 2 3 8 7 3 f e 18 a d 17 15 14 13 f e すべての頂点の組 (u,v) に対して成り 立つ Gomory-Hu 木 2. T における辺 e∈F の重みは、e に よって分割される頂点集合を、G 上 で分割する際のコスト(カットの重み) と等しい。 b a c 13 (4+2+2+3+2) b c 4 5 10 2 2 4 d 2 3 8 7 3 f e 18 a d 17 15 14 13 f e 辺 (f,e) に付随するカット Gomory-Hu 木 2. T における辺 e∈F の重みは、e に よって分割される頂点集合を、G 上 で分割する際のコスト(カットの重み) と等しい。 b a c 17 (4+2+3+8) b c 4 5 10 d 2 2 4 3 2 8 7 3 f e 18 a d 17 15 14 13 f e 辺 (b,f) に付随するカット すべての辺 e∈F に おいて成り立つ Gomory-Hu 木 • こんな都合の良い木が本当にあるのか? – 任意の重み付き連結グラフ G に対して、 Gomory-Hu 木 TG は必ず存在するのか? – 答え: 存在する(?) • Gomory-Hu 木を効率的に求めるアルゴリズムはあ るか? – 任意の重み付き連結グラフ G に対して、 Gomory-Hu 木 TG を構成する多項式時間アルゴリズムは存在するか? – 答え: 存在する(演習問題 4.6) Gomory-Hu 木を用いた k-カットアルゴリズム • 最小 k-カット問題: – グラフ G と自然数 k が与えられたとき、 G の k-カットの うちで、コスト最小のものを求めよ。 アルゴリズム 4.7 1. G に対する Gomory-Hu 木 TG を求める。 2. TG の n-1 個の辺のうち、重みの小さい方から k-1 個の 辺を選び出す。 3. 選び出された k-1 個の辺それぞれについて、付随する G のカットを求める。 4. 求まった k-1 個のカットの和集合 C を出力する。 n : G の頂点数 Gomory-Hu 木を用いた k-カットアルゴリズム 重み付き連結グラフ G k=3 b 4 5 10 a c 2 3 d 2 4 2 8 7 f 3 G に対する Gomory-Hu 木 TG e 1. G に対する Gomory-Hu 木 TG を求める。 b c 18 a 17 d 15 14 13 f e Gomory-Hu 木を用いた k-カットアルゴリズム 重み付き連結グラフ G k=3 b 4 5 10 a c 2 3 d 2 4 2 8 7 f 3 G に対する Gomory-Hu 木 TG e 2. TG の n-1 個の辺のうち、 重みの小さい方から k-1 個の辺を選び出す。 b c 18 a 17 d 15 14 13 f e Gomory-Hu 木を用いた k-カットアルゴリズム 重み付き連結グラフ G k=3 b 4 5 10 a c 2 3 d 2 4 2 8 7 f 3 G に対する Gomory-Hu 木 TG e 3. 選び出された k-1 個の辺 それぞれについて、付随 するG のカットを求める。 b c 18 a 17 d 15 14 13 f e Gomory-Hu 木を用いた k-カットアルゴリズム 重み付き連結グラフ G k=3 b 4 5 10 a c 2 3 d 2 4 2 8 7 f 3 G に対する Gomory-Hu 木 TG e 3. 選び出された k-1 個の辺 それぞれについて、付随 するG のカットを求める。 b c 18 a 17 d 15 14 13 f e Gomory-Hu 木を用いた k-カットアルゴリズム 重み付き連結グラフ G k=3 b 4 5 10 a ちょうど3つの連結 成分に分割された c 2 3 d 2 4 2 8 7 f 3 G に対する Gomory-Hu 木 TG e 4. 求まった k-1 個のカットの 和集合 C を出力する。 b c 18 a 17 d 15 14 13 f e 注意! • 一般に、連結グラフ G における k-1 個のカットの和 集合は、G をちょうど k 個の連結成分に分割する か? • 答え: しない 連結グラフ G 連結グラフ G ② ① ② ③ ① ③ ④ さらに注意! • 一般に、連結グラフ G における k-1 個のカットの和 集合は、G を k 個以上の連結成分に分割するか? 連結グラフ G 連結グラフ G さらに注意! • 一般に、連結グラフ G における k-1 個のカットの和 集合は、G を k 個以上の連結成分に分割するか? • 答え: しない 4個のカット 4個の連結成分 アルゴリズム 4.7 の問題点 • アルゴリズム 4.7: – G の k-1 個のカットの和集合 C を出力。 – しかし、C が G を k 個の連結成分に分割する保証は無 い。 • 次のことを証明する必要があった(補題4.6): – 重み付き連結グラフ G に対する Gomory-Hu 木を TG と する。このとき、TG の ℓ 個の辺に付随する G のカットの 和集合 S は G を ℓ +1 個以上の連結成分に分割する。 アルゴリズム 4.7 の問題点 (補題 4.6 の証明) • 補題 4.6 を証明するためには、次のことを考えれば よい: • 任意の木は、ℓ 個の辺を取り除くと、 ℓ +1 個の連結 成分に分割される。 アルゴリズム 4.7 の問題点 (補題 4.6 の証明) • Gomory-Hu 木 TG は、ℓ 個の辺を取り除くと、 ℓ +1 個の連 結成分に分割される。 • 分割された TG の連結成分の頂点集合をそれぞれ V1,V2,…,Vℓ +1 とする。 4.7 により得られる • グラフ Gアルゴリズム においても、対応する頂点集合は、辺に付随する カットによって分割される。 k-1 個のカットの和集合は、必ず b グラフ 4 5 10 a b c k 個以上に分割する Gを 2 3 8 18 d a 2 4 2 17 7 f 3 e 重み付き連結グラフ G c d 15 14 13 f e G に対する Gomory-Hu 木 TG アルゴリズム 4.7 の問題点 (補題 4.6 の証明) • グラフ G の頂点上をわたる木を考えると、これらの カットのうち、必ず一つは、二つ以上の辺をまたぐも のとなっている。 この4つが選ばれ たときに、和集合 は、G を4つの連 結成分にしか分割 しなかった。 このカットは、アル ゴリズムでは選ば れない アルゴリズム 4.7 の問題点 (補題 4.6 の証明) • 以上により、アルゴリズム 4.7 で得られる k-1 個の カットの和集合 C は、グラフ G を k 個以上の連結 成分に分割することが分かった。 • ちょうど k 個の連結成分にしたいなら、適当な辺を 戻してやればよい。 • 次は、アルゴリズム 4.7 が近似率 (2-2/k) を達成す ることを証明する。 • k+1 個以上の連結成分に分割されていたとしても、 C のコストは最適解コストの (2-2/k) 倍以下に抑え られる。 最小 k-カット問題 (アルゴリズム4.7の近似率) 最小 k-カットを A とする。 最適解 A cost(C)≦(2-2/k)cost(A)? 最小 k-カット問題 (アルゴリズム4.7の近似率) • 証明のアイデア: cost(C) ≦ ∑1≦i≦k-1 cost(fi ) TG の辺コストの小さいほうから k-1 個 ≦ ∑1≦i≦k-1 cost(bi ) ある性質を満たす TG の辺 (k-1 個) ≦ ∑1≦i≦k cost(Ai ) - cost(Amax) ≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai ) = (1-1/k) ・ ∑1≦i≦k cost(Ai ) = (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A) 最小 k-カット問題 (アルゴリズム4.7の近似率) 最小 k-カットを A とする。 最適解 A A2 A3 V2 V1 A1 V3 V5 V4 A5 A4 最小 k-カット問題 (アルゴリズム4.7の近似率) • Ai の直和集合には、 A の要素が2つづつ含まれる。 • つまり、A = {e1, e2, … , em } とおくと、 ∑1≦i≦k Ai = {e1, e1, e2, e2, … , em , em } となる。 • したがって、 Ai のコストの総和は、 A のコストの2 倍となる。すなわち、 ∑1≦i≦k cost(Ai ) = 2・cost(A) が成り立つ。 最小 k-カット問題 (アルゴリズム4.7の近似率) • 証明のアイデア: cost(C) ≦ ∑1≦i≦k-1 cost(fi ) TG の辺コストの小さいほうから k-1 個 ≦ ∑1≦i≦k-1 cost(bi ) ある性質を満たす TG の辺 (k-1 個) ≦ ∑1≦i≦k cost(Ai ) - cost(Amax) ≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai ) = (1-1/k) ・ ∑1≦i≦k cost(Ai ) = (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A) 最小 k-カット問題 (アルゴリズム4.7の近似率) • 証明のアイデア: cost(C) ≦ ∑1≦i≦k-1 cost(fi ) TG の辺コストの小さいほうから k-1 個 ≦ ∑1≦i≦k-1 cost(bi ) ある性質を満たす TG の辺 (k-1 個) ≦ ∑1≦i≦k cost(Ai ) - cost(Amax) ≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai ) = (1-1/k) ・ ∑1≦i≦k cost(Ai ) = (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A) 最小 k-カット問題 (アルゴリズム4.7の近似率) • cost(C) ≦ ∑1≦i≦k-1 cost(fi ) f1 ~ fk-1 : TG の辺コストの小さいほうから k-1 個 – C は、 TG の辺コストの小さいほうから k-1 個選び、それぞ れに付随する G のカットの和集合をとったもの – Gomory-Hu 木の性質2より、 TG の辺コストと、それに付 随する G のカットのコストは同じ – したがって成り立つ Gomory-Hu 木を用いた k-カットアルゴリズム 重み付き連結グラフ G k=3 b 4 cost(C)=25≦13+14=27 14 c Gomory-Hu 木の性質2から、そ れぞれの辺に付随するカットのコ ストは一致する。 5 10 a 13 2 3 d 2 4 2 8 7 f 3 G に対する Gomory-Hu 木 TG e b c 18 この辺が両方のカット に含まれている a 17 d 15 14 13 f e 最小 k-カット問題 (アルゴリズム4.7の近似率) • 証明のアイデア: cost(C) ≦ ∑1≦i≦k-1 cost(fi ) TG の辺コストの小さいほうから k-1 個 ≦ ∑1≦i≦k-1 cost(bi ) ある性質を満たす TG の辺 (k-1 個) ≦ ∑1≦i≦k cost(Ai ) - cost(Amax) ≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai ) = (1-1/k) ・ ∑1≦i≦k cost(Ai ) = (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A) 最小 k-カット問題 (アルゴリズム4.7の近似率) • ∑1≦i≦k-1 cost(fi ) ≦ ∑1≦i≦k-1 cost(bi ) f1~fk-1 : TG の辺コストの小さいほうから k-1 個 b1~bk-1 : ある性質を満たす T の辺 (k-1 個) • bi が TG の辺である限り、 bi のコストの総和は fi の コストの総和を超えてしまう。 b b c 18 a c 18 17 d a 15 14 13 f 17 e d 15 14 13 f e 最小 k-カット問題 (アルゴリズム4.7の近似率) • 証明のアイデア: cost(C) ≦ ∑1≦i≦k-1 cost(fi ) TG の辺コストの小さいほうから k-1 個 ≦ ∑1≦i≦k-1 cost(bi ) ある性質を満たす TG の辺 (k-1 個) ≦ ∑1≦i≦k cost(Ai ) - cost(Amax) ≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai ) = (1-1/k) ・ ∑1≦i≦k cost(Ai ) = (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A) 最小 k-カット問題 (アルゴリズム4.7の近似率) • ∑1≦i≦k-1 cost(bi ) ≦ ∑1≦i≦k cost(Ai ) - cost(Amax) b1~bk-1 : ある性質を満たす TG の辺 (k-1 個) • ある性質とは、任意の i (1≦i≦k-1) に対して cost(bi ) ≦ cost(Ai ) が成り立つことである。ただし、 Ak = Amax とする。 • このような bi が存在するかどうかは、後で議論する。 最小 k-カット問題 (アルゴリズム4.7の近似率) • 証明のアイデア: cost(C) ≦ ∑1≦i≦k-1 cost(fi ) TG の辺コストの小さいほうから k-1 個 ≦ ∑1≦i≦k-1 cost(bi ) ある性質を満たす TG の辺 (k-1 個) ?≦ ∑1≦i≦k cost(Ai ) - cost(Amax) ≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai ) = (1-1/k) ・ ∑1≦i≦k cost(Ai ) = (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A) 最小 k-カット問題 (アルゴリズム4.7の近似率) • Amax のコスト は、Ai のコストの総和の平均以上で ある。すなわち、 cost(Amax) ≧ 1/k ・∑1≦i≦k cost(Ai ) が成り立つ。 平均 最小 k-カット問題 (アルゴリズム4.7の近似率) • Amax のコスト は、Ai のコストの総和の平均以上で ある。すなわち、 cost(Amax) ≧ 1/k ・∑1≦i≦k cost(Ai ) が成り立つ。したがって、 ∑1≦i≦k cost(Ai ) ー cost(Amax) ≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai ) = (1-1/k) ・ ∑1≦i≦k cost(Ai ) 最小 k-カット問題 (アルゴリズム4.7の近似率) • 証明のアイデア: cost(C) ≦ ∑1≦i≦k-1 cost(fi ) TG の辺コストの小さいほうから k-1 個 ≦ ∑1≦i≦k-1 cost(bi ) ある性質を満たす TG の辺 (k-1 個) ?≦ ∑1≦i≦k cost(Ai ) - cost(Amax) ≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai ) = (1-1/k) ・ ∑1≦i≦k cost(Ai ) = (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A) 最小 k-カット問題 (アルゴリズム4.7の近似率) • ∑1≦i≦k-1 cost(bi ) ≦ ∑1≦i≦k cost(Ai ) - cost(Amax) b1~bk-1 : ある性質を満たす TG の辺 (k-1 個) • ある性質とは、任意の i (1≦i≦k-1) に対して cost(bi ) ≦ cost(Ai ) が成り立つことである。ただし、 Ak = Amax とする。 • このような bi が存在するかどうかは、後で議論する。 最小 k-カット問題 (アルゴリズム4.7の近似率) • これから示すこと: • Gomory-Hu 木 TG には、 任意の i (1≦i≦k-1) に対 して、 cost(bi ) ≦ cost(Ai ) が成り立つような、 k-1 個の辺 b1, b2, …, bk-1 が存 在する。 最適解 A A2 ただし、 Ai は最適解 A から A3 V2 得られる G のカットであり、 V1 V3 Ak は最大コストとする。 V V A1 5 4 A5 A4 最小 k-カット問題 (アルゴリズム4.7の近似率) 最適解によってカットされる Gomory-Hu 木の辺に 注目する 最適解 A V2 V1 V3 V5 V4 この辺集合 を B とおく 最小 k-カット問題 (アルゴリズム4.7の近似率) 各 Vi を一つの頂点として見る 最適解 A V2 V1 V3 V5 V4 この辺集合 を B とおく 最小 k-カット問題 (アルゴリズム4.7の近似率) 各 Vi を一つの頂点として見る 最適解 A V2 V1 V3 V5 V4 この辺集合 を B とおく 最小 k-カット問題 (アルゴリズム4.7の近似率) このグラフが木となるように、B の中から辺を選ぶ 最適解 A V2 V1 V3 V5 V4 この辺集合 を B’ とおく 最小 k-カット問題 (アルゴリズム4.7の近似率) Ai のコストが最大となるような Vi を根として、 木を有向化する 最適解 A A2 A3 V2 V1 A1 V3 V5 この辺集合 を B’ とおく V4 最大 A5 A4 最小 k-カット問題 (アルゴリズム4.7の近似率) Ai のコストが最大となるような Vi を根として、 木を有向化する 最適解 A V2 V1 V3 V5 最大 V4 この辺集合 を B’ とおく 最小 k-カット問題 (アルゴリズム4.7の近似率) 各 Vi から出る辺を bi と名付ける 最適解 A V2 b2 V1 b3 V3 b4 b1 V5 最大 V4 この辺集合 を B’ とおく 最小 k-カット問題 (アルゴリズム4.7の近似率) 各 Vi から出る辺を bi と名付ける 最適解 A V2 V1 V3 V5 最大 V4 最小 k-カット問題 (アルゴリズム4.7の近似率) これらの bi は、Gomory-Hu 木の辺であった 最適解 A V1 b2 V2 V5 最大 最適解 A b3 V3 b4 b1 Gomory-Hu 木 V4 b3 b2 b1 b4 最小 k-カット問題 (アルゴリズム4.7の近似率) これらの bi は、Gomory-Hu 木の辺であった Gomory-Hu 木 最適解 A b3 b2 b1 b4 最小 k-カット問題 (アルゴリズム4.7の近似率) Gomory-Hu 木の性質1に注目: 任意の u,v∈V に対して、G の最小 u-v カットの重みと TG の最小 u-v カットの重みが等しい。 最適解 A b1 の重みは、G の 最小 u-v カットの コストに等しい u b3 b2 b1 A1 A1 は、G における u-v カット v b4 最小 k-カット問題 (アルゴリズム4.7の近似率) • cost(b1) = G における最小 u-v カットのコスト • A1 は G における u-v カットの一つである • 最小 u-v カットのコスト ≦ u-v カットのコスト ⇒cost(b1) ≦ cost(A1) • 同様のことが、他の bi に対しても成り立つ。 • したがって、任意の i (1≦i≦k-1) に対して、 cost(bi) ≦ cost(Ai) が成り立つ。 最小 k-カット問題 (アルゴリズム4.7の近似率) • 以下のことが示された: • Gomory-Hu 木 TG には、 任意の i (1≦i≦k-1) に対 して、 cost(bi ) ≦ cost(Ai ) が成り立つような、 k-1 個の辺 b1, b2, …, bk-1 が存 在する。 最適解 A A2 ただし、 Ai は最適解 A から A3 V2 得られる G のカットであり、 V1 V3 Ak は最大コストとする。 V V A1 5 4 A5 A4 最小 k-カット問題 (アルゴリズム4.7の近似率) • ∑1≦i≦k-1 cost(bi ) ≦ ∑1≦i≦k cost(Ai ) - cost(Amax) b1~bk-1 : ある性質を満たす TG の辺 (k-1 個) • ある性質とは、任意の i (1≦i≦k-1) に対して cost(bi ) ≦ cost(Ai ) が成り立つことである。ただし、 Ak = Amax とする。 • このような bi が存在することが示された。 最小 k-カット問題 (アルゴリズム4.7の近似率) • 証明のアイデア: cost(C) ≦ ∑1≦i≦k-1 cost(fi ) TG の辺コストの小さいほうから k-1 個 ≦ ∑1≦i≦k-1 cost(bi ) ある性質を満たす TG の辺 (k-1 個) ≦ ∑1≦i≦k cost(Ai ) - cost(Amax) ≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai ) = (1-1/k) ・ ∑1≦i≦k cost(Ai ) = (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A) 最小 k-カット問題 (アルゴリズム4.7の近似率) cost(C) ≦ (2-2/k) ・cost(A) • アルゴリズム4.7によって得られた解のコストは、最 適解のコストの (2-2/k) 倍以下となることがわかっ た。 • アルゴリズム4.7の近似率は、これ以上改善されな いのか? • 答え: されない ∵ タイトな例が存在 最小 k-カット問題 (アルゴリズム4.7に対するタイトな例) k=K に対して、 頂点数が 2K と なるようにとる 2-ε 2-ε 1 1 1 2-ε 2-ε 1 1 2-ε 2-ε 最小 k-カット問題 (アルゴリズム4.7に対するタイトな例) k=4 の場合 2-ε 2-ε 2-ε 1 1 2-ε 1 1 2 2-ε 重み付き連結グラフ G 2-ε 2 2-ε 2 2-ε G に対する Gomory-Hu 木 TG cost(C) = 3・(2-ε) = (k-1)・(2-ε) 最小 k-カット問題 (アルゴリズム4.7に対するタイトな例) k=4 の場合 2-ε 1 2-ε cost(A) = 4 = k 1 最適解 A 1 2-ε 1 2-ε 最小 k-カット問題 (アルゴリズム4.7に対するタイトな例) • 一般の k に対して、 cost(C) = (k-1)・(2-ε) 及び cost(A) = k が成り立つことがわかった。したがって、 cost(C) / cost(A) = (1–1/k)・(2–ε) = (2–2/k) –ε(1–1/k) となる。これは、アルゴリズム 4.7 が (2–2/k) より小さい近似 率を達成できないことを示している。 • (どんなに小さい正数δに対しても、近似率 (2–2/k) –δを達 成できたとすると、ε<δ/ (1–1/k) が成り立つようにεを取れ ば、上式により、cost(C) / cost(A) > (2–2/k) –δが成り立 つようなインスタンスを作ることができ、矛盾が生じる。) 最小 k-カット問題(まとめ) • 最小 k-カット問題に対して、Gomory-Hu 木を用い たアルゴリズムが、(2–2/k) の近似率を保証してい ることがわかった。 • 最小 k-カット問題に対する、より良い近似保証を持 つアルゴリズムは存在するか? • 答え: ????
© Copyright 2024 ExpyDoc