アルゴリズムイントロダクション第15章後半の個人まとめ

はじめに

前回前半をやったので、後半やっていきます。
www.hanachiru-blog.com

テーマは同じく「動的計画法」です。

<br />

はじめに
動的計画法の基本要素
- 部分構造最適性
  - 重みなし最短路問題
  - 重みなし最長単純道問題
- 部分問題重複性
最長共通部分列問題
- 部分列
- 共通部分列
最長共通部分列問題
- 接頭語
LCSの部分構造最適性
LCS問題の定式化
LCS問題のアルゴリズム
最適2分探索木

動的計画法の基本要素

部分構造最適性

問題の最適解が，その内部に，その部分問題に対する最適解を含む．

重みなし最短路問題

入力：有向グラフ，頂点 $u, v$
出力：辺数最小の $u$ から $v$ への道

重みなし最短路問題が部分構造最適性を持つことの証明．（切貼り法を用いる）

問題が自明にならないように $u\neq v$ と仮定．
$u$ から $v$ への任意の道は中間頂点 $w$ を持つ．( $w$ は $u$ でも $v$ でも良い)
道 $u\overset{p}{\sim}> v$ は部分道 $u\overset{p_1}{\sim}> v$ と $u\overset{p_2}{\sim}> v$ に分解できる．

$p_1$ より短い $u$ から $w$ への道 $p_1'$ が存在すると仮定．
$p_1$ を $p_1'$ に置き換えると $p$ よりも短い道ができるので矛盾．
同様に $p_2$ は $w$ から $v$ への最短路．

重みなし最長単純道問題

入力：有向グラフ，頂点 $u, v$
出力：辺数最大の $u$ から $v$ への単純道

重みなし最長単純道問題が部分構造最適性を持たないことの証明．

最長単純道 $u\overset{p}{\sim}> v$ は部分道 $u\overset{p_1}{\sim}> v$ と $u\overset{p_2}{\sim}> v$ に分解できない反例を示す．

f:id:hanaaaaaachiru:20211206213823p:plain — 反例

上図の $𝑞→𝑟→𝑡$ は $𝑞$ から $𝑡$ への最長単純道．
しかし $𝑞→𝑟$ は $𝑞$ から $𝑟$ への最長単純道でない．

部分問題重複性

問題に対する再帰アルゴリズムの部分問題の空間が“小さい”こと．
アルゴリズムが常に新しい部分問題を生成するのではなく，同じ部分問題を繰り返し解く場合．

最長共通部分列問題

部分列

列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〉

最長共通部分列問題

入力：二つの列 $𝑋 = <𝑥_1, 𝑥_2,…,𝑥_𝑚>$ と $Y = <𝑦_1, 𝑦_2,…,𝑦_𝑚>$
出力：XとYの最長共通部分列

最長共通部分列問題はlongest-common-subsequence problemと英語で表記し，LCS問題と呼ばれることが多い．

LCS問題をシラミツブシ法で解いてみる．
与えられた二つの列 $𝑋 = <𝑥_1, 𝑥_2,…,𝑥_𝑚>$ と $Y = <𝑦_1, 𝑦_2,…,𝑦_𝑚>$ に対して，Xの部分列を全て列挙（ $2^𝑚$ 個ある）し，Yの部分列か調べ，最長の共通部分列を記録する．
Xの部分列の個数から指数時間かかることが分かる．

接頭語

任意の列 $𝑋 = <𝑥_1, 𝑥_2,…,𝑥_𝑚>$ について，Xの 𝑖 番目の接頭語(prefix)を $𝑋 = <𝑥_1, 𝑥_2,…,𝑥_𝑖>$ と定義．
例. $𝑋 = <𝐴, 𝐵, 𝐶, 𝐵, 𝐷, 𝐴, 𝐵>$ ， $𝑋_4 = <𝐴, 𝐵, 𝐶, 𝐵>$ ， $𝑋_0$ は空列

LCSの部分構造最適性

