15. Dynamic Programming, 15.1 ロッド切り出し

# 15.0 序文

## 動的計画法とは

動的計画法は分割統治法と同様、部分問題の解を統合することによって問題を解く方法である。

* 分割統治法 - 問題を独立な部分問題に分割し、部分問題を再帰的に解き、その後でこれらの解を組み合わせて元の問題の解を得る
* 動的計画法 - 部分問題の一部が一致しているとき、すなわち、これらの部分問題が「部分部分問題」を共有している時に適用する。各部分部分問題を1度だけ解き、その解を表に保存することで、部分部分問題を再計算する労を避ける

## 代表的な適用例

最適化問題

以下の4つの段階を経て開発する

1. 最適解の構造を特徴づける
2. 最適解の値を再帰的に定義する
3. (多くの場合にはボトムアップ方式で)最適解の値を計算する
4. 計算された情報から1つの最適解を構成する

# 15.1 ロッド切り出し

## 問題設定

1本の金属棒からいくつかの金属棒を切り出すとき、切断する場所を決定する問題

長さがnインチの1本の金属棒と i = 1, 2, ... , n に対する価格 p_i の表が与えられたとき、この金属棒から切り出される金属棒を価格表に従って販売して得ることができる収入の最大値を計算せよ

 長さ i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
 :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--:
 価格 p_i | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30

## n = 4 の場合

 分割方法 | 4 | 3,1 | 2,2 | 2,1,1 | 1,1,1,1 
 :--: | :--: | :--: | :--: | :--: | :--: 
 合計価格 | 9 | 9 | 10 | 7 | 4 

## n = 10 まで

 長さ i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
 :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--:
 合計価格 | 1(1) | 5(2) | 8(3) | 5(2) + 5(2) | 8(3) + 5(2) | 17(6) | 17(6) + 1(1) | 17(6) + 5(2) | 17(6) + 8(3) | 30(10)

## 一般化

一般に n >= 1 に対する収入 r_n を、 n 未満の長さの金属棒に対する最適収入を用いて

$$ r_n = max(p_n, r_1 + r_{n-1}, r_2 + r_{n-2}, ..., r_{n-1} + r_1) $$

と表現できる。サイズが n の元の問題を解くために同じ形の部分問題を解く必要があるが、解くべき部分問題のサイズは元の問題サイズ n より真に小さいことに注意する。最初の切断を実行して1本の金属棒から2本の金属棒を切り出してしまうと、切り出された金属棒をロッド切り出し問題の2つの独立したインスタンスと考えることができる。元の問題に対する最適解は2つの部分問題の最適解を含んでいて、それぞれ各金属棒片から得ることができる収入を最大化している。我々はロッド切り出し問題には部分構造最適性があると言う。

分割を金属棒の左端から切り出された長さ i の金属棒とその右側に残る長さ n - i の部分から構成されるとみなすことができる。

$$ r_n = max_{1 \leq i \leq n} (p_i + r_{n-i}) $$

この定式化では最適解は2個ではなく1個の関連する部分問題、すなわち右側に残った部分の最適解を含む

## 再帰的トップダウン型実現

```
CUT-ROD(p, n)
if n == 0
  return 0
q = - $$ \infty $$
for i = 1 to n
  q = max(q, p[i] + CUT-ROD(p, n - i))
return q
```

上記実装は n が大きくなるとと端に実行速度が遅くなる

 長さ n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
 :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--:
 CUT-PRODの内部呼び出し回数 | 0 | 1 | 2 + 1 | 4 + 2 + 1 | 8 + 4 + 2 + 1 | 16 + 8 + 4 + 2 + 1 | ... |  |  |  |  |
 CUT-PRODの総呼び出し回数 | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | ...

O(2^n)ぐらい計算量が必要になる・・・ 

各 i = 1, 2, ..., n に対して、CUT-ROD(p, n)はCUT-ROD(p, n - i)を呼び出す。すなわち、 j = 0, 1, ..., n - 1 に対して CUT-ROD(p, n) は CUT-ROD(p, j) を呼び出している。この手続を再帰的に開いていくと、行われた仕事の量は、n の関数として爆発的に増加する。

CUT-RODの実行時間を解析するために、第2引数の値をnとしてCUT-RODが呼び出されたときに、実行の過程で再帰的に CUT-ROD を呼び出した回数を T(n) とする。この回数は再帰木においてラベル n を持つ節点を根とする部分木に属する節点数と一致する。この回数には根における初期呼び出しが含まれる。したがって T(0) = 1 かつ $$ T(n) = 1 + \sum_{j=0}^{n-1} T(j) $$ である。先頭の1はねにおける呼び出し、項T(j)は、j = n - i とするとき、 CUT-ROD(p, n - i) が行った呼び出しの回数である。

練習問題 15.1-1 では T(n) = 2^n を証明する。

## 最適なロッド切り出しへの動的計画法の適用

単純な再帰に基づく解が同じ部分問題を繰り返し解くという理由で非効率であることがわかったので、各部分問題を解いたときにその解を保存することによって、各部分問題を1度だけ解けば十分なようにする。後でこの部分問題の解を再び参照する必要が出てきたときにはそれを再計算するのではなく保存してある解を検索する。
動的計画法は計算時間を冊役するために記憶を余分に利用する。これは、時間-領域トレードオフを示す例である。節約できる時間は劇的であり、指数時間解法を多項式時間解法に変換できることもある。関連する相異なる部分問題数が入力サイズの多項式時間で抑えられており、各部分問題がそれぞれ多項式時間で解ける場合には、動的計画法に基づくアルゴリズムは多項式時間で走る。

動的計画法には通常2つの実現方法がある。

