動的計画法と貪欲法最適部分構造・LCS・ナップサック・貪欲法が正しい条件

動的計画法は、問題の最適解が部分問題の最適解から組み立てられ（最適部分構造）、同じ部分問題が何度も現れる（部分問題の重なり）ときに、部分問題の答えを表に記録して1回ずつだけ解く方法である。漸化式を立て、依存の順に表を埋め、最後に表をたどって解を復元する。貪欲法はその時点で最もよい選択を1つ確定して進む方法で、貪欲選択性と最適部分構造が証明できる問題でだけ最適解を与える。

アルゴリズムとデータ構造の第4単元（全4単元）。先に読む単元：計算量と漸化式

情報系院試の問題集・ロードマップ

東大情報理工・東京科学大・阪大の大学別に、出題マップと類題を1冊にした教材（各4,980円）。収録内容と見本を商品ページで確認できる。

情報系の教材を見る

動的計画法が使える条件

定義

最適部分構造と部分問題の重なり

問題の最適解が、その部分問題の最適解を組み合わせて作れるとき、最適部分構造をもつという。再帰的に解くと同じ部分問題が繰り返し現れるとき、部分問題が重なるという。動的計画法は両方が成り立つ問題で、異なる部分問題の数 $\times$ 1つあたりの計算時間で解ける。

定義

メモ化とボトムアップ

再帰の形のまま、計算済みの部分問題の答えを表に記録して再利用する方法をメモ化（トップダウン）という。小さい部分問題から順に表を埋める方法をボトムアップという。どちらも計算量は同じで、ボトムアップは再帰の深さの制限を受けず、不要になった行を捨てて領域を減らせる。

素朴な再帰 $F(n) = F(n-1) + F(n-2)$ でフィボナッチ数を求めると、呼び出し回数は $2F(n+1) - 1$ 回になり、 $n = 10$ で177回、増え方は $\Theta(\varphi^n)$ である。部分問題は $F(0), \dots, F(n)$ の $n + 1$ 個しかないので、表に記録すれば $\Theta(n)$ 回の加算で済む。

動的計画法の答案は次の順に書く。

部分問題を定義する（表の添字が何を表すか）。
漸化式と初期値を書き、最適部分構造から正しさを述べる。
表を埋める順序を決める（右辺の部分問題を先に計算する順）。
計算量を「表の大きさ $\times$ 1マスの計算」で求め、必要なら表をたどって解を復元する。

代表的な動的計画法の漸化式

最長共通部分列（LCS）: $c[i][j] = \begin{cases} 0 & i = 0 \text{ または } j = 0 \\ c[i-1][j-1] + 1 & x_i = y_j \\ \max(c[i-1][j],\ c[i][j-1]) & x_i \neq y_j \end{cases}$
$c[i][j]$ は $x_1 \cdots x_i$ と $y_1 \cdots y_j$ の LCS の長さ。 $\Theta(mn)$ 。
0-1ナップサック: $V[i][c] = \begin{cases} V[i-1][c] & w_i > c \\ \max(V[i-1][c],\ V[i-1][c - w_i] + v_i) & w_i \le c \end{cases}$
$V[i][c]$ は品物 $1, \dots, i$ から重さの合計 $c$ 以下で選ぶときの価値の最大。 $V[0][c] = 0$ 。 $\Theta(nW)$ で、 $W$ の桁数に対しては指数時間（擬多項式時間）。
編集距離: $D[i][j] = \min\left(D[i-1][j] + 1,\ D[i][j-1] + 1,\ D[i-1][j-1] + [x_i \neq y_j]\right)$
$D[i][0] = i$ 、 $D[0][j] = j$ 。挿入・削除・置換をそれぞれ1回と数える。 $[\,P\,]$ は $P$ が真なら1、偽なら0。
連鎖行列積: $m[i][j] = \min_{i \le k < j} \left( m[i][k] + m[k+1][j] + p_{i-1} p_k p_j \right), \quad m[i][i] = 0$
$A_i$ は $p_{i-1} \times p_i$ 行列。 $\Theta(n^3)$ 。 $10 \times 30$ 、 $30 \times 5$ 、 $5 \times 60$ の積は $(A_1A_2)A_3$ で $1500 + 3000 = 4500$ 回、 $A_1(A_2A_3)$ で $9000 + 18000 = 27000$ 回の乗算。

表を埋める計算例

計算例

最長共通部分列の表

$X = \mathrm{ABCB}$ 、 $Y = \mathrm{BDCAB}$ の最長共通部分列の長さと、その1つを求めよ。

解答

行を $X$ の文字（ $i = 0, \dots, 4$ ）、列を $Y$ の文字（ $j = 0, \dots, 5$ ）として漸化式で埋めると

\begin{array}{c|cccccc} & \varnothing & \mathrm{B} & \mathrm{D} & \mathrm{C} & \mathrm{A} & \mathrm{B} \\ \hline \varnothing & 0 & 0 & 0 & 0 & 0 & 0 \\ \mathrm{A} & 0 & 0 & 0 & 0 & 1 & 1 \\ \mathrm{B} & 0 & 1 & 1 & 1 & 1 & 2 \\ \mathrm{C} & 0 & 1 & 1 & 2 & 2 & 2 \\ \mathrm{B} & 0 & 1 & 1 & 2 & 2 & 3 \end{array}

LCS の長さは $c[4][5] = 3$ 。右下から、文字が一致するマスでは左上へ、一致しなければ値の等しい上か左へたどると、一致した文字 $\mathrm{B}, \mathrm{C}, \mathrm{B}$ を逆順に拾い、LCS の1つ $\mathrm{BCB}$ を得る。

検算

