15.3 動的計画法の基本要素

工学的な見地からは与えられた問題に対して動的計画法の解を探すべきか否かを判断できることが重要である。本節では動的計画法が適用できるための最適化問題が持たなければならない重要な2つの特徴、部分構造最適性と部分問題重複性について調べる。また、トップダウン再帰方式の中で部分問題重複性を有効に利用するために履歴管理が果たす役割をより詳しく検討する。

部分構造最適性

動的計画法によって最適化問題を解くための第1段階は最適解の構造を特徴づけることである。問題の最適解が、その内部に、その部分問題に対する最適解を含むとき、この問題は部分構造最適性を持つと言う。ある問題が部分構造最適性を持つなら、それは動的計画法がこの問題に対して適用可能であることを示す良い兆候である。

動的計画法では問題の最適解をその部分問題の最適解から構成する。だから、考察する部分問題の範囲が最適解の構成に使われる部分問題を含んでいることを保証する必要がある。

ロッド切り出し問題と連鎖行列積問題は部分構造最適性を持っていた。

部分構造最適性の発見に至る以下の共通の手順に気づく。

金属棒の最初の切断箇所の選択や連鎖行列の分割場所の選択といった、ある選択から与えられた問題の解が構成されることを示す。行った選択からいくつかの解くべき部分問題が発生する
与えられた問題に対して最適解を導く選択が与えられていると仮定する。この時点では最適な選択を行う方法は吟味せず、最適な選択が与えられているとだけ仮定する。
与えられた最適な選択から生ずる部分問題を決定し、結果として現れる部分問題の空間を適切に特徴づける方法を定める
与えられた問題の最適解の中で用いられる部分問題の解が、部分問題の最適解であることを「切り貼り法」を用いて証明する。この証明法では、ある部分問題の解が最適ではないと仮定し矛盾を導くことを証明する。最適ではないと仮定した部分問題の解を切り取り、最適解に貼り替えると元の問題に対するより良い解を得ることができるので、与えられた元の問題の解は最適であるという仮定に対する矛盾が導かれる。複数の部分問題が存在する場合にもおおよそ同様であり、「切り貼り法」を複数の場合を扱えるように簡単に変更できる。

部分問題空間を特徴づけるための信頼できる方法は、最初は空間をできるだけ簡単にしておき、後で必要に応じて拡張することである。

ロッド切り出し問題であれば、長さ i のみ
連鎖行列積問題であれば、i のみではなく i と j の組

問題領域によって部分構造最適性は次の2点で違いがある

元の問題の最適解が利用する部分問題の個数
最適解が利用する部分問題の候補の個数

ロッド切り出し問題
- サイズ n の最適解は1つ(サイズ n - i)の部分問題の最適解のみを使う
- i を決定するために n 個の i の候補を全て考慮する必要がある
連鎖行列積問題
- A_i ... A_j の最適解は2つ(A_i ... A_k, A_{k+1} ... A_j)の部分問題の最適解を使う
- k を決定するために j - i 個の k の候補を全て考慮する必要がある

動的計画アルゴリズムの実行時間はおおよそ2つの要因
* 部分問題の総数
* 各部分問題で考慮しなければならない候補
の積に依存する

ロッド切り出し問題
- 部分問題の総数 \Theta (n)
- 選択肢は n 個
- 実行時間は O(n^2)
連鎖行列積問題
- 部分問題の総数 \Theta (n^2)
- 選択肢は n-1 個
- 実行時間は O(n^3)

多くの場合、部分問題グラフを用いても同様の解析ができる

各頂点 => 部分問題に対応
接続する辺 => 部分問題に対する選択肢に対応

動的計画法は部分構造最適性をボトムアップふうに用いることが多い。すなわち、ある問題を解くには、部分問題に対する最適解をまず発見し、すべての部分問題を解いてしまってから、この問題の最適解を発見する。この問題の最適解を発見するには、この問題を解くために利用する部分問題を決定する必要がある。この問題の解のコストは、部分問題にかかるコストと部分問題の選択に直接起因するコストの和である。

