近似アルゴリズム (Approximation Algorithms) Ｖ．Ｖ．ヴァジラーニ（著） 浅野孝夫（訳） はじめに 逆説的に感じるかもしれないが、厳密な科学 はすべて近似の概念に支配されている。 ― Bertrand Russell はじめに • 我々の出会う最適化問題の多くは、ＮＰ困難である ことが多く、現実的な時間で解を得ることはできない （と広く信じられている）。 • だからといって、解を求めるのを諦めてしまうわけに はいかない。 • 二つの方法 – インスタンスの領域を狭くして、その中での効率的なアル ゴリズムを使う。 – 最適性を捨て、近似解を求める効率的なアルゴリズムを 使う。 ⇒ 「近似アルゴリズム」の研究分野の発達 はじめに • この本の内容 第一部 重要な問題とそれに対する近似アルゴリズム 第二部 近似アルゴリズムの系統的設計技法 第三部 その他の重要なトピック 第一章 はじめに 作： 牧山幸史 はじめに • この章の目的： – 実際の問題を通して、近似アルゴリズムの考え 方について学ぶ 最適化問題と近似アルゴリズム • 最適化問題とは、解空間（実行可能領域）とコスト関 数（目的関数）が与えられたとき、コストが最小、ま たは最大になるような解を求めよという形式の問題 のこと。 • 多くの場合、最適化問題はＮＰ困難であり、現実的 な時間で解を求めることはできない（と考えられてい る）。 • 近似アルゴリズムとは、このような問題に対して、最 適である保証はないが、最適に近い解を求めるとい う保証を持ったアルゴリズムのことである。 近似率（近似保証） • 最適に近い解であるという保証はどのようになされ るか？ • 「この近似アルゴリズムで求まる解は、必ず最適解 のコストのα倍に収まる」ということを証明する。 • このとき、αを近似率または近似保証といい、近似 率αを持つ近似アルゴリズムをα近似アルゴリズムと いう。 個数版点カバー問題 • 本章では、個数版点カバー問題に対して、２近似ア ルゴリズムを与える。 • 点カバー問題（ｐ1）： – 無向グラフ G=(V,E)，各点へのコスト関数 c:V→Q+ が入力として与えられて、最小コストの 点カバーを求める問題。点カバーとは、 G=(V,E) のどの辺に対しても少なくとも一方の 端点を含むような点集合 V’⊆V のことをいう。 – 点カバー問題の特別な場合で、どの点のコストも １であるとき、個数版点カバー問題と呼ばれる。 個数版点カバー問題 点カバーとは、すべての 辺をカバーする頂点集合 のことである コスト４の点カバーが 得られた 個数版点カバー問題 • 個数版点カバー問題を解く多項式時間アルゴリズ ムは存在するか？ • 答え： たぶん存在しない 個数版点カバー問題は「ＮＰ困難」 Ｐ＝ＮＰでない限り、この問題を解く多項式時間 アルゴリズムは存在しない。 個数版点カバー問題に対する 近似アルゴリズム • 近似アルゴリズムを考える。 • アルゴリズム1.2（ｐ3）： – G の極大マッチング M を求めて、マッチング M の辺の端点からなる集合を点カバーとして出力 する • マッチングとは、グラフに含まれる独立な辺の集合 のことであり、極大マッチングとは、それ以上辺を付 け加えるとマッチングではなくなってしまうマッチング のことである。 極大マッチング マッチングとは、グラフに 含まれる独立な辺の集合 のことである 独立とは、共通の頂点を 持たないという意味 辺をこれ以上選ぶことが できない→極大マッチング 個数版点カバー問題に対する 近似アルゴリズム • アルゴリズム1.2（ｐ3）： – G の極大マッチング M を求めて、マッチ ング M の辺の端点 からなる集合を点カ バーとして出力する 個数版点カバー問題に対する 近似アルゴリズム • アルゴリズム1.2の出力は点カバーになっている。 • 証明： – 出力された点集合でカバーされないような辺は1 つもない。あったとすると、そのような辺はマッチ ング M に付け加えることができて、 M の極大性 に反する。 個数版点カバー問題に対する 近似アルゴリズム • 極大マッチング の端点でカバー されない辺があ ると、その辺は マッチングに付 け加えることが できる グラフ G 極大マッチング 個数版点カバー問題に対する 近似アルゴリズム • アルゴリズム1.2で出力される点カバーのコストは、 最小点カバーのコストの2倍以内に抑えられる。 • 証明： – どの極大マッチングの辺数も、最小点カバーのコ ストより小さい（点カバーは極大マッチングの辺を すべてカバーしているから） ⇒ |M| ≦ OPT – 出力される点カバーのコストは、 2|M| – したがって、 2|M| ≦ 2OPT より、出力される点 カバーのコストは 2OPT 以下。 近似保証について • ポイント： – 一般に、ＮＰ最適化問題において、最適解のコス ト OPT を求めるのは難しい。 – しかし、近似保証を与えるには、 OPT のα倍以 内に収まるということを示さなければならない。 – そこで、 OPT よりも小さいことが保証されている 値（下界）を用いて近似保証することが多い。 – ここでは、マッチングの辺数 |M| が OPT より必 ず小さくなることを利用した。すなわち、 |M| が OPT の下界であることを利用したのである。 個数版点カバー問題の 近似保証の改善 • 個数版点カバー問題に対して、アルゴリズム1.2 が２近似アルゴリズムであることを示した。 1. アルゴリズム1.2の近似保証は、よりよい解析を 用いれば改善できるか？ 2. 極大マッチングの辺数を下界として用いる方法 で、よりよい近似保証を持つアルゴリズムが設 計可能か？ 3. 点カバー問題に対して、よりよい近似保証を持 つアルゴリズムは存在するか？ 個数版点カバー問題の 近似保証の改善 1. アルゴリズム1.2の近似保証は、よりよい解析を用 いれば改善できるか？ 答え： できない • タイトな例が存在する • タイトな例とは、α近似アルゴリズムに対して、出力 される解のコストが、最適解のコストのちょうどα倍 となるようなインスタンスのことである。 • すなわち、タイトな例を入力すると、最適解のコス ト OPT に対し、αOPT のコストを持つ解が出力さ れる。 アルゴリズム1.2の 近似保証2に対するタイトな例 • 完全二部グラフ Kn,n n ・ ・ ・ ・ ・ ・ • アルゴリズム 1.2による出力 のコスト ＝ 2n • 最適解のコスト OPT ＝ n 個数版点カバー問題の 近似保証の改善 2. 極大マッチングの辺数を下界として用いる方法で、 よりよい近似保証を持つアルゴリズムが設計可能 か？ 答え できない • 極大マッチングの辺数 ≦ 最適点カバーのコスト という不等式の両辺の比が、２となるようなインス タンスが存在する。極大マッチングの辺数を下界 として用いる場合、このようなインスタンスに対して 近似率２以下のアルゴリズムは作れない。 個数版点カバー問題の 近似保証の改善 • n を奇数としたときの n 点の完全グラフ Kn • 極大マッチングの辺数 ＝ (n-1)/2 • 最小点カバーのコスト ＝ n-1 個数版点カバー問題の 近似保証の改善 3. 点カバー問題に対して、よりよい近似保証を持つ アルゴリズムは存在するか？ 未解決 個数版点カバー問題の 近似保証の改善 • 個数版点カバー問題に対して、アルゴリズム1.2 が２近似アルゴリズムであることを示した。 1. アルゴリズム1.2の近似保証は、よりよい解析を 用いれば改善できるか？ できない 2. 極大マッチングの辺数を下界として用いる方法 で、よりよい近似保証を持つアルゴリズムが設 計可能か？ できない 3. 点カバー問題に対して、よりよい近似保証を持 つアルゴリズムは存在するか？ 未解決
© Copyright 2024 ExpyDoc