$𝑋 = 〈𝑥_1, 𝑥_2,…,𝑥_𝑚〉$ と $Y = 〈𝑦_1, 𝑦_2,…,𝑦_n〉$ を列， $Z = 〈z_1, z_2,…,z_k〉$ を $X$ と $Y$ の任意のLCSとする．

$x_m = y_n$ ならば， $z_k = x_m = y_n$ であり， $Z_{k-1}$ は $X_{m-1}$ と $Y_{n-1}$ のLCSである．

$x_m \neq y_n$ のとき， $z_k \neq x_m$ ならば， $Z$ は $X_{m-1}$ と $Y$ のLCSである．

$x_m \neq y_n$ のとき， $z_k \neq y_n$ ならば， $Z$ は $X$ と $Y_{n-1}$ のLCSである．

1の前半の証明．
$z_k \neq x_m = y_n$ と仮定． $Z$ の末尾に $x_m$ を追加した列もXとYの共通部分列で長さがk+1なのでZより長い列．
これはZがLCSであることに矛盾．

1の後半の証明．
$Z_{k-1}$ は $X_{m-1}$ と $Y_{n-1}$ の長さがk-1の共通部分列．これがLCS(最長)であることを示す．
長さがk以上の $X_{m-1}$ と $Y_{n-1}$ の共通部分列Wが存在すると仮定．
Wに $x_m = y_n$ を付与すると，長さがk+1以上のXとYの共通部分列ができて矛盾．

2の証明．
$z_k \neq x_m$ ならばZは $X_{m-1}$ とYの共通部分列．これがLCS(最長)であることを示す．
長さがk+1以上の $X_{m-1}$ とYの共通部分列Wが存在すると仮定．
Wは $X_m$ とYの共通部分列でもあるので，ZがXとYのLCSである仮定に矛盾．

3の証明．
2と同様．

LCS問題の定式化

列 $X_i$ と $Y_j$ のLCSの長さをc[i, j]と定義．
LCS問題の部分構造最適性から以下の漸化式を得る．

$c [ i,j ] = \begin{cases} 0 & if　i=0\vee j=0 \\ c[ i-1, j-1 ]+1 & if　i,j>0 \wedge x_i = y_j \\ max(c [ i, j-1 ] , c [ i-1,j ] ) & if　i,j>0 \wedge x_i \neq y_j \end{cases}$

LCS問題のアルゴリズム

f:id:hanaaaaaachiru:20211206222346p:plain — プログラム

b[i,j] : LCSの再構成の用いる表
c[i,j] : $X_i$ と $Y_j$ のLCSの長さ

計算量は $\Theta(m,n)$

最適2分探索木

ソート済みのn個のキー $𝐾=<𝑘_1,𝑘_2,…,𝑘_𝑛>(𝑘_1<𝑘_2<…<𝑘_𝑛)$ と各キー $𝑘_𝑖$ を探索する確率 $𝑝_𝑖$ ，Kが含まない値を示す「ダミーキー」 $𝑑_0, 𝑑_1, …,𝑑_𝑛$ と探索が $𝑑_𝑖$ で終わる確率 $𝑞_𝑖$ が与えられたとき，探索コストの期待値を最小化する２分探索木．

f:id:hanaaaaaachiru:20211206223043p:plain — 以下のpi,qi，n=5のときの最適2分探索木

f:id:hanaaaaaachiru:20211206223220p:plain — 出現確率

ダミーキー

$𝑑_0$ は $𝑘_1$ 未満， $𝑑_𝑛$ は $𝑘_𝑛$ 以上， $𝑑_𝑖$ は $𝑘_𝑖$ と $𝑘_{𝑖+1}$ の間の全ての値を表現する．

期待値の計算

一回の探索にかかる実コストを訪れた節点数，すなわち発見された節点のTにおける深さ+1と仮定．

一回の探索コストの期待値は以下の通り．
$E [search cost in T ] = \sum_{i=1}^n(depth_T(k_i) + 1)\cdot p_i + \sum_{i=0}^n(depth_T(d_i) + 1)\cdot q_i$
$E [search cost in T ] = 1+ \sum_{i=1}^ndepth_T(k_i)\cdot p_i + \sum_{i=0}^ndepth_T(d_i)\cdot q_i$