第16章　動的計画法 アルゴリズムイントロダクション

動的計画法(DP) とは Dynamic Programming 最適化問題に使用される手法 Programing : 表を引く手法 適用可能な問題には構造的な制限がある． 適用可能であれば効率的に最適解を算出可

動的計画法(DP) の構造 基本的に以下の構造 …どういうこと？ 1. 最適解の構造を特長づける 2. 最適解の値を再帰的に定義する． 3. ボトムアップ形式で最適解の値を計算 4. 求められた情報から一つの最適解を構成 …どういうこと？ 最適解の中に部分的に最適な解があればOK！

連鎖行列積 DPで効率よく解く事の出来る問題の一例 n個の行列の積を考える どの順番で計算すると計算回数が一番少なくなる？

連鎖行列積 総当たりで計算すると… 通り数は適切なカッコの付け方 総通り数は これは碁盤目状の道を対角線に向かって進むときに対角線を超えない通り方と等しい （対角線を超える＝カッコの対応が正しく付かない） 総通り数は Stirling‘s formula　　　　　　　から導出． 指数的に増えてくるのであまり頭良くない．

連鎖行列積 最適解を観察してみる が最適解だとする． 二つの積から順々に構成することが可能． 最適解の構造を特長付けできた． 　　　　　　　　　　が最適解だとする． この解は部分問題の最適解　　　　　　　　を持つ． 最適解が他のパターンだとしても， などの部分的な最適解を部分的に含む． 二つの積から順々に構成することが可能． 最適解の構造を特長付けできた．

連鎖行列積 最適解の値を再帰的に定義 　　 : 行列積　　　　　にかかるコスト　　

連鎖行列積 ボトムアップに最適解を計算 部分問題に対する最適解を計算 再帰的に計算が可能 再帰するたびに計算するのではなく 　その値を表に覚えておく 129 63 75 95 21 35 57 6 20 8

連鎖行列積 最適解を構成 最適解の構造を構成したい． 積がどこで分かれているのかを示す値を別の表で記憶する 129 63 75 95 1 1 129 63 75 95 1 1 3 3 21 35 57 2 3 3 6 20 3 3 8 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. ならば であり，かつ， は と とのLCSである． 1.　　 　ならば　　　　　であり，かつ， 　　　　　　　　　は　　と　　とのLCSである． 2.　　 　のとき，　　 ならば 　は　　 と　とのLCSである． 3.　　　 のとき，　　 ならば 　　　　　　　　は　 と　　との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の長さを　　として，

最長共通部分系列(LCS) 動的計画法を使うと 異なる部分問題は 通りしかない 最適解の構成は？ 最適値をボトムアップに計算する． 異なる部分問題は　　　通りしかない 最適値をボトムアップに計算する． 最適解の構成は？ 右下から見る 一致すれば左上に 一致しない 　　　なら左に 　　　なら上に この手法で　　　　時間． 1 1 1 1 1 1 1 2 2 1 1 2 2 2 2 1 1 1 2 3 3 1 2 2 2 3 3 1 2 2 3 3 4 1 2 2 3 4 4

最適三角形分割問題 ある凸な多角形を考える この多角形の頂点と頂点とを結び，複数の三角形に分割することを考える． その分割した三角形で定義できる重みを考える 例：（総辺長，内接円の半径，…） 三角形全てに対する重みの和を最小にする三角形分割を求める

最適三角形分割問題 どう考えるか？ 解析木という考え方 解を木構造で表現 一つの解が一意に一つの 解析木と対応付け． 辺 を根， 辺　　を根， その他の既存の辺を葉， 引いた辺を節として， 三角形が一つの親子になる 木を構成する 一つの解が一意に一つの 　解析木と対応付け．

最適三角形分割問題 解析木は 部分構造の最適性 実は… 確認すると… がある！→動的計画法． 連鎖行列積も解析木を持つ 連鎖行列積は最適三角形 分割問題の特殊例． 確認すると…

最適三角形分割問題 連鎖行列積そのものは(当然ながら)使えない． 同じ考え方で再帰を作る 多角形　　　　　の 最適三角形分割の重みを 　　とすると，

動的計画法まとめ 動的計画法は再帰的に最適性がある問題に使える． 部分構造の最適性 部分問題の重複性 解析木を作れるなら動的計画法が使える． →問題を小さく考える事ができた 部分問題の重複性 →記憶することで時間コストを下げる 解析木を作れるなら動的計画法が使える． しかしながら，ある一定の記憶領域と時間を必要とする（線形時間や対数領域は無理）