近似アルゴリズム (pproximation agorithms).pptVIP

近似アルゴリズム(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 の極大性に反する。 個数版点カバー問題に対する近似アルゴリズム 極大マッチングの端点でカバーされない辺があると、その辺はマッチングに付け加えることができる 個数版点カバー問題に対する近似アルゴリズム アルゴリズム1.2で出力される点カバーのコストは、最小点カバーのコストの2倍以内に抑えられる。 証明： どの極大マッチングの辺数も、最小点カバーのコストより小さい（点カバーは極大マッチングの辺をすべてカバーしているから）　?　|M| ≦ OPT 出力される点カバーのコストは、 2|M| したがって、 2|M| ≦ 2OPT より、出力される点カバーのコストは 2OPT 以下。 近似保証について ポイント： 一般に、ＮＰ最適化問題において、最適解のコスト OPT を求めるのは難しい。 しかし、近似保証を与えるには、 OPT のα倍以内に収まるということを示さなければならない。 そこで、 OPT よりも小さいことが保証されている値（下界）を用いて近似保証することが多い。 ここでは、マッチングの辺数 |M| が OPT より必ず小さくなることを利用した。すなわち、 |M| が OPT の下界であることを利用したのである。 個数版点カバー