実践的アルゴリズム(2010年9月15日・於金沢大学)
上原隆平
uehara@jaist.ac.jp
http://www.jaist.ac.jp/~uehara/に “上原
上原 折り紙”
折り紙 でもOK!
も1

困難な問題に対する挑戦• （計算機で解きたい）困難な問題は計算機 解きた
難な– 解答の妥当性は、ある程度わかる
解答 妥当性は、ある程度わ る– 可能な選択肢が爆発的に大きくて手に負えない– 理論的なモデルでは• 最悪の場合の計算量の下界を与える• 正確な解を求める• 入力サイズが大きくなったときの漸近的なふるまい

を す とが多を示すことが多い
もう少しなんとかしたい！！

2/40

困難な問題に対する挑戦• （計算機で解きたい）困難な問題は– 理論的なモデルでは• 最悪の場合の計算量の下界を与える• 正確な解を求める• 入力サイズが大きくなったときの漸近的なふるまいを示すことが多い

もう少しなんとかしたい！！
• 最近のトレンド：

乱択アルゴリズム– ランダム性を使って平均的なふるまいを考える
近似アルゴリズム– 正解からの誤差を許した計算を考える– （指数時間かけてでも、ある程度の規模の問題を解く）
3/40

困難な問題に対する挑戦• （計算機で解きたい）困難な問題は– 理論的なモデルでは– 最近のトレンド：
最近のトレンド• ランダム性を使った平均的なふるまい：乱択アルゴリズム– “ランダム性”を入力に仮定する» …この場合はアルゴリズムは決定性でもよい» 一般に与えられる入力の分布はわからないことが多い– アルゴリズムで“乱数”を使う» “良い”疑似乱数を生成する方法はけっこう難しい– 効率（実行時間/使用メモリ）の期待値/最悪値などを解析する必要がある• 正解からの誤差を許した計算を考える：近似アルゴリズム– 近似率を理論的に保証することができる場合がある
4/40

確率解析 の前に
確率解析…
– アルゴリズムで“乱数”を使う• “良い”疑似乱数を生成する方法はけっこう難しい– 良い疑似乱数を使用することで、モンテカルロ法が1000倍速くなり、それまで２年かかっていた計算が１日で終わるようになった事例がある。
– 疑似乱数の「良さ」とは？
コンピュータ・サイエンスのバイブル“The Art of Computer Programming”, Vol. 2, by D.E. Knuth
でも詳しく議論されているテーマ• メルセンヌ・ツイスター(Mersenne twister)– 松本眞、西村拓士による疑似乱数生成器– 公式サイトからダウンロードして使用可能– http://www.math.sci.hiroshima‐u.ac.jp/~m‐mat/MT/SFMT/index‐jp.html– 速い/コードが単純/性能が理論保証されている

5/40

確率解析の例: クーポンコレクター問題– クーポンコレクター問題
ク ポ
クタ 問題
n 種類のクーポンが無限にある。毎回それぞれの種類 ク ポン 無限 ある。毎回それぞれクーポンを 1/n の確率で引き当てる。すべてのクーポンが集まるまでクーポンを引き続けるとすると、クーポンを何枚引かなければならないだろうか。
を何枚引かなければならな だろうか

– 定理
n 種類のク
種類のクーポンが集まるまでにクーポンを引く枚数
ポンが集まるまでにク ポンを引く枚数
をC(n)とおくと、C(n)の期待値 E(C(n)) は次の式で表現される：
E(C(n)) = O(n log n)
6/40

確率解析の例: クーポンコレクター問題– 定理
n 種類のクーポンが集まるまでにクーポンを引く枚数
をC(n)とおくと、C(n)の期待値 E(C(n)) は次の式で表現される：
E(C( )) = O(nE(C(n))
O( logl n))– おまけ：上記の式は E(C(n)) = n log n + o(1) と書ける。
– 例：• クーポンが10種類なら23強• クーポンが100種類なら460強

余談：マクドナルドの101匹
わんちゃんのコンプリート
わんちゃんのコンプリ
ト
セットは定価５万円でした。

