スライド

情報数理科学Ⅶ／広域システム科学特殊講義Ⅳ
算法の設計と解析
動的計画法（2）
http://www.graco.c.u-tokyo.ac.jp/~kawamura/t/ad/
河村彰星
再掲
Dynamic Programming
動的計画法とは
漸化式を使って値を順次記録しながら
求める方法
問題フィボナッチ数列の第 𝑛 項を求める
1
𝑛 = 0 のとき
𝑓𝑛 = ቐ1
𝑛 = 1 のとき
𝑓𝑛−1 + 𝑓𝑛−2
他
そのまま再帰呼出しにすると……
f(n) {
if (n が 0 か 1)
return 1
else
return f(n - 1) + f(n - 2)
fi
}
同じ函数呼出しを何度もするせいで非効率
f(4)
f(3)
f(2)
f(1)
f(0)
f (2)
f(1)
f(1)
f(0)
1
1
1
末端は 1
1
1
fib(n) を計算するには再帰呼出しが fib(n) 回以上
一回やった計算の結果は覚えておこう
再掲
動的計画法最終結果を求めるのに必要な値の「表」を作る
• 表が埋まった≒問題が解けた
• 表の既に埋めたマスの値は何度も使える
f(n) {
何でそれだけのことに
長さ n + 1 の配列 table を用意
名前が付いてるの？
for i in 0 .. n
if (i が 0 か 1)
軍の資金で研究させてもらうために
table[i] := 0
なんか強そうな名前にしといた
else
table[i] := table[i - 1] + table[i - 2]
fi
0 1 2 3 4 5 6 7 8
end
1 1 2 3 5 8 13 21 34
table[n]
}
この表を左から右に順に埋めてゆく
時間計算量 O 𝑛
空間計算量 O 𝑛
リチャード・ベルマン
（Richard Bellman, 1920～84）
実際の問題に適用するには
うまく「端から埋めていける」ような漸化式を見つける必要がある
問題背嚢問題（knapsack problem）
入力価値と重さの指定された幾つかの品物と重み制限 𝑊 > 0
品物 𝑖 = 1, … , 𝑛 価値が 𝑣𝑖 > 0 重さが 𝑤𝑖 > 0
出力重みの和が 𝑊 以下で
例
𝑖
𝑣𝑖
価値の和が最大となる選び方
𝑤𝑖
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
重さ制限 𝑊 = 11
品物 3 と 4 を選び
価値 40 を得るのが最大
ダメな例
価値 𝑣𝑖 の高い順に貪慾法
重さ 𝑤𝑖 の軽い順に貪慾法
比 𝑣𝑖 /𝑤𝑖 の大きい順に貪慾法
問6.1 どれも正しくないことを示せ
動的計画法（漸化式を立てよう）
品物 1, …, 𝑖 を使って（重さ制限 𝑊 以内で）得られる最大価値 𝑂𝑃𝑇 𝑖
𝑖 = 0 のとき
0
𝑂𝑃𝑇(𝑖) = ቊ
max{𝑂𝑃𝑇 𝑖－1 , 𝑣𝑖 +
品物 𝑖 を
選ばないとき
} それ以外
品物 𝑖 を
選ぶとき
うまく部分問題に
帰着できるように
する必要がある…
最適値が満す漸化式
品物 1, …, 𝑖 のみを用いて重さの和 𝑤 以内で
実現できる最大の価値 𝑂𝑃𝑇 𝑖, 𝑤 は？
品物 𝑖 を選ぶ場合この品物 𝑖 でまず価値 𝑣𝑖 が得られ更に
品物 1～ 𝑖 − 1 を使って重さ 𝑤 − 𝑤𝑖 以内で
最大価値を得る
𝑖 を選ばない場合品物 1～ 𝑖 − 1 を使って最大価値を得る
つまり
𝑖 = 0 のとき
0
𝑤𝑖 > 𝑤 のとき
𝑂𝑃𝑇(𝑖, 𝑤) = ቐ𝑂𝑃𝑇(𝑖 − 1, 𝑤)
max 𝑂𝑃𝑇 𝑖 − 1, 𝑤 , 𝑣𝑖 + 𝑂𝑃𝑇 𝑖 − 1, 𝑤 − 𝑤𝑖
それ以外のとき
𝑂𝑃𝑇 𝑛, 𝑊 が答
𝑖
𝑣𝑖
𝑤𝑖
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
𝑖
品物 1, …, 𝑖 のみを用いて重さの和 𝑤 以内で
実現できる最大の価値 𝑂𝑃𝑇 𝑖, 𝑤
𝑖 = 0 のとき
0
𝑤𝑖 > 𝑤 のとき
= ቐ𝑂𝑃𝑇(𝑖 − 1, 𝑤)
max 𝑂𝑃𝑇 𝑖 − 1, 𝑤 , 𝑣𝑖 + 𝑂𝑃𝑇 𝑖 − 1, 𝑤 − 𝑤𝑖
それ以外のとき
𝑤
0
1
2
3
4
5
6
7
8
9
10
11
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
1
1
2
0
1
6
7
7
7
7
7
7
7
7
7
3
0
1
6
7
7
18
19
24
25
25
25
25
4
0
1
6
7
7
18
22
24
28
29
29
40
5
0
1
6
7
7
18
22
28
29
34
35
40
Knapsack(𝑣1 , … , 𝑣𝑛 , 𝑤1 , … , 𝑤𝑛 , 𝑊) {
for 𝑤 = 0, … , 𝑊
最適値を達成する
𝑀 0, 𝑣 ≔ 0.
品物の選び方を求めるには？
for 𝑖 = 1 to 𝑛
for 𝑤 = 0, … , 𝑊
表を作り終えてから
if 𝑤𝑖 > 𝑤
このどちらが選ばれたか
𝑀 𝑖, 𝑤 ≔ 𝑀[𝑖 − 1, 𝑤].
調べながら戻ればよい（次頁）
else
𝑀 𝑖, 𝑤 ≔ max 𝑀 𝑖 − 1, 𝑤 , 𝑣𝑖 + 𝑀 𝑖 − 1, 𝑤 − 𝑤𝑖 .
return 𝑀 𝑛, 𝑊
}
𝑖
𝑣𝑖
𝑤𝑖
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
𝑖
品物 1, …, 𝑖 のみを用いて重さの和 𝑤 以内で
実現できる最大の価値 𝑂𝑃𝑇 𝑖, 𝑤
𝑖 = 0 のとき
0
𝑤𝑖 > 𝑤 のとき
= ቐ𝑂𝑃𝑇(𝑖 − 1, 𝑤)
max 𝑂𝑃𝑇 𝑖 − 1, 𝑤 , 𝑣𝑖 + 𝑂𝑃𝑇 𝑖 − 1, 𝑤 − 𝑤𝑖
それ以外のとき
𝑤
0
1
2
3
4
5
6
7
8
9
10
11
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
1
1
2
0
1
7
7
7
7
7
7
7
3
0
6
7
7
品物３を選択
1
6
7
7
18
19
25
25
4
0
1
6
7
7
18
24 25 25
品物４を選択
22 24 28 29
29
40
5
0
1
6
7
7
18
22
35
40
28
29
34
定理
この算法は
入力長の多項式
以内にはなってない
時間量 Θ 𝑛𝑊
空間量 Θ 𝑛𝑊
∵ 表の寸法は 𝑛 + 1 × 𝑊 + 1 = Θ 𝑛𝑊 であり
各成分の計算に定数時間
このように「入力に現れる数」の多項式時間で終了する算法
言い換えればもし入力中の数が二進法ではなく羅列法（𝑛 を 0𝑛 と書く）で
表されていたら多項式時間であるような算法
を
擬多項式（pseudo-polynomial）時間の算法と呼ぶことがある
再来週～
背嚢問題はNP困難なので多項式時間算法はおそらく存在しない
しかし「最適解との差が1%以内の解を求める」という問題なら
多項式時間で解ける
問題文字列 𝑢 = 𝑢1 … 𝑢𝑚 と 𝑣 = 𝑣1 … 𝑣𝑛 の編集距離を求める
文字列の違いの度合を測る尺度
二つの文字列を「揃えて」比べる
例 “GACGGATTAG” と “GATCGGAATAG” の距離は？
𝑑 "GACGGATTAG", "GATCGGAATAG" = 3
揃え方は色々あるが……
GAC-GGATTAG
○○△×○○○△○○○
GATCGGAATAG
4点
○（一致）0点
△（不一致）1点
×（間隙）2点
GA-CGG-ATTAG
○○×○○○×○○×○○
GATCGGAAT-AG
6点
GA-CGGATTAG
○○×○○○○△○○○
GATCGGAATAG
3点
として合計点の最小値（すべての揃え方のうちで）
以下では一般化して
文字 𝑝 と 𝑞 を揃えた場合 𝛼𝑝𝑞 点
揃えずに間隙を作った場合 𝛿 点とする
最適値が満す漸化式
文字列 𝑢1 … 𝑢𝑖 と 𝑣1 … 𝑣𝑗 との距離 𝑂𝑃𝑇 𝑖, 𝑗 は？
𝑢1 … 𝑢𝑖−1
𝑢𝑖
𝑢1 … 𝑢𝑖−1
𝑣1 … 𝑣𝑗−1
𝑣𝑗
𝑣1 … 𝑣𝑗
𝑢𝑖
𝛼𝑢𝑖 𝑣𝑗 + 𝑂𝑃𝑇 𝑖 − 1, 𝑗 − 1 ,
min
𝑂𝑃𝑇 𝑚, 𝑛 が答
𝑣1 … 𝑣𝑗−1
𝑣𝑗
𝑖 = 0 のとき
𝑗 = 0 のとき
𝑗𝛿
𝑖𝛿
𝑂𝑃𝑇(𝑖, 𝑗) =
𝑢1 … 𝑢𝑖
𝛿 + 𝑂𝑃𝑇 𝑖 − 1, 𝑗 ,
𝛿 + 𝑂𝑃𝑇(𝑖, 𝑗 − 1)
それ以外のとき
定理
これに従った動的計画法で
時間量 Θ 𝑚𝑛
空間量 Θ 𝑚𝑛
∵ 表の寸法
空間量を減らせるか？
各列の計算には直前の行しか使わないので
表全体ではなく一行だけ記憶していればよい
Θ 𝑚+𝑛
しかしそうすると最適の揃え方を復元できない
定理
次頁からの算法を使うと
分割統治法と組合せる
時間量 Θ 𝑚𝑛
空間量 Θ 𝑚 + 𝑛
ハーシュバーグ（Hirschberg）の算法
𝑂𝑃𝑇 𝑖, 𝑗 はこのグラフにおいて
頂点 0,0 から 𝑖, 𝑗 への最短距離 𝑓 𝑖, 𝑗
ε
ε
v1
v2
v3
v4
v5
v6
0-0
u1
𝛼𝑢𝑖𝑣𝑗
u2
u3
𝛿
𝛿
i-j
m-n
ハーシュバーグ（Hirschberg）の算法
各列の計算は Θ 𝑚 + 𝑛 空間で可能
j
ε
ε
v1
v2
v3
v4
v5
v6
0-0
u1
u2
u3
i-j
m-n
ハーシュバーグ（Hirschberg）の算法
逆に考えて 𝑖, 𝑗 から 𝑚, 𝑛 への最短距離 𝑔 𝑖, 𝑗 も求まる
ε
ε
u1
v1
v2
v3
v4
v5
v6
0-0
i-j
𝛿
𝛼𝑢𝑖+1 𝑣𝑗+1
𝛿
u2
u3
m-n
ハーシュバーグ（Hirschberg）の算法
逆に考えて 𝑖, 𝑗 から 𝑚, 𝑛 への最短距離 𝑔 𝑖, 𝑗 も求まる
（空間 Θ 𝑚 + 𝑛 で）
j
ε
ε
u1
v1
v2
v3
v4
v5
v6
0-0
i-j
u2
u3
m-n
ハーシュバーグ（Hirschberg）の算法
頂点 𝑖, 𝑗 を通る路の長さの最小値は 𝑓 𝑖, 𝑗 + 𝑔 𝑖, 𝑗
ε
ε
u1
v1
v2
v3
v4
v5
v6
0-0
i-j
u2
u3
m-n
ハーシュバーグ（Hirschberg）の算法
𝑓 𝑞,
𝑛
𝑞,
2
𝑛
2
+ 𝑔 𝑞,
u1
を最小にする 𝑞 を求めると
を通る最短路が存在するので…
n/2
ε
ε
𝑛
2
v1
v2
v3
v4
v5
v6
0-0
i-j
q
u2
u3
m-n
ハーシュバーグ（Hirschberg）の算法
𝑢𝑞 と 𝑣𝑛/2 を揃えることとし
その前後の部分問題を再帰的に解く
n/2
ε
ε
u1
v1
v2
v3
v4
v5
v6
0-0
i-j
q
u2
u3
m-n
この算法の時間量 𝑇 𝑚, 𝑛 は……
𝑛
𝑛
𝑇 𝑚, 𝑛 = 𝑇 𝑞, + 𝑇 𝑚 − 𝑞, + O 𝑚𝑛
2
2
𝑞 を求めるのに
再帰呼出し
かかる時間
つまり或る定数 𝑐 について
𝑇 𝑚, 2 ≤ 𝑐𝑚
𝑇 2, 𝑛 ≤ 𝑐𝑛
𝑛
𝑛
𝑇 𝑚, 𝑛 ≤ 𝑇 𝑞, + 𝑇 𝑚 − 𝑞, + 𝑐𝑚𝑛
2
2
すると 𝑇 𝑚, 𝑛 ≤ 2𝑐𝑚𝑛 が成立つ
∵ 𝑚 + 𝑛 に関する帰納法
𝑛
𝑛
𝑇 𝑚, 𝑛 ≤ 𝑇 𝑞, + 𝑇 𝑚 − 𝑞, + 𝑐𝑚𝑛
2
2
≤ 𝑐𝑞𝑛 + 𝑐 𝑚 − 𝑞 𝑛 + 𝑐𝑚𝑛 = 2𝑐𝑚𝑛
帰納法の仮定
採点が溜まっててすみません…
演習問題
・［KT］第六章末問題（前回配布）
・問6.1
注意動的計画法の算法を説明するときは
表の各マスで「何」を求めるのかを
（それを「どう計算するか」よりも前に）明記して下さい
［KT］クラインバーグ、タルドシュ著（浅野、浅野、小野、平田訳）『アルゴリズムデザ
イン』共立出版（平成20年）

Download Report