ロッド切り出し問題
- i = 0, 1, ... , n-1 に対して、長さ i の部分問題を解く
- 長さ n に最適な長さ i の部分問題を決定する
連鎖行列積問題
- i, j に対して、A_i ... A_j の最適括弧付けを決定する
- A_k を決定する

注意をすべきこと

部分構造最適性が適用できないにも関わらず、そのことを仮定することがないように気をつける。

有向グラフ G = (V, E) と頂点 u, v ∈ V が与えられたとき、次の2つの問題を考える。

重み無し最短路: 辺数最小の u から v への道を発見せよ。最短路が単純でなければ閉路を除去してより短い道を作ることができるので、最短路は単純である。
重み無し最長単純道: 辺数最大の u が v への単純道を発見せよ。単純性が要請されていなければ、閉路を好きなだけ周り、任意に長い道を作れるので、単純性は必要。

重み無し最短路問題が部分構造最適性を持つことの証明

u から v への任意の道 p は中間地点 w を持つ。
p(u => v)はp_1(u => w)とp_2(w => v)に分解でき、pの辺数はp_1の辺数とp_2の辺数の和になる。「切り貼り法」を用いて証明すると、pの辺数が最小の場合はp_1の辺数とp_2の辺数は最小のパターンとなる。次に全ての中間地点 w を考えると、最短路を発見できる。よって、部分構造最適性を持つ。

重み無し最長単純路問題の場合

部分構造最適性を持たない。よって、この問題を解く動的計画法は知られていない。事実、この問題はNP-完全。

最長単純道の部分構造が最短路と全く異なる理由

最長単純道は部分問題が独立ではない
最短路の部分問題は独立

部分問題重複性

動的計画法を適用するために最適化問題に必要とされる第2の特徴は、この問題に対する再帰アルゴリズムの部分問題の空間が"小さい"ことである。

つまり、このアルゴリズムが常に新しい部分問題を生成するのではなく、同じ部分問題を繰り返し解く場合である。できれば、異なる部分問題の総数が入力サイズの多項式であって欲しい。再帰アルゴリズムが同じ問題を繰り返し訪れるとき、その最適化問題は部分問題重複性を持つと言う。動的計画法では各部分問題を1度だけ解き、必要なときに定数時間で検索できる表にこの解を保存することで、部分問題の重複を上手に利用する。

ロッド切り出し問題 => 指数回数の呼び出しを2次関数時間に改良した

RECURSIVE-MATRIX-CHAIN(p, i, j)
if i == j
  return 0
m[i, j] = \infty
for k = i to j - 1
  q = RECURSIVE-MATRIX-CHAIN(p, i, k) + RECURSIVE-MATRIX-CHAIN(p, k + 1, j) + p_{i-1} p_k p_j
  if q < m[i, j]
    m[i, j] = q
return m[i, j]

連鎖行列積問題 => 指数回数の呼び出し(下記で証明する)を3次関数時間に改良した

RECURSIVE-MATRIX-CHAINが必要とする計算時間を T(n) とする。
1-2行: 1単位時間
6-7行: 1単位時間
5行の積: 1単位時間

\begin{array}{ll}
T(1) \geq 1 & n = 1\\
T(n) \geq 1 + \sum_{k=1}^{n-1} (T(k) + T(n-k) + 1) & n > 1 
\end{array}

\sum_{k=1}^{n-1} (T(k) + T(n-k) + 1) = n - 1 + 2 \sum_{k=1}^{n-1} T(k)

なので

T(n) \geq n + 2 \sum_{k=1}^{n-1} T(k)

置き換え法を用いて

T(n) = \Omega(2^n)

を証明する。具体的には

すべての n \geq 1 について T(n) \geq 2^{n-1} を示す \\
T(1) \geq 1 = 2^0 なので、 n = 1 のときは自明 \\
n - 1 \geq k \geq 2 に対して成り立つとして \\
T(n) \geq n + 2 \sum_{i=1}^{n-1} T(i) \\
= n + 2 \sum_{i=1}^{n-1} 2^{i-1} \\
= n + 2(2^{n-1} - 1) \\
= 2^n - 2 + n \\
\geq 2^{n-1}

ある問題の自然な再帰解に対する再帰木が同じ問題を何度も含んでおり、異なる部分問題の総数が少ないときには動的計画法によって常に効率を改善でき、その効果はときに劇的である