$\mathrm{BCB}$ は $X$ の1・3・4文字目、 $Y$ の1・3・5文字目で、両方の部分列である。 $X$ の長さ4の部分列は $X$ 自身だけで、 $\mathrm{ABCB}$ は $Y$ の部分列ではないから長さ4はない。

計算例

0-1ナップサックの表

重さ $(2, 3, 4, 5)$ 、価値 $(3, 4, 5, 6)$ の4品物から、重さの合計5以下で価値を最大にせよ。

解答

$V[i][c]$ （ $c = 0, \dots, 5$ ）を行ごとに埋める。

\begin{array}{c|cccccc} i \backslash c & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 3 & 3 & 3 & 3 \\ 2 & 0 & 0 & 3 & 4 & 4 & 7 \\ 3 & 0 & 0 & 3 & 4 & 5 & 7 \\ 4 & 0 & 0 & 3 & 4 & 5 & 7 \end{array}

最大価値は $V[4][5] = 7$ 。 $V[2][5] = \max(V[1][5], V[1][2] + 4) = \max(3, 7) = 7$ で品物2を採り、残り容量2で $V[1][2] = 3$ から品物1を採る。選ぶのは品物1と2（重さ5、価値7）。

検算

$2^4 = 16$ 通りの選び方を全部調べても、重さ5以下での価値の最大は7。品物4だけ（重さ5）は価値6、品物3だけは5で、どちらも7に届かない。

貪欲法が最適になる条件と反例

定義

貪欲選択性

ある規則で選んだ1つの要素を含む最適解が必ず存在するとき、その規則は貪欲選択性をもつという。貪欲選択性と最適部分構造の両方が示せれば、選択を1つずつ確定する貪欲法が最適解を与える。示せない問題では、もっともらしい規則でも誤った答えを出すことがある。

定理・法則

区間スケジューリング（活動選択）

条件

区間 $[s_i, f_i)$ （ $s_i < f_i$ ）の集合から、互いに重ならない区間をできるだけ多く選ぶ。 $f_i = s_j$ の区間どうしは重ならないとみなす。

主張

終了時刻 $f_i$ の早い順に見て、それまでに選んだ区間と重ならなければ選ぶ貪欲法は、選ぶ区間の数を最大にする。整列を含めて $O(n \log n)$ 。

要点

最適解の最初の区間を、終了時刻が最も早い区間に置き換えても重なりは生じない（交換論法）。開始時刻の早い順や区間の短い順の規則は最適にならない場合がある。重みつきの区間スケジューリングでは貪欲法は使えず、動的計画法を使う。

ハフマン符号（情報源符号化と通信路符号化）も、確率の小さい2つを合わせる貪欲法が最適になる例である。ナップサック問題では、品物を分割してよい場合は価値/重さの大きい順に詰める貪欲法が最適だが、0-1の場合は最適とは限らない。

計算例

区間スケジューリング

区間 $[1,4), [3,5), [0,6), [5,7), [3,9), [5,9), [6,10), [8,11), [8,12), [2,14), [12,16)$ から、重ならない区間を最も多く選べ。

解答

終了時刻の順に見る。 $[1,4)$ を選ぶ。 $[3,5)$ は $3 < 4$ で重なるので選ばない。次に開始が4以上で終了の最も早い $[5,7)$ を選ぶ。続いて開始が7以上の $[8,11)$ 、開始が11以上の $[12,16)$ を選ぶ。選んだ区間は $[1,4), [5,7), [8,11), [12,16)$ の4個。

検算

$2^{11} = 2048$ 通りの部分集合を全部調べても、重ならない区間の個数の最大は4。

計算例

硬貨の枚数で貪欲法が失敗する例

額面 $\{1, 3, 4\}$ の硬貨で6を払うとき、枚数の最小を貪欲法と動的計画法で求めよ。

解答

貪欲法は大きい額面から使い、 $4 + 1 + 1$ の3枚になる。動的計画法では $N(0) = 0$ 、 $N(a) = \min_{c \le a} (N(a - c) + 1)$ として

N(1), \dots, N(6) = 1, 2, 1, 1, 2, 2

で、 $N(6) = N(3) + 1 = 2$ 、つまり $3 + 3$ の2枚が最小である。

検算

6を2枚で払う組は $3 + 3$ だけで、1枚の硬貨では払えない。日本の硬貨 $\{1, 5, 10, 50, 100, 500\}$ では貪欲法が最適になるが、それは額面の組の性質によるもので、任意の額面で成り立つわけではない。

答案でよくある誤り

1
表の添字の意味を書かずに漸化式だけ書く。「 $V[i][c]$ は品物 $1, \dots, i$ から容量 $c$ 以下で選んだときの価値の最大」のように、部分問題を言葉で定義してから漸化式を書く。
2
0-1ナップサックの $\Theta(nW)$ を多項式時間と書く。入力の大きさは $W$ の桁数 $\log W$ で測るので、 $W$ に比例する時間は擬多項式時間である。この問題の判定版はNP完全で、計算可能性とNP完全性の帰着と矛盾しない。
3
1次元配列に縮めた0-1ナップサックで、容量 $c$ を小さい順に更新する。同じ品物を何度も使うことになるので、 $c$ は大きい順に更新する（小さい順は個数制限なしのナップサックになる）。
4
貪欲法の正しさを例で確かめただけで結論する。交換論法などで貪欲選択性を示すか、硬貨 $\{1,3,4\}$ のような反例がないかを考える。
5
LCS と最長共通部分文字列（連続した部分）を混同する。部分列は飛び飛びでよく、部分文字列は連続でなければならないので、漸化式も異なる。

動的計画法と貪欲法が出た院試の過去問

院試hubが年度別解説の大問を分類した集計から、この単元の内容を扱う出題を挙げる。問題文は各大学の公式過去問で確かめ、解き方は各年度の解説ページで読める。