余談：オークションで7000円でした。
7/40

確率解析の例: クーポンコレクター問題
– 定理
定
定理：
n 種類のクーポンが集まるまでにクーポンを種類 ク ポ が集まるま
ク ポ を引く枚数をC(n)とおくと、C(n)の期待値 E(C(n)) は次の式で表現される： E(C(n)) = O(n log n)– 証明• 現在 i 種類のクーポンを持っている状態を状態 i とする。
• 時刻 t に t 枚目のクーポンを引くとする。
• 時刻0は状態0で、時刻1は状態1である。
時刻 は状態
時刻 は状態 ある• 状態 i でクーポンを１枚引くと、– 新しいクーポンを引いて状態 i+1 に状態遷移する確率： (n-i)/n( )– すでに持っているクーポンを引いて状態が変わらない確率： i/n• 新しい状態に遷移することを成功と考えると、これは幾何分
散に関するよく知られた定理が使える。
8/40

確率解析の例: クーポンコレクター問題
幾何分散に関するよく知られた定理： 1回の試行で– 定理成功する確率が p である事象を繰り返し行うと、1回成功するまでの繰り返しの回数の期待値 E(S(p)) は次の式で表現される：E(S(p)) = 1/p– 例：• 成功確率が1/2なら繰り返しの回数の期待値は2回• 成功確率が1/6なら繰り返しの回数の期待値は6回• 成功確率が1/100なら繰り返しの回数の期待値は100回– 証明• 定義通り、

1  p  2  (1  p )  p  3  (1  p ) 2 p    i  (1  p )i 1 p  を計算すればよいを計算すればよい。

– 注意：あくまで期待値の話であって、博打には役立ちません
9/40

確率解析の例: クーポンコレクター問題
定理： n 種類のク
種類のクーポンが集まるまでにクーポンをポンが集まるまでにク ポンを– 定理
引く枚数をC(n)とおくと、C(n)の期待値 E(C(n)) は次の式で表現される： E(C(n)) = O(n log n)– 証明• 状態 i でクでクーポンを１枚引くと、ポンを 枚引く 、– 新しいクーポンを引いて状態 i+1 に状態遷移する確率： (n-i)/n– すでに持っているクーポンを引いて状態が変わらない確率： i/n• 新しい状態に遷移することを成功と考えると、これは幾何分
新しい状態に遷移することを成功と考えると これは幾何分
散に関するよく知られた定理が使える。
• よって状態 i から状態 i+1 に遷移するまでの時間の期待値＝状態 i の区間の長さの期待値＝n/(n-i)の区間の長さの期待値＝ /( i)• 期待値の線形性より、これらを i=0～n-1まで足せばよい（意外と重要：期待値には線形性があり、そのまま足すことができる。）
10/40

確率解析の例: クーポンコレクター問題– 定理：
定理 n 種類のクーポンが集まるまでにクーポンを定理
種類のク ポンが集まるまでにク ポンを引く枚数をC(n)とおくと、C(n)の期待値 E(C(n)) は次の式で表現される： E(C(n)) = O(n log n)– 証明• したがって求める期待値は
n 1

n 1
n
n
1
1
n
n


 nH (n)i 0 n  ii 0 n  ii 1 iとなる n 1
• ここで   H (n) は調和数 (Harmonic number)と呼ばれる数列でi 1 i
1
1
1
1
0



,   00.5772156649
5772156649
H (n)  log n    



,
6
2
4
256n
n 12n 120nが知られている。よって定理を得る。

11/40

確率解析の例: クーポンコレクター問題– 調和数についての参考文献
調和数
参考文献• 簡単に読めて楽しい（？）本– 『数学ガール』結城浩、ソフトバンククリエイティブ、2007.
ハーモニックナンバーに関する章だけなら以下のWeb版でも読めます：» テトラちゃんとハーモニック・ナンバー
http://www.hyuki.com/girl/harmonic.pdf
結城浩、2006年４月– 『世界でもっとも奇妙な数学パズル』ジュリアン･ハヴィル著、松浦俊輔訳 青土社 2009
松浦俊輔訳、青土社、2009．
第11章に載ってます。いろいろな「不思議」が載っている良書。

