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

近似アルゴリズム (Approximation Algorithms)