最適解の再構成

実用的な観点から、各部分問題について行った選択を表に保存してあるコストから再構成しなくて済むように、この情報も合わせて表に保存しておくことがよく行われる。

ロッド切り出し問題 => 先頭からの長さ i
連鎖行列積問題 => 行列の分割位置 k

連鎖行列積問題で選択結果の表を保存していなければ A_i ... A_j の最適括弧付に利用する部分問題を決定するのに j - i 個の候補を検討する必要があり、 j - i は定数ではない。したがって、与えられた問題の解のために選択した部分問題を再構成するために \Theta (j-i) = \omega (1) 時間が必要になる。しかし、保存しておけば O (1) 時間で再構成できる。

履歴管理

MEMOIZED-MATRIX-CHAIN(p)
n = p.length - 1
m[1..n, 1..n] を新しい表とする
for i = 1 to n
  for j = i to n
    m[i, j] = \infty
return LOOKUP-CHAIN(m, p, 1, n)

LOOKUP-CHAIN(m, p, i, j)
if m[i, j] < \infty
  return m[i, j]
if i == j
  m[i, j] = 0
else for k = i to j - 1 // here
  q = LOOKUP-CHAIN(m, p, i, k) + LOOKUP-CHAIN(m, p, k+1, j) + p_{i-1} p_k p_j
  if q < m[i, j]
  m[i, j] = q
return m[i, j]

実行時間は O(n^3) である。LOOKUP-CHAINの第5行を \Theta (n^2) 回実行する。

m[i, j] = \infty を満たすタイプで第3-9行を実行する
m[i, j] < \infty を満たすタイプでLOOKUP-CHAINは第2行で戻る

タイプ1の呼び出しが各要素に対して1回、全部で \Theta (n^2) 回発生する。
タイプ2の呼び出しはタイプ1が行う再帰呼び出しとして発生する。任意に与えられたLOOKUP-CHAINの呼び出しが再帰呼び出しをするとすれば、その回数は常に O(n) (= j-i) で抑えられているから、全体で O(n^3) である。タイプ2の実行時間は O(1) なので、総計算時間は O(n^3) である。履歴管理によって \Omega (2^n) 時間アルゴリズムを O(n^3) 時間アルゴリズムに改良できた。

まとめると、連鎖行列積問題は、どちらの方法でも O(n^3) 時間で解ける。どちらも部分問題重複性を上手に利用している。異なる部分問題は全部で \Theta (n^2) 個しかなく、各部分問題の解を1度しか計算しない。(何度も計算する再帰アルゴリズムでは指数時間かかってしまう)

すべての部分問題を1度は解かなければならないなら、再帰のためのオーバーヘッドが必要なく、表管理のオーバーヘッドも小さいボトムアップ型がトップダウン型よりも定数倍優れている。しかも、いくつかの問題では表へのアクセス順序を規則化することで、時間と記憶容量をさらに節約できる。
一方部分問題空間に属するすべての部分問題を解く必要がないなら、トップダウン型はどうしても解かなければならない部分問題だけを解くという長所がある。

練習問題

15.3-1

連鎖行列積問題において最適乗算回数を決定するにはつぎの2つの方法のどちらの効率がよいか？

すべての括弧付を列挙してそれぞれに対して乗算回数を計算する
RECURSIMATRIX-CHAINを実行する

結局どちらも全パターンを計算することになるが、オーバーヘッドが小さい

15.3-2

手続き MERGE-SORT が 16要素からなる配列上で働く場合の再帰木を描け。MERGE-SORTのような効率の良い分割統治アルゴリズムの高速化に履歴管理が役立たない理由を説明せよ。