12/40

ちょっと休憩…
ちょっと休憩
• レポート課題を配布する
ポ
課 を 布する

13/40

乱択アルゴリズム(Randomized Algorithm)– 乱数を用いたアルゴリズム
乱数を
た
ゴ ズム
• 乱数を用いることで計算の高速化/単純化を目指すア
ルゴリズム
ゴ ズム
• ラスベガス型– いつでも正しい答えを返すことが保証されている。
いつでも正しい答えを返すことが保証されている– 計算時間は何らかの確率分布に従う• モンテカルロ型– ときどき間違える。例えば Yes/No タイプの問題であれば» twotwo‐sided
sided error; Yes を No という確率も No を Yes という確率も0ではない» one‐sided error; 上記のどちらかのみ 0 でない– 普通は誤答を与える確率を小さくできる

14/40

乱択アルゴリズム(Randomized Algorithm)– 乱数を用いたアルゴリズム• ラスベガス型：いつでも正しい解答を出力する• モンテカルロ型：一定の割合で誤答を出力する
ンテカル 型定の割合で誤答を出力する• 演習問題１：– アルゴリズムAは1回の実行時間が t(n) 時間であり、そのとき3/4
時間であり そのとき3/4の確率で正解を出力する。これを3回実行して多数決をとる。このときの実行時間と正解を出力する確率を求めよ。

• レポート問題１：– アルゴリズムBは1回の実行時間が t1(n) 時間である。このとき
確率 p で正解を出力する。出力が正しいかどうかは別のアルで正解を出力する。出力が正しいかどうかは別のアルゴ
リズム C で t2(n) 時間で確認することができる。正解が得られる
まで B, C を繰り返し実行するアルゴリズムの実行時間と正解を出力する確率を求めよ。ここから何が言えるか。
15/40

確率解析の例(1): QuickSortの解析– ソーティング問題
ソ テ ング問題
Input: n 個のデータを記録した配列 a[n]Output: 以下の条件を満たす配列
条件を満たすa[n]a[1]<a[2]<…<a[n]★話を単純にするため、a[i]=a[j],
話を単純 すi≠j を満たすペアはないと仮定
を満 す
な
仮定
– QuickSort は実用上、最速と言われることが多いは実用上 最速と言われることが多い• 典型的な分割統治法に基づくアルゴリズム• 都合良く分割されると O(n log n) 時間で計算が終わる• いつでも最悪の場合だと O(n2) かかる• …理論的な解析と速度保証はできるのか？
16/40

確率解析の例(1): QuickSortの解析– QuickSortのおさらい
ラスベガスタイプ• qsort(a,1,n)
qsort(a 1 n) を呼び出すのアルゴリズム• qsort(a, i, j) が呼び出されると、– pivot a[m] を（ランダムに）選ぶ– a を a[m] を基準に「前半」と「後半」に分ける。つまりを基準に「前半」と「後半」に分ける つまりi≦ i’ < m なら a[i’]<a[m]m< j’ < j なら a[j’]>a[m]を満たすように並べ替える[余談]
毎回 O(j-i) 時間かければちょうど中央の値を見つけることもできる。

