第二章 集合カバー

第二章 集合カバー(その2)
作: 牧山幸史
これまでのあらすじ
•
•
•
•
現実で遭遇する最適化問題の多くは「NP困難」
厳密解を求めるのに、膨大な計算時間が必要
近似解ならば、求めることができるかも。
個々の問題に対する近似アルゴリズムを調査する
(第Ⅰ部):
第1章: 個数版点カバー問題
(近似率2)
第2章: 集合カバー問題
第二章 集合カバー(目次)
• 集合カバー問題(グリーディアルゴリズム)
• 重み付き点カバー問題(層別化)
• 最短拡大ストリング問題
重み付き点カバー問題
• ここでは、重み付き点カバー問題に対して、層別化
を用いた2近似アルゴリズムを与える。
• 重み付き点カバー問題(p1):
– 無向グラフ G=(V,E),各点へのコスト関数
w:V→Q+ が入力として与えられて、最小コスト
の点カバーを求める問題。点カバーとは、
G=(V,E) のどの辺に対しても少なくとも一方の
端点を含むような点集合 V’⊆V のことをいう。
重み付き点カバー問題
2
3
4
点カバーとは、すべての
辺をカバーする頂点集合
のことである
3
2
コスト9の点カバーが
得られた
1
2
層別化によるアルゴリズム設計
• アイデア:与えられたグラフの点集合の重み関数を、
次数重み付き関数に分割する。
• 次数重み付き関数:
– w:V→Q+ を点集合上の重み関数とするとき、
各点 v ∈ V の重み w(v) が、ある定数 c を用い
て w(v) = c・deg(v) と表されるとき、 w を次数
重み付き関数という。
次数重み付き関数
• 次数重み付き関数は、次のようなよい性質を持つ。
• w:V→Q+ が次数重み付き関数ならば、
w(V) ≦ 2・OPT が成り立つ。
• 証明:
– c を w(v) = c・deg(v) を満たす定数とし、U を
G の最適点カバーとする。 U はすべての辺をカ
バーするので、∑v∈U deg(v) ≧ |E| が成り立ち、
したがって、 OPT = w(U) ≧ c|E| となる。一方、
∑v∈V deg(v) = 2|E| であり、 w(V)=2c|E| で
あるので、証明された。
次数重み付き点カバー問題
2
4
4
2
次数重み付き関数ならば
すべての点を選んでも、
コストは OPT の高々2倍
2
2
4
1
4
2
層別化アルゴリズム
•
c = min{w(v)/deg(v)}
•
•
1.
2.
3.
4.
5.
6.
t(v) = c・deg(v)
w’(v) = w(v) – t(v)
(最大次数重み付き関数)
(残余重み付き関数)
i=0, G0=G, w0=w
Di = { v∈Gi| deg(v)=0 } とおく。
Gi – Di, w0 に対して c, t, w’ を計算する。
Wi = { v∈Gi – Di | w’(v)=0 }
Gi+1 = Gi – (Wi∪Di), wi+1=w’, i=i+1
Gi の点がすべて次数 0 になったら終了。出力は
C=W0∪・・・∪Wi-1, そうでなければ 2. に戻る。
層別化アルゴリズム
1.0
0.75
3
2
c = min{w(v)/deg(v)}
t(v) = c・deg(v)
0.5
4
3
2
2.0
1
0.25
1.5
1.0
2
層別化アルゴリズム
0.5
1.0
3
2
c = min{w(v)/deg(v)}
t(v) = c・deg(v)
w’(v) = w(v) – t(v)
1.0
4
3
2
0.5
1
1.0
0.5
0.5
2
層別化アルゴリズム
1.5
2
2.0
3.5
4
2.5
1.0
2
0
c = min{w(v)/deg(v)}
t(v) = c・deg(v)
w’(v) = w(v) – t(v)
G1
1.5
層別化アルゴリズム
0.75
0.75
2.0
3.5
4
3.5
c = 0.33..
1.5
2
c = min{w(v)/deg(v)}
t(v) = c・deg(v)
w’(v) = w(v) – t(v)
0.33..
2.5
1.0
2
1.25
1.5
1.5
G1
層別化アルゴリズム
0.66..
1.0
1.5
2
2.0
3.5
4
0.33..
c = 0.33..
c = min{w(v)/deg(v)}
t(v) = c・deg(v)
w’(v) = w(v) – t(v)
1.0
2.5
1.0
2
0.66..
0.33..
1.5
G1
層別化アルゴリズム
1.0
3.166..
4
0.833..
2 c = min{w(v)/deg(v)}
t(v) = c・deg(v)
w’(v) = w(v) – t(v)
1.833..
0
G2
c = 0.33..
1.166..
層別化アルゴリズム
0.4266..
0.5
1.0
3.166..
4
3.166..
c = 0.4266..
0.833..
2 c = min{w(v)/deg(v)}
t(v) = c・deg(v)
w’(v) = w(v) – t(v)
1.833..
1.833..
G2
次数0になったので
1.166.. 切り捨て
層別化アルゴリズム
0.833..
0.833..
1.0
3.166..
4
0.4266..
c = 0.4266..
0.833..
2 c = min{w(v)/deg(v)}
t(v) = c・deg(v)
w’(v) = w(v) – t(v)
1.833..
0.4266..
G2
層別化アルゴリズム
0.166..
2.74
4
0
c = min{w(v)/deg(v)}
t(v) = c・deg(v)
w’(v) = w(v) – t(v)
1.4066..
G3
c = 0.4266..
層別化アルゴリズム
0.166..
0.166..
2.74
4
2.74
c = min{w(v)/deg(v)}
0.166.. t(v) = c・deg(v)
w’(v) = w(v) – t(v)
0.166
2.74
1.4066..
0.166
0
c = 0.166..
2.5733..
点がすべて次数0に
なったので終了
層別化アルゴリズム
2
3
4
出力として出されるのは
アルゴリズムの途中で
重みが0になった頂点
3
2
1
2
層別化アルゴリズム
Gk
Gk-1
Di : 次数が0になった頂点
Wi : 重みが0になった頂点
Dk
Wk-1
Dk-1
・
・
・
G1
W1
G0 W0
(=G)
出力 C = W0∪・・・∪Wk-1
G – C = D0∪・・・∪Dk
D1
D0
層別化アルゴリズムの解析
•
層別化アルゴリズムは重み付き点カバー問題に
対して、近似保証 2 を達成する。
• 証明:
1. 出力 C は G の点カバーである
2. w(C) ≦ 2・OPT
の順で説明する。
層別化アルゴリズムの解析
1. 出力 C は G の点カバーである
– もし、C が G の点カバーでないとすると、ある i,
j に対して u∈Di かつ v∈Dj となる (u, v) が存
在することになる。仮に i≦j とすると、(u, v) は
Gi に存在することになり、 u が次数0の点であ
ることに反する。 j≦i のときも同様。したがって、
C は G の点カバーである。
層別化アルゴリズムの解析
2. w(C) ≦ 2・OPT の証明(前半)
– C* を最適な点カバーとし、 w(C) ≦ 2・w(C*)
となることを証明する。
– アルゴリズムの各繰り返しで得られる t を順番
に t0, t1, ..., tk-1 と表すことにする。
– 点 v∈C に対して、v∈Wj とすると、
w(v)=∑i≦jti(v) が成り立つ。
– 点 v∈G–C に対して、v∈Dj とすると、
w(v)>∑i<jti(v) が成り立つ。
層別化アルゴリズムの解析
2. w(C) ≦ 2・OPT の証明(後半)
– ところで、各 i に対して、C∩Gi =Wi∪・・・∪Wk-1 お
よび C*∩Gi は点カバーである。
– よって、t が次数重み付き関数であることから、
ti(C∩Gi) ≦ ti(Gi) ≦ 2・OPT ≦ 2・ti(C*∩Gi )
が成り立つ。
– したがって、
w(C) = ∑i=0k-1ti(C∩Gi)
≦ 2・∑i=0k-1ti(C*∩Gi) ≦ 2・w(C*)
重み付き点カバー問題の
近似保証の改善
•
重み付き点カバー問題に対して、層別化アルゴリ
ズムが 2 近似アルゴリズムであることを示した。
1. 層別化アルゴリズムの近似保証は、よりよい解
析を用いれば改善できるか?
答え: できない ⇒ タイトな例が存在する
2. 重み付き点カバー問題に対して、よりよい近似
保証を持つアルゴリズムは存在するか?
層別化アルゴリズムの
近似保証2に対するタイトな例
n
1
1
1
1
1
1
・
・
・
・
・
・
1
1
• すべての点の
重みが1の完全
二部グラフ Kn,n
• アルゴリズムに
よる出力のコス
ト = 2n
• 最適解のコスト
OPT = n
重み付き点カバー問題の近似保証の改善
•
重み付き点カバー問題に対して、層別化アルゴリ
ズムが 2 近似アルゴリズムであることを示した。
1. 層別化アルゴリズムの近似保証は、よりよい解
析を用いれば改善できるか?
答え: できない ⇒ タイトな例が存在する
2. 重み付き点カバー問題に対して、よりよい近似
保証を持つアルゴリズムは存在するか?
答え: ????
第二章 集合カバー(目次)
• 集合カバー問題(グリーディアルゴリズム)
• 重み付き点カバー問題(層別化)
• 最短拡大ストリング問題