(3, 9, 2, 13, 14, 0, 4, 12, 1, 6, 11, 10, 5, 7, 15, 8)
=> ((3, 9, 2, 13, 14, 0, 4, 12), (1, 6, 11, 10, 5, 7, 15, 8))
=> (((3, 9, 2, 13), (14, 0, 4, 12)), ((1, 6, 11, 10), (5, 7, 15, 8)))
=> ((((3, 9), (2, 13)), ((14, 0), (4, 12))), (((1, 6), (11, 10)), ((5, 7), (15, 8))))
=> (((((3), (9)), ((2), (13))), (((14), (0)), ((4), (12)))), ((((1), (6)), ((11), (10))), (((5), (7)), ((15), (8)))))
=> ((((3, 9), (2, 13)), ((0, 14), (4, 12))), (((1, 6), (10, 11)), ((5, 7), (8, 15))))
=> (((2, 3, 9, 13), (0, 4, 12, 14)), ((1, 6, 10, 11), (5, 7, , 8, 15)))
=> ((0, 2, 3, 4, 9, 12, 13, 14), (1, 5, 6, 7, 8, 10, 11, 15))
=> (0, ..., 15)

そもそも1回しか部分問題は呼ばれないから

15.3-3

連鎖行列積問題の変形として、必要なスカラー乗算回数を最大化するように行列の積を括弧付けする問題を考える。この問題は部分構造最適性を持つか？

持つ。最大のコストの計算は内部ではそれ未満の長さの最大のコストとする問題を利用するる。

(A_i A_{i+1} ... A_k)(A_{k+1} ... A_j) を計算するコスト = \\
(A_i A_{i+1} ... A_k) を計算するコスト \\
+ (A_{k+1} ... A_j) を計算するコスト \\
+ A_{i..k} A_{k+1..j} の積を計算するコスト

左部分と右部分を計算するコストのそれぞれが最大でないならば、より大きいものに置き換えると・・・という「切り貼り法」で証明でき、部分構造最適性を有することを示せる。

15.3-4

A_i ... A_j について p_{i-1} p_k p_j を最小化する行列 Ak を分割点として選択するという貪欲法が、最適解を導かない例を示せ

1000, 10, 2, 1, 200(1000x10, 10x2, 2x1, 1x200) とする

貪欲法

p_k は 1(k は 3) => (A_1 A_2 A_3)(A_4)
前方の p_k 2(k は 2) => ((A_1 A_2) A_3)(A_4)
A_1 A_2 の計算回数 => 1000 * 10 * 2 = 20,000
A_{1..2} A_3 の計算回数 => 1000 * 2 * 1 = 2,000
A_{1..3} A_4 の計算回数 => 1000 * 1 * 200 = 200,000
合計 222,000

最適解

((A_1 (A_2 A_3)) A_4)

A_2 A_3 の計算回数 => 10 * 2 * 1 = 20
A_1 A_{2..3} の計算回数 => 1000 * 10 * 1 = 10,000
A_{1..3} A_4 の計算回数 => 1000 * 1 * 200 = 200,000

15.3-5

ロッド切り出し問題に新たな制約として、切り出すことができる長さ i の金属棒の本数の上限 l_i が与えられるとする。
部分構造最適性が成立しないことを示せ。

n = 4 で l_2 = 1 と制限されているとすると

r_2 = 5 で r_4 = r_2 + r_2 = 10 としたいができない。部分問題同士が独立ではなく、自身の中で最適を考えればよいわけでではなくなっている。

15.3-6

通貨の両替問題

1, 2, ... , n と名付けられた n 個の通貨の両替が可能であり、あなたが現在持っている通貨を1, 最終的に手に入れたい通貨をnとする。通貨の組iとjに対する交換比率を r_ij とする。両替には手数料が必要で、k回の両替にかかる手数料を c_k とする。すべての k = 1, 2, ..., n に対して c_k = 0ならば、通貨1をnに両替するための最適な両替手順を発見する問題は部分構造最適性を持つことを証明せよ。

j => i の変換はできないっぽい。あったら増殖するループ見つけたら無限大に発散するが・・・

iからjへの最適な手順による両替をp_ijとすると
p_1n = p_1k * p_kn
が成り立つ。成り立たないならばより有利なものに置き換えると・・・という「切り貼り法」で証明でき、部分構造最適性を持つことを示せた。

手数料 c_k が任意の値であれば、必ずしも部分構造最適性を持たないことを証明せよ。

ある k を超えると十分に大きくしてしまえば、実質的に両替回数を制限していることになる。そうすると、15.3-5と同じで、2つに分割した部分問題同士が独立ではなくなる。

15. Dynamic Programming, 15.3 動的計画法の基本要素