– qsort(a, i, i’), a[m], qsort(a, j’, j) がソート結果– QuickSort は実用上、最速と言われることが多いが、、、• a[m] がいつでも a[i]..a[j] の中央の値だとT(n) ≦ 2T(n/2) + (c+1) nが成立するので T(n)が成立するので、T( ) = O(O(n logl n)) を得る。
を得る
• a[m] がいつでも a[i] や a[j] だとT(n)≦T(1)+T(n-1)+(c+1)nが成立するので、T(n)成 す、 ( ) = O(n( 2) を得を得る。
。

平均的な場合はどうなのか？

17/40

確率解析の例(1): QuickSortの解析– QuickSort は実用上、最速と言われることが多いが、、、• 平均的には、a[i] ... a[j] の値が一様に選ばれると仮定する。

– つまり k 番目のものを pivot にする確率は 1/(j-i+1)
オーバーヘッドの少なさから、確かに速いと言えそう[定理]
上記の仮定のもとでの QuickSort の実行時間の期待値の上界は 2n H(n)H(n)~ 2n log n– 記法» a[1]…a[n] の中で k 番目に来るべき要素を sk と書く。と書く
» 指示変数（indicator variable）Xij を以下のように定義する
0 si と sj がアルゴリズム中で比較されないとき
X ij  1 si と sj がアルゴリズム中で比較されるときn– QuickSort
Q i kS t の実行時間~要素の比較回数=の実行時間~要素の比較回数

 X
i 1 j  i

ij

18/40

確率解析の例(1): QuickSortの解析[定 ] 仮定のもとでの[定理]
定
QuickSort の実行時間のQ
実
期待値の上界は 2n H(n)~ 2n log n（期待値の線形性による）nni 1 j  ii 1 j  i• QuickSort の実行時間の期待値= E[ X ij ]  E[ X ij ]• 「ppij = 『si と sj が比較される確率』」と定義すると、E[ X ij ]  pij 1  (1  pij )  0  pij

よって pij の値を考える• si と sj はどんなときに比較されるのか？
1. どちらかが pivot に選ばれている
選ばれる
2. それまでの計算過程で、別々の qsort にわけられていない
pivot として選ばれていない⇔ si と sj の間の要素が、まだ p
19/40

確率解析の例(1): QuickSortの解析[定 ] 仮定のもとでの[定理]
定
QuickSort の実行時間のQ
実
期待値の上界は 2n H(n)~ 2n log n• si と sj はどんなときに比較されるのか？
1. どちらかが pivot に選ばれている
2. それまでの計算過程で、別々の qsort にわけられていない⇔ si と sj の間の要素が、まだ pivot として選ばれていない
3. si, si+1, si+2, …, sj-1に選ばれる順番は、すべて等確率！
て等確率！
j 1,sj が pivot に選ばれる順番は、す2
4. よってこれらの中で si か sj が最初の pivot になる確率:j  i 1

– よってQuickSortの実行時間の期待値=
n
n
n
n

2
i 1 j i j  i  1

E[ X ij ]  E[ X ij ]   pij i 1 j  ii 1 j  ii 1 j in n  i 1nn
21
    2  2nH (n)i 1 k  2 ki 1 k 1 k

20/40

確率解析の基本ツール(1)：マルコフの不等式– 定理 (マルコフの不等式)
非負の値をとる任意の確率変数を Y とする。
E[Y ]すると任意の正の実数 t に対して次が成立する：Pr[Y  t ] t1
これは次と同値である：
Pr[Y  kE[Y ]] k• マルコフの不等式の意味とは…
マルコフの不等式の意味とは「期待値の k 倍以上になる確率は 1/k 以下である」– QuickSort の実行時間が 4n log n 以上になる確率は ½ 以下
– 10種類のクーポンを全部集めるために 69 回以上買う確率は1/3 以下…

• Yが非負であることと期待値 E[Y] しかわからないときは、これは改善できない 分散もわかると もうちょっと改善できる
れは改善できない。分散もわかると、もうちょっと改善できる。
21/40

確率解析の基本ツール(1)：マルコフの不等式– 定理 (マルコフの不等式)
等式
非負の値をとる任意の確率変数を Y とする。
すると任意の正の実数 t に対して次が成立する：
に対し 次が成立する Pr[Y  t ]  E[Y ]t1
これは次と同値である：Pr[Y  kE[Y ]]  k
0
f
(
y
)


[証明] 関数 f(y) を次のように定義する：
1
すると Pr[Y  t ]  E[ f (Y )] である。
である

y<t
y≧t

ここですべての y に対して f(y)≦y/t なので、Pr[[Y  t ]  E[ f ( y )]  E[Y / t ] 

E[Y ]
t

t

となる。
22/40

確率解析の基本ツール(1)：マルコフの不等式– 定理 (マルコフの不等式)
等式
非負の値をとる任意の確率変数を Y とする。
すると任意の正の実数 t に対して次が成立する：
に対し 次が成立する Pr[Y  t ]  E[Y ]t1
これは次と同値である：Pr[Y  kE[Y ]] k

演習問題２：
正整数 k を一つ固定する。このとき非負の値をとる確率変数
を一つ固定する このとき非負の値をとる確率変数 Xで以下の条件を満たすのはどのような確率変数だろうか。
Pr[[ X  kE
k [ X ]] 

1
k

23/40

確率解析の基本ツール(2)：チェビシェフの不等式– 定理 (チェビシェフの不等式)(チ ビシ フの不等式)
期待値 μx と標準偏差 σx をもつ確率変数を X とする。
すると任意の正の実数 t に対して次が成立する： Pr[[ X   x  t x ]  12t

• 復習：標準偏差とは…
– 定義:
定義 確率変数Xが値
確率変数 が値 x1, x2, …, xn をそれぞれ確率を れぞれ確率 p1, p2, …, pn
でとるとする。このとき期待値（平均値） μxと分散σx2は次で定義nされる：   p x
x



i i

i1
n

 x 2   pi (xi   x ) 2i 1– 分散の正の平方根σxが標準偏差• 標準偏差（分散）がわかっている確率変数に対しては、こちらの方がマルコフの不等式よりもずっと強力である。
こちらの方がマルコフの不等式よりもずっと強力である
24/40

確率解析の基本ツール(2)：チェビシェフの不等式– 定理
定 (チェビシェフの不等式)
ビ等
期待値 μx と標準偏差 σx をもつ確率変数を X とする。
1
すると任意の正の実数 t に対して次が成立する： Pr[
P [ X   x  t x ]  2t[証明] まず、明らかに次が成立する。
Pr[ X   x  t x ]  Pr[( X   x ) 2  t 2 x2 ]確率変数 Y を Y=(X- μx)2 とおくと、 Y の期待値は σx2 である。
Y と t2 に対してマルコフの不等式を適用すると、に対してマルコフの不等式を適用すると
1
Pr[Y  t 2 E[Y ]]  2tより以下を得る。

1
Pr[ X   x  t x ]  Pr[( X   x ) 2  t 2 x2 ]  2
t

25/40

ＯHPシートで作った川崎ローズ（デザイン：川崎敏和、
折 た人 上原）
折った人：上原）

２回目の休憩
曲線折りの例（デザイン、折った人：Martin Demaine）• レポートを書いて提出。時間は30分くらい？
上原のところにある折り紙作品
あのお父さん（デザイン：上原、折った人：上原）

たぶん世界最小前川デビル 26/40（デザイン：前川淳、折った人：上原）ソートの下界の話– 比較に基づく任意のソートアルゴリズムは
比較 基づく任意ゴ ズムはΩ(n( logg n)) 時間の計算時間が必要である• 証明（概略）– k 回の比較で区別できる場合の数は高々 2k 種類しかない– n 個の要素の異なる並べ方は n! 通りある
– したがって少なくともn
2k  n !  2 n  enが成立していなければならない。
両辺の対数をとれば以下を得る。
n1nk  log 2 n    n log n  O(n)  log n  O(1)
2
e
27/40

超高速ソートの話– 以下の特殊なソートを考える：
特殊なを考える• 入力： a[1]…a[n] で、それぞれの a[i] の値は 1～10
• 以下のアルゴリズムAは O(n) 時間で動作する(!?)
1. 配列 b[1]=b[2]=…=b[10]=0; // b[i] は a[j]=i を満たす要素の個数
2. for i=1,2,…,n do b[a[i]]++;
3. for j=1,2,…,10 do “j をb[j]個出力する”.
このソートAは比較に基づいていない!!
Radix sort, bucket sort などと呼ばれるソートと同様のアイデアなどと呼ばれる
トと同様のアイデア
データが「整数」など「特殊」な場合はこちらの方が速い!!

データに
暗黙の仮定
があれば
利用できる
かもしれない28/40

典型的なNP完全問題KNAP を高速に解く方法(?)
典型的なNP完全問題KNAP…を高速に解く方法(?)– KNAP:
KNAP
Input: アイテムの配列 a[1], …, a[n], 大きさ k
Output:p  a[i ]  k を満たす集合
を満たす集合S⊆{1,…,n}が存在するか?
{ , , }が存在するかiS– アルゴリズムB：それぞれの a[i] が正整数なら以下で解ける
一般には k の値が n に対して
1. b[1]=b[2]=…=b[k]=0;
2.. for ii=1,2,…,n, ,…,n do
1.

for j=k,k‐1,…,2,1 do
1. if b[j]>0 then b[j+a[i]]=1;

3 if b[t]>0 then “yes”
3.
yes else “no”
no .

– Bの実行時間は O(nk) 時間

指数関数的に大きくなりうるので、
実は多項式時間アルゴリズムではない!!
b[]をリストにすれば、実数などでも動作する。
データが「整数」など「特殊」な場合や、とりうる値の組合せの数（b[]の要素数）がn の多項式で押さえられるときは速い!!
29/40

典型的なNP完全問題KNAP を高速に解く方法(?)
典型的なNP完全問題KNAP…を高速に解く方法(?)– KNAP:
Input: アイテムの配列 a[1], …, a[n], 大きさ k
Output: a[i ]  k を満たす集合S⊆{1,…,n}が存在するか?
を満たす集合が存在するかiS– 演習問題：次のアルゴリズムB’は何を計算しているのか?
演習問題 次のアルゴリズムB’は何を計算しているのか?
1. b[1]=b[2]=…=b[k]=0;
2 for
2.
f i=1,2,…,n
i 12
d
do
1.

for j=k,k‐1,…,2,1 do[j] then b[j+a[i]]=b[j+a[i]]+1;[j [ ]] [j [ ]] ;1. if b[j]>0

3. if b[t]>0 then “yes” else “no”.

30/40

近似アルゴリズム(Approximation Algorithm)•

近似アルゴリズムの枠組
近似アルゴリズムの枠組：– 「Yes/No」タイプの決定問題を「最適化問題」に改造して考える。
（注意）最適化問題は「最小化問題」と「最大化問題」がある•

例：– VC（頂点被覆）: 大きさ最小の頂点被覆を見つける– MaxSAT: 与えられた論理式のうち、なるべく多くの項を与えられた論理式のうち なるべく多くの項を “True”
True にする– 巡回セールスマン問題: すべての都市をめぐる最小コストの経路を探す（グラフを「辺に重み（コスト）のついたグラフ」にして、全経路を通れることにする）– KNAP: 大きさ k 以下の組合せの中で最大のものを見つける•

近似アルゴリズムの良さは「近似率」（と計算時間）で測る：– 最適な解を O
O* として、アルゴリズムの出力をとして アルゴリズムの出力を O とすると、とすると最小化問題の近似率=O/O*≧1最大化問題の近似率=O*/O≧1– 近似率はいつでも1以上で、近似率1のアルゴリズムは誤差のないアルゴリズム。
31/40

近似アルゴリズム(Approximation Algorithm)•

アルゴリズムの良さを「近似率」（と計算時間）で測る
アルゴリズムの良さを「近似率」（と計算時間）で測る：– 困難問題（を最適化問題に翻訳したもの）は典型的には以下の3つのタイ
プに分類できる
1. 定数倍近似すら困難なもの(クラス: この授業では扱わない)
1.

“=が成立しない限り定数倍近似は存在しない問題”など

2. 適当な定数に対して定数倍近似が可能なもの（2倍近似アルゴリズムなど）
3. 任意の正定数 ε>0 に対して以下の条件を満たすアルゴリズムが存在する：
ゴ ズ が
1. n と 1/ε に対する多項式時間で動作する
2. (1+ε)近似解を出す
このアルゴリズム（群）を多項式時間近似スキーム(PTAS; Polynomial Time Approximation Scheme)と呼ぶ

32/40

近似アルゴリズム(Approximation Algorithm)
2. 2倍近似アルゴリズムの例
倍近似
ゴリズム 例

なぜか2倍を切れるかどうかが難しい
問題が多い
が– 頂点被覆問題(VC)の最適化バージョン
入力：無向グラフG=(V,E)
出力：最小の頂点被覆 S– アルゴリズムC:
アルゴリズムC

SはGの 頂点被覆」：
SはGの「頂点被覆」：
どの辺{u,v}に対してもu∈Sまたはv∈Sが成立

1. S:=Φ;2. G の辺 e={u,v}を適当に1本選ぶ
3. u と v を S に入れる

線形時間で動作するのは簡単なので省略

4. u,v につながっている辺を G からすべて削除する
5. G に辺が残っていれば 2 に戻る[定理] アルゴリズムCの実行時間はO(|V|+|E|)時間である。
また G の最適な頂点被覆を S* とし、アルゴリズムCの出力を
ゴリズム
出力を S とすると、以下が成立：とすると 以下が成立|S|/|S*|≦2

33/40

近似アルゴリズム(Approximation Algorithm)
2. 2倍近似アルゴリズムの例
倍近似
ゴリズム 例– アルゴリズムC:

SはGの「頂点被覆」：
どの辺{ }に対してもどの辺{u,v}に対してもu∈Sまたはv∈Sが成立

11. S:=Φ;2. G の辺 e={u,v}を適当に1本選ぶ
3. u と v を S に入れる
4 u,v
4.
u v につながっている辺を G からすべて削除する
5. GGに辺が残っていれば
2 に戻る
[定理]
の最適な頂点被覆をS* とし、

アルゴリズムCの出力を S とすると、以下が成立：|S|/|S*|≦2[証明] ステップ2で選ばれた辺 e の集合を C とおく。
e はステップ4で削除されるため同じ辺が2度選ばれることはない。∴2|C|=|S|。
度選| | | |
C は頂点を互いに共有しない辺の集合で、e∈C のそれぞれについて
少なくとも一方の端点は S* に入っていなければならない。∴|C|≦|S*|
したが て |S|/|S*|≦2|C|/|C|=2
したがって|S|/|S*|≦2|C|/|C| 2 である。
である
34/40

近似アルゴリズム(Approximation Algorithm)
2. 2倍近似アルゴリズムの例
倍近似
ゴリズム 例– アルゴリズムC:

SはGの「頂点被覆」：
どの辺{ }に対してもどの辺{u,v}に対してもu∈Sまたはv∈Sが成立

11. S:=Φ;2. G の辺 e={u,v}を適当に1本選ぶ
3. u と v を S に入れる
4 u,v
4.
u v につながっている辺を G からすべて削除する
5. GGに辺が残っていれば
2 に戻る
[定理]
の最適な頂点被覆をS* とし、

アルゴリズムCの出力を S とすると、以下が成立：|S|/|S*|≦2[演習問題] アルゴリズムCは2倍近似アルゴリズムであることが証明された。
C の近似率2はこれ以上改善できないことを示せ。
改善
具体的に、無限に多くの n に対して、C の近似率がちょうど 2 であるような
n 頂点グラフの例を示せ。

35/40

近似アルゴリズム(Approximation Algorithm)
3. 多項式時間近似スキームの例
多項式時間近似 キ ム 例– ＫＮＡＰの最適化バージョン[アイデア] 個々の値をそれに近い値に丸めてそれに近い値に丸めて、値の種類を減らす

Input: アイテムの配列 a[1],[1] …, a[n],[ ] 大きさ k
Output:  a[i ]  k S  k を満たす集合S⊆{1,…,n}でもっとも近いもの
iS– アルゴリズムD （アルゴリズムBも参照）:
1. L:=Φ; //実現できる和の近似値のリスト
2. for i=1,2,…,
1. L のそれぞれの要素 b に対して、b+a[i]≦k ならそれを L に登録
2 L のいくつかの要素を「丸め」て
2.
のいくつかの要素を「丸め」て、不要なら捨てる
不要なら捨てる3. L の中の k 以下のもっとも大きな値 k’ を出力する[ポイント] Dで以下の2点が満たされればよい：
1. Lのサイズがいつでも n の多項式
2. 出力 k’ がよい近似解を与える

36/40

近似アルゴリズム(Approximation Algorithm)
3. 多項式時間近似スキームの例
多項式時間近似 キ ム 例– ＫＮＡＰの最適化バージョン
Input: アイテムの配列 a[1],[1] …, a[n],[ ] 大きさ k
Output:  a[i ]  k S  k を満たす集合S⊆{1,…,n}で もっとも近いもの
iS

[仮定]
– アルゴリズムD（アルゴリズムBも参照）:• L が小さい順で並んでいるとする• 正の定数εを固定する[丸めの詳細]• Lの中で b1<b2≦(1+ε/2n) b1 なら b2 を削除する[定理]
定理 アルゴリズムDはＰＴＡＳである。
ゴ ズム はある
つまり任意の正定数εに対して以下が成立する：
1. n, 1/ε の多項式で動作する
2 近似率は (1+ε)
2.
(1+ )[証明] 1,2 ともにちょっと計算が必要…

37/40

近似アルゴリズム(Approximation Algorithm)– 補題13.1: 自然数列 a1=1, a2, …, an=k が
1 t
n
l k
ln
(ai+1)/ai ≧ 1+t を満たすなら、次が成立：
が
t
x
n
n

log
k
[証明] (1  t )  k より、である。公式 ln(1  x)  x
t 1
1 x
を適用すると以下を得る
を適用すると以下を得る。
ln k(1  t )n  log t 1 k ln ktln(1  t )

 

n


– 補題13.2： 0<ε <1に対して 1    1   2n 
[証明] 以下の公式をつかう。
n x[公式1] lim 1    e x (この式は n に対して単調増加関数)
n 
 n
[公式2] |x|≦1ならば 1  x  e x  1  x  x 2
n

2

 
  

 /2
以上より 1 e
1    1 2 2 2n 

38/40

近似アルゴリズム(Approximation Algorithm)–

ＫＮＡＰの最適化バージョンの多項式時間近似スキームの最適化バ ジ ンの多項式時間近似スキ ム[定理13.2] アルゴリズムDはＰＴＡＳである。
つまり任意の正定数εに対して以下が成立する：
まり任意の正定数εに対して以下が成立する：
1. n, 1/ε の多項式で動作する
2. 近似率は (1+ε)[証明] 1) Lのサイズがズ n, 1/ε の多項式で抑えられればよい。
ここで L の要素列 b1, b2, … は、1≦b1, bi ≦k, bi+1/bi > (1+ε/2n) を満たす。
よって補題13.1より、Lのサイズ＜log
ズ(1+ε/2n) k = ((2n+ε) log k)/ε < (2n log k)/ε
となる。

39/40

近似アルゴリズム(Approximation Algorithm)–

ＫＮＡＰの最適化バージョンの多項式時間近似スキームの最適化バ ジ ンの多項式時間近似スキ ム[定理13.2] アルゴリズムDはＰＴＡＳである。
つまり任意の正定数εに対して以下が成立する：
1. n, 1/ε の多項式で動作する
2. 近似率は (1+ε)[証明] 2) アルゴリズムの出力 k’ を構成する a[][] の要素集合が存在する。
の要素集合が存在する
この集合を S’ とする。
a[]  k 'つまり次が成立する：
a[]S '
ここで入力に対する
a[]  k * とする。
最適な集合を S* とし、a[]S *
S* のそれぞれのa[] に対しては、それがに対しては それが L に存在しているか、それを代替したものがあるはずに存在しているか それを代替したものがあるはずである。代替されている場合、最悪だと a[] は以下の値 a’ で代替されている。





a[]
a[]

 a '  a[]nn 1(1   / 2n)(1   / 2n)よって
k*/(1+ε/2n)n ≦ k’ が成立し、補題13.2より k*/k’≦1+ε を得る。

40/40