動的計画法の基本要素
部分構造最適性
問題の最適解が,その内部に,その部分問題に対する最適解を含む.
重みなし最短路問題
入力:有向グラフ,頂点
出力:辺数最小のから
への道
重みなし最短路問題が部分構造最適性を持つことの証明.(切貼り法を用いる)
問題が自明にならないようにと仮定.
から
への任意の道は中間頂点
を持つ.(
は
でも
でも良い)
道は部分道
と
に分解できる.
より短い
から
への道
が存在すると仮定.
を
に置き換えると
よりも短い道ができるので矛盾.
同様には
から
への最短路.
重みなし最長単純道問題
入力:有向グラフ,頂点
出力:辺数最大のから
への単純道
重みなし最長単純道問題が部分構造最適性を持たないことの証明.
最長単純道は部分道
と
に分解できない反例を示す.

上図のは
から
への最長単純道.
しかしは
から
への最長単純道でない.
部分問題重複性
問題に対する再帰アルゴリズムの部分問題の空間が“小さい”こと.
アルゴリズムが常に新しい部分問題を生成するのではなく,同じ部分問題を繰り返し解く場合.
最長共通部分列問題
部分列
列Zと列Xについて,Xから0個以上の文字を取り除いたあと,残りの文字を元の順序で連結することでZが得られるとき,ZはXの部分列であるという.
例. X = 〈A, B, C, B, D, A, B〉,Z = 〈B, C, D, B〉
共通部分列
列Xと列Yと列Zについて,ZがXとYの両方の部分列であるとき,ZをXとYの共通部分列という.
例. X = 〈A, B, C, B, D, A, B〉,Y = 〈B, D, C, A, B, A〉,Z = 〈B, C, B, A〉
最長共通部分列問題
入力:二つの列
と
出力:XとYの最長共通部分列
最長共通部分列問題はlongest-common-subsequence problem
と英語で表記し,LCS
問題と呼ばれることが多い.
LCS問題をシラミツブシ法で解いてみる.
与えられた二つの列と
に対して,Xの部分列を全て列挙(
個ある)し,Yの部分列か調べ,最長の共通部分列を記録する.
Xの部分列の個数から指数時間かかることが分かる.
接頭語
任意の列について,Xの 𝑖 番目の接頭語(prefix)を
と定義.
例. ,
,
は空列
LCSの部分構造最適性
と
を列,
を
と
の任意のLCSとする.
ならば,
であり,
は
と
のLCSである.
のとき,
ならば,
は
と
のLCSである.
のとき,
ならば,
は
と
のLCSである.
1の前半の証明.
と仮定.
の末尾に
を追加した列もXとYの共通部分列で長さが
k+1
なのでZより長い列.
これはZがLCSであることに矛盾.
1の後半の証明.
は
と
の長さが
k-1
の共通部分列.これがLCS(最長)であることを示す.
長さがk以上のと
の共通部分列Wが存在すると仮定.
Wにを付与すると,長さがk+1以上のXとYの共通部分列ができて矛盾.
2の証明.
ならばZは
とYの共通部分列.これがLCS(最長)であることを示す.
長さがk+1以上のとYの共通部分列Wが存在すると仮定.
WはとYの共通部分列でもあるので,ZがXとYのLCSである仮定に矛盾.
3の証明.
2と同様.
LCS問題の定式化
列と
のLCSの長さを
c[i, j]
と定義.
LCS問題の部分構造最適性から以下の漸化式を得る.
LCS問題のアルゴリズム

b[i,j] : LCSの再構成の用いる表
c[i,j] : と
のLCSの長さ
計算量は
最適2分探索木
最適2分探索木
ソート済みのn個のキーと各キー
を探索する確率
,Kが含まない値を示す「ダミーキー」
と探索が
で終わる確率
が与えられたとき,探索コストの期待値を最小化する2分探索木.


ダミーキー
は
未満,
は
以上,
は
と
の間の全ての値を表現する.
期待値の計算
一回の探索にかかる実コストを訪れた節点数,すなわち発見された節点のTにおける深さ+1と仮定.
一回の探索コストの期待値は以下の通り.
※ は木
における節点の深さ
シラミツブシ法
n個の節点を持つ任意の2分木の節点をキーでラベル付け.ダミーキーを追加.
n個の節点を持つ2分木の個数は
シラミツブシでは指数時間かかる.
部分構造最適性
最適2分探索木を求める問題が部分構造最適性を持つことを証明する.
最適2分探索木𝑇が部分木𝑇’を持つとすると,𝑇’よりも期待コストの小さい𝑇’’があるなら𝑇から𝑇’を切り取り代わりに𝑇’’を貼り込むことで, 𝑇よりも期待コストが小さくなり矛盾.
よって,最適2分探索木𝑇の部分木𝑇’も最適2分探索木.
最適解の構成
最適部分木の根はキーを根に持ち、これに対し左部分木と右部分木はそれぞれキー
と
を持つ.
全ての根の候補に対して左部分木と右部分木のそれぞれの最適2分探索木を決定することで問題の最適2分探索木を必ず発見できる.
を以下のように定義&漸化式が成り立つ.
アルゴリズム

計算量