動的計画法(dynamic programming)とは、問題を部分問題に分けて再帰式を立て、部分問題の答えを表に記録して再利用することで、同じ計算の繰り返しを除く計算の方法である。部分問題の依存に閉路がなく、結合の関数が単調で、再帰式の解がもとの問題の解に対応するとき、再帰式の解は最適値を与える。手間は表のマスの数と 1 マスの選択の数の積で、記録しない再帰が指数的になる問題でも多項式で済むことがある。最長共通部分列、編集距離、ナップサック問題、連鎖行列積、負の辺を許す最短の道などに使う。
動的計画法(dynamic programming)は、問題を小さい部分問題に分け、部分問題の答えを表に記録して再利用することで、同じ計算の繰り返しを除く計算の方法である。
たとえば Fibonacci数 $F_n$ を、$F_0=0$、$F_1=1$、$F_n=F_{n-1}+F_{n-2}$ の 漸化式 のとおりに再帰で計算すると、$F_{30}$ を求めるのに関数の呼び出しが $2{,}692{,}537$ 回起こる(ex-dp-fib)。しかし現れる値は $F_0,\dots,F_{30}$ の $31$ 個しかない。同じ値を何度も計算しているのである。値を $F_0$ から順に表に書いていけば、足し算は $29$ 回で済む。
左:F_5 を漸化式のとおりに再帰で計算するときの呼び出しの木。呼び出しは 15 回。右:同じ計算の依存関係。部分問題は 6 個で、F_2 以上の各部分問題は 2 つの部分問題に依存する。
動的計画法は「繰り返しのない再帰」である(Eri19 §3.4、p. 105)。仕事は 2 段に分かれる。部分問題を選んで正しい再帰式を立てることと、依存の順に表を埋めることである。難しいのは前の段で、再帰式が正しいためには条件が要る。この記事では、次を証明する。
再帰式が「部分問題の最適値から全体の最適値を作る」形をしているとき、その形を次のように書く。以下 $\overline{\mathbb{R}}:=\mathbb{R}\cup\{+\infty\}$ とする。$+\infty$ は解がないことを表す。
再帰的分解(recursive decomposition)は、次のものからなる。
(a) 有限集合 $S$。その元を 部分問題 という。
(b) 各 $s\in S$ について、空でない有限集合 $C(s)$。その元を $s$ の 選択 という。
(c) 各選択 $c$ について、部分問題の列 $(t_1,\dots,t_k)$($k\ge0$ は $c$ による)と、結合の関数 $h_c\colon\overline{\mathbb{R}}^k\to\overline{\mathbb{R}}$。$k=0$ のとき $h_c$ は定数である。
$t$ が $s$ のある選択の列に現れるとき有向辺 $s\to t$ を引いたグラフを 依存グラフ という。依存グラフに閉路がないとき、$s$ の 解 を、選択 $c\in C(s)$ と各 $t_i$ の解 $\sigma_i$ の組 $\sigma=(c;\sigma_1,\dots,\sigma_k)$ として帰納的に定め、その 値 を
$$
\operatorname{val}(\sigma):=h_c\bigl(\operatorname{val}(\sigma_1),\dots,\operatorname{val}(\sigma_k)\bigr)
$$
と定める。$s$ の解の全体は有限集合なので、最小値 $\operatorname{opt}(s)\in\overline{\mathbb{R}}$ が定まる。これを $s$ の 最適値、最小を与える解を 最適解 という。
最大化の問題は、値の符号を変えて最小化の問題とみる(値の範囲は $\mathbb{R}\cup\{-\infty\}$ になる)。結合の関数の単調性は符号を変えても保たれるので、以下の定理は $\min$ を $\max$ に替えてそのまま使える。
動的計画法が使えるのは、次の条件が成り立つときである。
(i) 依存に閉路がない:部分問題の依存グラフが 有向非巡回グラフ である。
(ii) 結合が単調:各 $h_c$ は各変数について単調非減少である。すなわち部分問題の答えをよくすれば、全体の答えは悪くならない。
(iii) もとの問題と対応する:もとの問題の実行可能解のそれぞれに、同じ値をもつ分解の解があり、分解の解のそれぞれに、同じ値をもつ実行可能解がある。
(iv) 部分問題が少ない:部分問題の数と 1 つあたりの選択の数が、扱える大きさである。
(i)(ii)(iii) は答えが正しいための条件で、(iv) は速さのための条件である。(ii)(iii) を合わせた性質は 最適部分構造(optimal substructure)とよばれる(Eri19 §3.7、p. 112)。全体の最適解が部分問題の最適解から組み立てられる、という性質である。どの条件も外せないことは ex-dp-counterexamples で確かめる。
どの行も def-dp-system の形である。$\delta_{ij}$ は $x_i=y_j$ なら $0$、そうでなければ $1$ とする。
| 問題 | 部分問題 | 再帰式 | 手間 | 根拠 |
|---|---|---|---|---|
| 最長共通部分列 | 語の前の部分の組 $(i,j)$ | $x_i=y_j$ なら $L(i,j)=L(i-1,j-1)+1$、それ以外は $\max\{L(i-1,j),L(i,j-1)\}$ | $O(mn)$ | prop-dp-lcs |
| 編集距離 | 語の前の部分の組 $(i,j)$ | $D(i,j)=\min\{D(i-1,j)+1,\ D(i,j-1)+1,\ D(i-1,j-1)+\delta_{ij}\}$ | $O(mn)$ | 下の導出、Eri19 §3.7 |
| 0-1 ナップサック | 品物の個数と上限 $(i,c)$ | $w_i\le c$ なら $K(i,c)=\max\{K(i-1,c),\ K(i-1,c-w_i)+v_i\}$、それ以外は $K(i-1,c)$ | $O(nW)$ | 下の導出 |
| 連鎖行列積 | 区間 $(i,j)$ | $m(i,j)=\min_{i\le k< j}\{m(i,k)+m(k+1,j)+d_{i-1}d_kd_j\}$ | $O(n^3)$ | 下の導出 |
| 有向非巡回グラフの最長の道 | 頂点 $v$ | $\ell(v)=\max_{v\to u}\{w(v,u)+\ell(u)\}$ | $O(\lvert V\rvert+\lvert E\rvert)$ | 下の導出、Eri19 §6.4、pp. 235–236 |
| 単一始点の距離(負の辺も可) | 辺数の上限と頂点 $(k,v)$ | $d_k(v)=\min\{d_{k-1}(v),\ \min_{u\to v}(d_{k-1}(u)+w(u,v))\}$ | $O(\lvert V\rvert(\lvert V\rvert+\lvert E\rvert))$ | thm-dp-bf |
| 巡回セールスマン | 通った頂点の集合と最後の頂点 | 通った頂点の集合を 1 つ減らす式 | $O(n^22^n)$ | 巡回セールスマン問題 の定理「部分集合についての動的計画法」 |
編集距離:語 $X$ を、1 文字の削除・挿入・置換の列で語 $Y$ に変える最小の回数を編集距離という。$X,Y$ の最初の $i$ 文字・$j$ 文字についての値を $D(i,j)$ とする($D(i,0)=i$、$D(0,j)=j$)。2 つの語を縦に並べた対応の表で最後の列を見ると、$x_i$ の削除、$y_j$ の挿入、$x_i$ と $y_j$ の対応(文字が違えば置換)のどれかである。最後の列を除いた残りは、短い語どうしの対応の表である。これが 3 つの選択で、結合の関数は $x+1$、$x+1$、$x+\delta_{ij}$ で単調である。
0-1 ナップサック:品物 $1,\dots,n$ の重さ $w_i$ を正の整数、価値を $v_i\ge0$、上限 $W$ を整数とする。品物 $1,\dots,i$ から重さの和が $c$ 以下になるように選ぶときの価値の和の最大値を $K(i,c)$ とする($K(0,c)=0$)。選び方は品物 $i$ を含まないか、含むかのどちらかで、含むなら残りは上限 $c-w_i$ の $1,\dots,i-1$ からの選び方である。結合の関数は $x$ と $x+v_i$ である。
連鎖行列積:行列 $A_i$ の型を $d_{i-1}\times d_i$ とする。$p\times q$ 行列と $q\times r$ 行列の積の掛け算の回数を $pqr$ とし、積 $A_i\cdots A_j$ の計算の最小の回数を $m(i,j)$ とする($m(i,i)=0$)。かっこの付け方の最後の積が $(A_i\cdots A_k)(A_{k+1}\cdots A_j)$ であるとして $k$ で場合分けする。子は 2 つで、結合の関数 $x+y+d_{i-1}d_kd_j$ は両方の変数について単調である。かっこの付け方の総数は Catalan 数 $C_{n-1}$ である。
有向非巡回グラフの最長の道:終点 $g$ への最長の道の長さを $\ell(v)$ とする($\ell(g)=0$。$g$ 以外で出る辺がなければ $-\infty$)。道の最初の辺で場合分けする。依存グラフはもとのグラフそのものである。
def-dp-system の分解で、依存グラフに閉路がなく、すべての $h_c$ が各変数について単調非減少であるとする。このとき次が成り立つ。
(1) 再帰式
$$
W(s)=\min_{c\in C(s)}h_c\bigl(W(t_1),\dots,W(t_k)\bigr)\qquad(s\in S)
$$
を満たす関数 $W\colon S\to\overline{\mathbb{R}}$ はただ 1 つある($(t_1,\dots,t_k)$ は選択 $c$ の列)。
(2) すべての $s$ で $\operatorname{opt}(s)=W(s)$ である。
(3) 各 $s$ で右辺の最小を与える選択 $c^*(s)$ をとる。$s$ から始めて $c^*$ に従って子へ下りて作った解は、$s$ の最適解である。
$s$ から出る有向の道の長さの最大値を $s$ の高さ $\operatorname{ht}(s)$ とする。$S$ は有限で閉路がないので高さは有限であり、$s\to t$ なら $\operatorname{ht}(t)< \operatorname{ht}(s)$ である。
(1) 再帰式の右辺は、高さが $s$ より小さい部分問題の値だけで決まる。高さの小さい順に値を定めれば $W$ が作れ、再帰式を満たす関数はどれもこの値に一致する。
(2)(3) 高さについての帰納法で、$\operatorname{opt}(s)=W(s)$ と、(3) で作った解 $\sigma^*(s)$ の値が $W(s)$ であることを示す。高さが $s$ より小さい部分問題では成り立つとする(高さ $0$ の $s$ では、そのような部分問題を使わない)。
$s$ の任意の解 $\sigma=(c;\sigma_1,\dots,\sigma_k)$ をとる。帰納法の仮定から $\operatorname{val}(\sigma_i)\ge\operatorname{opt}(t_i)=W(t_i)$ である。$h_c$ の単調性と $W$ の定義から
$$
\operatorname{val}(\sigma)=h_c\bigl(\operatorname{val}(\sigma_1),\dots,\operatorname{val}(\sigma_k)\bigr)\ge h_c\bigl(W(t_1),\dots,W(t_k)\bigr)\ge W(s)
$$
となる。よって $\operatorname{opt}(s)\ge W(s)$ である。
逆に $c=c^*(s)$ の列を $(t_1,\dots,t_k)$ とする。帰納法の仮定から $\operatorname{val}(\sigma^*(t_i))=W(t_i)$ なので、$\sigma^*(s)=(c;\sigma^*(t_1),\dots,\sigma^*(t_k))$ の値は $h_c(W(t_1),\dots,W(t_k))=W(s)$ である。よって $\operatorname{opt}(s)\le W(s)$ で、$\sigma^*(s)$ は最適解である。$\square$
単調性は、上の式の最初の不等号だけに使われている。部分問題の解を最適解に取り替えても全体が悪くならないこと、これが最適部分構造の中身である。
この定理は、選択の子が 2 つ以上ある場合(ex-dp-chain の連鎖行列積)も含む。状態が一本の列をたどり費用が段ごとの足し算である問題に限れば、動的計画法と最適制御 の定理「Bellman 方程式と最適性原理」が同じ主張を与え、その証明は費用の差の分解まで示している。
再帰式を計算する方法は 3 つある。
閉路のない分解で、選択 $c$ の列の長さを $k_c$ とし、$M:=\sum_{s\in S}\sum_{c\in C(s)}(1+k_c)$ とおく。
(1) 表の計算は、$h_c$ をそれぞれ 1 回ずつ計算し、$M$ 回の表の読み取りと関数の計算と、$\lvert S\rvert$ 回の表の書き込みで終わる。
(2) 部分問題 $s_0$ から始めるメモ化では、$s_0$ から到達できる部分問題だけが計算され、再帰の呼び出しは $1+\sum_{s\in S}\sum_{c\in C(s)}k_c$ 回以下である。
(3) 記録しない再帰の、$s$ から始めた呼び出しの回数 $N(s)$ は、$s$ から出る有向の道の本数である。ただし長さ $0$ の道を含め、同じ子が同じ選択の中や別の選択に重ねて現れるときは別の辺として数える。
$S=\{0,\dots,n\}$、$0,1$ の選択は定数、$m\ge2$ の選択は 1 つで列 $(m-1,m-2)$、結合の関数を $x+y$ とすると、$W(m)=F_m$ である。prop-dp-cost の (3) の回数は $N_0=N_1=1$、$N_m=1+N_{m-1}+N_{m-2}$ を満たす。$N_m=2F_{m+1}-1$ である。実際 $m=0,1$ で成り立ち、$1+(2F_m-1)+(2F_{m-1}-1)=2F_{m+1}-1$ である。$N_{30}=2F_{31}-1=2{,}692{,}537$ で、部分問題は $31$ 個である。
語 $X=x_1\cdots x_m$ の添字 $p_1< \dots< p_r$ を選んで $x_{p_1}\cdots x_{p_r}$ を作ったものを $X$ の 部分列 という。語 $X$ と $Y=y_1\cdots y_n$ の両方の部分列である語を 共通部分列 という。$X_i:=x_1\cdots x_i$、$Y_j:=y_1\cdots y_j$ とし、$X_i$ と $Y_j$ の共通部分列の長さの最大値を $L(i,j)$ とする。
$L(i,0)=L(0,j)=0$ であり、$i,j\ge1$ について
$$
L(i,j)=\begin{cases}L(i-1,j-1)+1&(x_i=y_j)\\\max\{L(i-1,j),\ L(i,j-1)\}&(x_i\ne y_j)\end{cases}
$$
が成り立つ。
$X_i$ と $Y_j$ の長さ $r$ の共通部分列は、添字の対の列 $(p_1,q_1),\dots,(p_r,q_r)$ で、$p,q$ がともに狭義に増え、$x_{p_l}=y_{q_l}$ となるものである。$i,j\ge1$ とする。最後の対について、次のどれかが成り立つ($r=0$ は 1 に含める)。
$G=(V,E)$ を有限の有向グラフ、$n:=\lvert V\rvert$、$w\colon E\to\mathbb{R}$ を辺の重み、$s\in V$ を始点とする。辺の重みの和が負である閉じた歩道を 負の閉路 という。$d_k(v)$ を、$s$ から $v$ への辺が $k$ 本以下の歩道の重みの和の最小値とする(なければ $+\infty$)。辺の本数を添字に入れるのが要点で、$k$ が減るので依存に閉路ができない。
| 部分問題の型 | 添字 | 埋める順 | 例 |
|---|---|---|---|
| 列の前の部分 | $i$ または $(i,j)$ | $i$ の増える順、同じ $i$ で $j$ の増える順 | ex-dp-lcs、ex-dp-edit |
| 列の前の部分と資源の量 | $(i,c)$ | $i$ の増える順 | ex-dp-knapsack |
| 区間 | $(i,j)$ | 区間の長さ $j-i$ の増える順 | ex-dp-chain |
| グラフと辺の本数 | $(k,v)$ | $k$ の増える順 | ex-dp-bf |
| 部分集合 | $(A,v)$ | $\lvert A\rvert$ の増える順 | 巡回セールスマン問題 の定理「部分集合についての動的計画法」 |
| 表の計算 | メモ化 | ||
| :-- | :-- | :-- | |
| 順序 | 自分で決める | 再帰が自動で決める | |
| 計算する部分問題 | すべて | 到達できるものだけ | |
| 向く場面 | 表が密で順序が簡単なとき | 使われる部分問題が少ないとき |
使う公式:prop-dp-lcs。
答え:長さは $3$ で、最長の共通部分列は MAX と MAI の 2 つである。
行が MATRIX、列が MAXIMA である。各マスは $L(i,j)$ で、右下が答えである。
| M | A | X | I | M | A | ||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| M | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| A | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| T | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| R | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| I | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| X | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
右下から、文字が一致して値が 1 減る斜めの移動をたどると解が復元できる。X の行の X の列の斜めの移動をたどると MAX、I の行の I の列をたどると MAI が得られる。
使う公式:公式の表の編集距離の行。
答え:$3$ である。U を L に、最初の S を O に置き換え、I を挿入すればよい。
行が GAUSS、列が GALOIS である。
| G | A | L | O | I | S | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| G | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| A | 2 | 1 | 0 | 1 | 2 | 3 | 4 |
| U | 3 | 2 | 1 | 1 | 2 | 3 | 4 |
| S | 4 | 3 | 2 | 2 | 2 | 3 | 3 |
| S | 5 | 4 | 3 | 3 | 3 | 3 | 3 |
整数計画法 の例「荷物を選ぶ 0-1 の問題」と同じく、価値が $16,19,23,28$、重さが $2,3,4,5$、上限が $W=7$ の品物を考える。
使う公式:公式の表の 0-1 ナップサックの行。
答え:最大の価値は $44$ で、品物 1 と品物 4 を選ぶ。
各行は品物 $1,\dots,i$ を使うときの $K(i,c)$ である。
| $i\backslash c$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 16 | 16 | 16 | 16 | 16 | 16 |
| 2 | 0 | 0 | 16 | 19 | 19 | 35 | 35 | 35 |
| 3 | 0 | 0 | 16 | 19 | 23 | 35 | 39 | 42 |
| 4 | 0 | 0 | 16 | 19 | 23 | 35 | 39 | 44 |
$K(4,7)=\max\{K(3,7),\ K(3,2)+28\}=\max\{42,\ 44\}=44$ なので品物 4 を選び、残りは $K(3,2)=16$ で、これは品物 1 である。
$A_1,A_2,A_3,A_4$ の型を $10\times20$、$20\times5$、$5\times30$、$30\times2$ とする($d=(10,20,5,30,2)$)。
使う公式:公式の表の連鎖行列積の行。
答え:最小の掛け算の回数は $900$ で、かっこの付け方は $A_1(A_2(A_3A_4))$ である。5 通りのかっこの付け方のうち、最大は $9{,}600$ 回である。
区間の長さの増える順に埋める。各マスは $m(i,j)$ である。
| $i\backslash j$ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 1000 | 2500 | 900 |
| 2 | 0 | 3000 | 500 | |
| 3 | 0 | 300 | ||
| 4 | 0 |
$m(1,4)=\min\{m(2,4)+10\cdot20\cdot2,\ m(1,2)+m(3,4)+10\cdot5\cdot2,\ m(1,3)+10\cdot30\cdot2\}=\min\{900,\ 1400,\ 3100\}=900$ である。
頂点 $s,a,b,c$ と辺 $s\to a:4$、$s\to b:2$、$b\to a:-3$、$a\to c:2$、$b\to c:5$ を考える。
使う公式:thm-dp-bf。
答え:距離は $a$ が $-1$、$b$ が $2$、$c$ が $1$ である。$c$ への最短の道は $s\to b\to a\to c$ である。
| $k$ | $d_k(s)$ | $d_k(a)$ | $d_k(b)$ | $d_k(c)$ |
|---|---|---|---|---|
| 0 | 0 | $+\infty$ | $+\infty$ | $+\infty$ |
| 1 | 0 | 4 | 2 | $+\infty$ |
| 2 | 0 | $-1$ | 2 | 6 |
| 3 | 0 | $-1$ | 2 | 1 |
| 4 | 0 | $-1$ | 2 | 1 |
$n=4$ で $d_4=d_3$ なので、thm-dp-bf の (3) により負の閉路はない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| (i) 依存に閉路がない | 辺 $s\to u:1$、$u\to v:0$、$v\to u:0$ の距離の式 | 再帰式の解が一意でない |
| (ii) 結合が単調 | 2 段で数を選ぶ積の最大化 | 前半の最適から全体の最適が作れない |
| (iii) もとの問題と対応する(値の対応) | 添字 $i$ を落としたナップサックの再帰式 | 再帰式の値が実行可能解の値でない |
| (iii) もとの問題と対応する(組み立て) | 最長の単純な道 | 部分問題の最適解をつないでも解にならない |
| (iv) 部分問題が少ない | 重さ $1,2,4,\dots,2^{n-1}$ のナップサック | 記録しても手間が減らない |
| thm-dp-bf の負の閉路がないこと | 辺 $s\to a:1$、$a\to b:1$、$b\to a:-3$ | $d_k$ が止まらず、距離が定まらない |
どの行も、その行の条件だけを満たしていない。
閉路:$d(s)=0$、$d(u)=\min\{1,d(v)\}$、$d(v)=d(u)$ は、$d(u)=d(v)=c$ が $c\le1$ のすべてで解になる。本当の距離は $c=1$ である。結合は単調だが、依存 $u\to v\to u$ が閉路である。添字 $k$ を入れる thm-dp-bf は、この閉路を切る方法である。
単調でない結合:第 1 段で $1$ か $-2$ を選び、第 2 段で $-3$ を掛け、積を最大にする。第 1 段の最適は $1$ だが、積は $-3$ である。$-2$ を選ぶと積は $6$ で、こちらが最適である。結合の関数 $x\mapsto-3x$ は減少する。最大と最小の両方を部分問題に持てば解ける。
値の対応:重さ $1$、価値 $1$ の品物が 1 個、$W=2$ とする。添字 $i$ を落として $K(c)=\max_{w_i\le c}\{K(c-w_i)+v_i\}$ とすると $K(2)=2$ だが、正しい値は $1$ である。この式は同じ品物を何度も使う問題の式である。ex-dp-knapsack の品物では $51$ となり、正しい $44$ より大きい。
組み立て:4 頂点 $q,r,s,t$ で、$q$ と $r$、$q$ と $s$、$r$ と $t$、$s$ と $t$ の間に両向きの辺があるとする。$q$ から $t$ への最長の単純な道の 1 つは $q\to r\to t$ である。しかし $q$ から $r$ への最長の単純な道は $q\to s\to t\to r$、$r$ から $t$ への最長の単純な道は $r\to q\to s\to t$ で、つなぐと同じ頂点を 2 度通る。部分問題どうしが頂点を取り合うので、独立に解けない。一般の有向グラフの最長の道は NP 困難である(Eri19 §6.4、p. 235)。閉路のないグラフでは、公式の表の行のとおり解ける。
部分問題の数:重さ $w_i=2^{i-1}$、上限 $W=2^n-1$ のとき、$(n,W)$ から再帰すると、$i$ を決めた段の $c$ はそれまでの選び方ごとにすべて異なる(2 進表示の一意性)。よって異なる部分問題は $2^{n+1}-1$ 個で、再帰の呼び出しの回数と同じである。答えは正しいが、手間は全列挙と変わらない。
負の閉路:$d_k(a)$ は $k=1,3,5$ で $1,-1,-3$ と減り続ける。閉路 $a\to b\to a$ を回るほど重みの和が小さくなるので、最小値がない。$n=3$ で $d_3(a)=-1< d_2(a)=1$ であり、thm-dp-bf の (3) のとおり検出できる。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 局所的に一番よい選択を続ける(貪欲法) | 選択をすべて試す再帰式を立てる | 額面 $1,3,4$ で金額 $6$ を作る硬貨の最小枚数は $2$ だが、大きい額面から取ると $3$ 枚になる |
| 再帰式が正しいので、そのまま再帰で書く | 表かメモ化で記録する | ex-dp-fib、prop-dp-cost の (3) |
| ナップサックの $O(nW)$ を多項式時間と言う | 擬多項式時間という。$W$ を 2 進で書いた入力の長さは $\log W$ 程度なので、入力の長さの多項式ではない | WS11 第 3 章、p. 65、Eri19 §3.8、p. 117 |
| ナップサックの表を 1 行にして $c$ の増える順に更新する | $c$ の減る順に更新する。増える順だと更新した値を同じ行で使い、同じ品物を重ねて入れる | ex-dp-counterexamples の値の対応 |
| 値の表だけ捨てて解を復元できなくなる | 復元が要るなら表全体か選択を残す | thm-dp-main の (3) |
| 辺の本数を添字に入れずに距離の式を解く | 閉路があるときは添字を足して閉路を切る | ex-dp-counterexamples の閉路 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する