1. 履歴管理を用いるトップダウン方式(メモ化再帰) - 自然な再帰で記述するが、各部分問題の解を保存し、保存してあれば計算せずにそちらを参照するようにする
2. ボトムアップ方式 - すべての部分問題をサイズの昇順でソートし、サイズの小さいものから順番に解いていく

### 履歴管理を用いるトップダウン方式の CUT-ROD

r[0..n]を新しい配列とする

```
for i = 0 to n
  r[i] = $$ - \infty $$
return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r)
if r[n] >= 0
  return r[n]
if n == 0
  q = 0
else q = $$ - \infty $$
  for i = 1 to n
    q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r))
r[n] = q
return q
```

### ボトムアップ方式の CUT-ROD

r[0..n]を新しい配列とする

```
BOTTOM-UP-CUT-ROD(p, n)
r[0] = 0
for j = 1 to n
  q = $$ - \infty $$
  for i = 1 to j
    q = max(q, p[i] + r[j - i])
  r[j] = q
return r[n]
```

実行時間はどちらも $$ \Theta (n^2) $$ である

## 部分問題グラフ

動的計画法をある問題に適用することを考えるときには関連する部分問題の集合と部分問題間の関係を理解する必要がある。

ボトムアップ型の動的計画法では、任意の部分問題 x に対して x を解く前に x に隣接するすべての部分問題 y を解かなければならないという制約の下で部分問題グラフに現れるすべての部分問題を解く。

部分問題グラフ G = (V, E) のサイズから動的計画アルゴリズムの実行時間が決定できる場合がある。各部分問題をちょうど1度しか解かないから、各部分問題を解くために必要な時間の和が実行時間になる。典型的な場合には

* ある部分問題の解の計算時間はその部分問題に対応する部分問題グラフ上の頂点の次数(外向辺の数)に比例
* 部分問題の数は部分問題グラフの頂点数と一致

この場合には、動的計画法の実行時間は頂点数と辺数の線形時間である

## 解の再構成

各部分問題に対して最適値だけでなく、最適値を達成する選択を保存するようにできる

各金属棒のサイズ j に対して、最大収入 r_j とともに r_j を達成するために左端から切り取る金属棒の長さ s_j を計算する拡張版の擬似コード

```
EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
r[0..n]とs[1..n]を新しい配列とする
r[0] = 0
for j = 1 to n
  q = $$ - \infty $$
  for i = 1 to j
    if q < p[i] + r[j - i]
      q = p[i] + r[j - i]
      s[j] = i
  r[j] = q
return r and s
```

```
PRINT-CUT-ROD-SOLUTION(p, n)
(r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
while n > 0
  print s[n]
  n = n - s[n]
```

 長さ i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
 :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--:
 r[i] | 0 | 1 | 5 | 8 | 10 | 13 | 17 | 18 | 22 | 25 | 30
 s[i] |  | 1 | 2 | 3 | 2 | 2 | 6 | 1 | 2 | 3 | 10

## 練習問題

### 15.1-1

T(0) = 1 と $$ T(n) = 1 + \sum_{j=0}^{n-1} T(j) $$ から T(n) = 2^n が導けることを示せ

----

任意の0 <= i <= n に対して T(i) = 2^i とした時、T(n + 1) = 1 + 1 + 2 + 2^2 + 2^3 + ... + 2^n = 2^(n + 1)
n = 0 のときは T(0) = 2^0 = 1 を満たしているので

### 15.1-2

長さ i の金属棒の密度 p_i / i が最大になるものから切り出していく貪欲法が最適とならない例を示せ

----

 長さ i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
 :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--:
 価格 p_i | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30
 密度 p_i / i | 1 | 2.5 | 8/3 | 2.25 | 2 | 17/6 | 17/7 | 2.5 | 8/3 | 3

 長さ i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
 :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--:
 合計価格 | 1(1) | 5(2) | 8(3) | 5(2) + 5(2) | 8(3) + 5(2) | 17(6) | 17(6) + 1(1) | 17(6) + 5(2) | 17(6) + 8(3) | 30(10)

長さ 4 の時に 8/3 > 5/2 なので、長さ 3 で切り出してしまうと、合計が 8(3) + 1(1) = 9 となってしまうが、正しくカットした場合は 5(2) + 5(2) = 10 とできる 

### 15.1-3

1回の切断にコストcがかかるパターン

----

```
BOTTOM-UP-CUT-ROD-WITH-COST(p, n, c)
r[0] = 0
for j = 1 to n
  q = $$ - \infty $$
  for i = 1 to j - 1
    q = max(q, p[i] + r[j - i] - c)
  r[j] = max(q, p[j])
return r[n]
```

### 15.1-4

MEMOIZED-CUT-ROD の EXTENDED 版

----

```
for i = 0 to n
  r[i] = $$ - \infty $$
return EXTENDED-MEMOIZED-CUT-ROD-AUX(p, n, r) and s

EXTENDED-MEMOIZED-CUT-ROD-AUX(p, n, r)
if r[n] >= 0
  return r[n]
if n == 0
  q = 0
else q = $$ - \infty $$
  for i = 1 to n
    if q < p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r)
      q = p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r)
      s[j] = i
r[n] = q
return q
```

### 15.1-5

```math
F_0 = 0 \\
F_1 = 1 \\ 
F_i = F_{i - 1} + F_{i -2}, i \geqq 2 のとき
```

によってフィボナッチ数は定義されている。n 番目のフィボナッチ数をO(n)で計算する動的計画アルゴリズムを設計せよ

----

```scala
def fibonacci(n: Int): Int = {
  val answerBuf = scala.collection.mutable.ArrayBuffer.empty[Int]
  answerBuf += 0
  answerBuf += 1
  for (i <- Range(2, n + 1)) {
    answerBuf += answerBuf(i - 1) + answerBuf(i - 2)
  }
  answerBuf(n)
}
```