LCS

第16章
動的計画法
アルゴリズムイントロダクション
動的計画法(DP)

とは
Dynamic Programming
 Programing
: 表を引く手法
 Dynamic : その表を動的に作成していく

最適化問題に使用される手法
 適用可能な問題には構造的な制限がある．
 適用可能であれば効率的に最適解を算出可
動的計画法(DP)

の構造
基本的に以下の構造
1. 最適解の構造を特長づける
2. 最適解の値を再帰的に定義する．
3. ボトムアップ形式で最適解の値を計算
4. 求められた情報から一つの最適解を構成

…どういうこと？
 最適解の中に部分的に最適な解があればOK！
連鎖行列積
 DPで効率よく解く事の出来る問題の一例

n個の行列の積を考える

どの順番で計算すると計算回数が一番少なく
なる？
連鎖行列積

総当たりで計算すると…
 通り数は適切なカッコの付け方
 これは碁盤目状の道を対角線に向かって進むときに対
角線を超えない通り方と等しい
 （対角線を超える＝カッコの対応が正しく付かない）
 総通り数は

Stirling‘s formula
から導出．
 指数的に増えてくるのであまり頭良くない．
連鎖行列積

最適解を観察してみる

が最適解だとする．
 この解は部分問題の最適解
を持つ．
 最適解が他のパターンだとしても，
などの部分的な最適解を部分的に含む．
 二つの積から順々に構成することが可能．
 最適解の構造を特長付けできた．
連鎖行列積

最適解の値を再帰的に定義

: 行列積
にかかるコスト
連鎖行列積

ボトムアップに最適解を計算

0
129
63
75
95
部分問題に対する最適解を計算


0
21
35
57
0
6
20
0
8
0
再帰的に計算が可能
再帰するたびに計算するのではなく
その値を表に覚えておく
連鎖行列積

最適解を構成
0
129
63
75
95
0
21
35
57
0
6
20
0
8
0
1
1
3
3
2
3
3
3
3
4

最適解の構造を構成したい．

積がどこで分かれているのかを示す
値を別の表で記憶する
連鎖行列積

最適解を構成
1
1
3
3
2
3
3
3
3
4
動的計画法の基本

なぜ連鎖行列積で動的計画法が使えたか？
 部分構造の最適性
 問題の最適解がその内部に部分問題に対する最適解を
含んでいた．
→問題を小さく考える事ができた
 部分問題の重複性
 再帰アルゴリズムが同じ部分問題を何度も訪れていた．
→記憶することでコストを下げる事ができた
→もし記憶せずに毎回計算していたら…？
動的計画法の基本

もし毎回計算していたら…
動的計画法の基本

もし毎回計算していたら、指数コストかかる．
 上からn段目にかかる計算回数を

とすると
を仮定して，帰納的に証明．
動的計画法の基本

動的計画法が効率的に動く背景
 部分構造の最適性
→問題を小さく考える事ができた
 部分問題の重複性
→記憶することで時間コストを下げる
最長共通部分系列(LCS)

二つの系列X,Yにおける，最も長い，共通部
分系列Zを求める問題

は共通部分系列(Common Subsequence)
 これは最長？
 最長なものの例として
など．
最長共通部分系列(LCS)

動的計画法が使えるか？
 部分構造の最適性
 部分問題の再起解
 以上二つを満たせば動的計画法で解ける．
 最適解がその部分問題の最適解を必ず含む？
 部分問題の最適解は再帰的に使用される？
最長共通部分系列(LCS)

定理16.1(LCSの部分構造の最適性)
let :
1.
2.
3.
ならば
であり，かつ，
は
と
とのLCSである．
のとき，
ならば
は
ととのLCSである．
のとき，
ならば
は
と
とのLCSである．
最長共通部分系列(LCS)

定理16.1(LCSの部分構造の最適性)
 Proof：(1)背理法．
のとき

でないなら，
しかし，
なのでは最長ではない…矛盾
はLCS？
も背理法で．
LCSじゃないと仮定→LCSであるWを仮定→矛盾．
最長共通部分系列(LCS)

定理16.1(LCSの部分構造の最適性)
 Proof：(2)背理法．
，
のとき，が
のLCS？
LCSじゃないと仮定→LCSであるWを仮定→矛盾．
(3)も対称的に同じ．
最長共通部分系列(LCS)

動的計画法が使えるか？
 部分構造の最適性
○
 部分問題の再起解
 解を再帰的に表現したい．
 先ほどの最適性を使って表現する．
 系列
と
のLCSの長さを
として，
最長共通部分系列(LCS)

動的計画法を使うと
 異なる部分問題は
通りしかない
 最適値をボトムアップに計算する．
0 0 0 0 0 0 0
 最適解の構成は？
0 0 0 0 1 1 1
 右下から見る
0 1 1 1 1 2 2
一致すれば左上に
 一致しない
0 1 1 2 2 2 2



 この手法で
0 1 1 1 2 3 3
なら左に
なら上に
0 1 2 2 2 3 3
0 1 2 2 3 3 4
時間．
0 1 2 2 3 4 4
最適三角形分割問題

ある凸な多角形を考える
 この多角形の頂点と頂点とを結び，複数の三角
形に分割することを考える．
 その分割した三角形で定義できる重みを考える
 例：（総辺長，内接円の半径，…）
 三角形全てに対する重みの和を最小にする三角
形分割を求める
最適三角形分割問題

どう考えるか？
 解析木という考え方
 解を木構造で表現
辺
を根，
その他の既存の辺を葉，
引いた辺を節として，
三角形が一つの親子になる
木を構成する
 一つの解が一意に一つの
解析木と対応付け．
最適三角形分割問題

解析木は
 部分構造の最適性
がある！→動的計画法．
 実は…
 連鎖行列積も解析木を持つ
 連鎖行列積は最適三角形
分割問題の特殊例．
 確認すると…
最適三角形分割問題
 連鎖行列積そのものは(当然ながら)使えない．

同じ考え方で再帰を作る
 多角形
の
最適三角形分割の重みを
とすると，
動的計画法まとめ

動的計画法は再帰的に最適性がある問題に使
える．
 部分構造の最適性
→問題を小さく考える事ができた
 部分問題の重複性
→記憶することで時間コストを下げる
 解析木を作れるなら動的計画法が使える．
 しかしながら，ある一定の記憶領域と時間を必
要とする（線形時間や対数領域は無理）

Download Report