動的計画法

同義語:動的計画動的プログラミングダイナミックプログラミングdynamic programming

概要

動的計画法(dynamic programming)とは、問題を部分問題に分けて再帰式を立て、部分問題の答えを表に記録して再利用することで、同じ計算の繰り返しを除く計算の方法である。部分問題の依存に閉路がなく、結合の関数が単調で、再帰式の解がもとの問題の解に対応するとき、再帰式の解は最適値を与える。手間は表のマスの数と 1 マスの選択の数の積で、記録しない再帰が指数的になる問題でも多項式で済むことがある。最長共通部分列、編集距離、ナップサック問題、連鎖行列積、負の辺を許す最短の道などに使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 漸化式, 有向非巡回グラフ, 位相的整列, 数学的帰納法

動的計画法(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 つの部分問題に依存する。 左:F_5 を漸化式のとおりに再帰で計算するときの呼び出しの木。呼び出しは 15 回。右:同じ計算の依存関係。部分問題は 6 個で、F_2 以上の各部分問題は 2 つの部分問題に依存する。
動的計画法は「繰り返しのない再帰」である(Eri19 §3.4、p. 105)。仕事は 2 段に分かれる。部分問題を選んで正しい再帰式を立てることと、依存の順に表を埋めることである。難しいのは前の段で、再帰式が正しいためには条件が要る。この記事では、次を証明する。

  • 部分問題の依存に閉路がなく、結合の関数が単調なら、再帰式の解が最適値である(thm-dp-main)。
  • 表の計算の手間は依存の総量に比例し、記録しない再帰の手間は依存グラフの道の本数である(prop-dp-cost)。
  • 最長共通部分列の再帰式(prop-dp-lcs)と、負の辺を許す最短の道の Bellman–Ford の再帰式(thm-dp-bf)が正しいこと。
    動的計画法の枠組みは Bellman が 1950 年代半ばに定式化して広めた(Eri19 第 3 章、p. 101)。状態・行動・費用で書いた多段の決定の問題、とくに線形の系の制御と連続時間の問題は 動的計画法と最適制御 で扱う。この記事はアルゴリズムの設計の方法としての動的計画法を扱う。

定義と使える条件

再帰式が「部分問題の最適値から全体の最適値を作る」形をしているとき、その形を次のように書く。以下 $\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 つある。

  • 表の計算:子が親より先に来る順に $S$ を並べ、その順に $W$ を計算して表に書く。この順は依存グラフの 位相的整列 の逆順である(Eri19 §6.4、p. 235)。
  • メモ化(memoization):再帰のまま書き、計算した値を表に記録する。呼び出されたらまず表を見て、値があれば再帰しない(Eri19 §3.1、p. 100)。
  • 記録しない再帰:再帰式をそのまま再帰の手続きにする。
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$ の道を含め、同じ子が同じ選択の中や別の選択に重ねて現れるときは別の辺として数える。

  1. 順序から、$s$ を計算するときに子の値は表にある。各 $s$ の計算は、各選択について $k_c$ 回の読み取りと $h_c$ の計算 1 回で、最後に表への書き込みが 1 回ある。
  2. 各 $s$ の本体は、最初に呼ばれたときに 1 回だけ実行される。呼び出しは、最初の 1 回を除いて、実行された本体の中で行われる。本体の中の呼び出しは $\sum_{c\in C(s)}k_c$ 回である。
  3. 呼び出しは $s$ 自身の 1 回と、各子からの呼び出しからなるので、$N(s)=1+\sum_{c\in C(s)}\sum_{i=1}^{k_c}N(t_i)$ である。$s$ から出る道は、長さ $0$ の道か、最初の辺で子へ進む道なので、本数は同じ式を満たす。高さについての帰納法で両者は等しい。$\square$
Fibonacci 数の呼び出しの回数

$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 に含める)。

  1. $p_r< i$:これは $X_{i-1}$ と $Y_j$ の共通部分列である。
  2. $q_r< j$:これは $X_i$ と $Y_{j-1}$ の共通部分列である。
  3. $(p_r,q_r)=(i,j)$:このとき $x_i=y_j$ で、最後の対を除いた列は $X_{i-1}$ と $Y_{j-1}$ の共通部分列である。
    逆に、各場合の短い語の共通部分列は、$X_i$ と $Y_j$ の共通部分列を与える(3 では対 $(i,j)$ を足す)。よって選択が「$x_i$ を使わない」「$y_j$ を使わない」「($x_i=y_j$ のとき)対にする」の分解は、最大化の def-dp-system で、結合の関数 $x$、$x$、$x+1$ は単調であり、依存は $i+j$ が減る向きなので閉路がない。分解の解からは対の列が得られ、どの対の列もこうして得られ、値は列の長さである。thm-dp-main により、
    $$ L(i,j)=\max\{L(i-1,j),\ L(i,j-1),\ L(i-1,j-1)+1\} $$
    である。ただし最後の項は $x_i=y_j$ のときだけ現れる。$x_i\ne y_j$ の場合は主張の式である。
    $x_i=y_j$ のとき、最初の 2 項が最後の項を超えないことを示す。$X_{i-1}$ と $Y_j$ の共通部分列から $q=j$ の対(あれば 1 つ)を除くと、$X_{i-1}$ と $Y_{j-1}$ の共通部分列になるので、$L(i-1,j)\le L(i-1,j-1)+1$ である。$L(i,j-1)$ も同様である。$\square$

負の辺を許す最短の道

$G=(V,E)$ を有限の有向グラフ、$n:=\lvert V\rvert$、$w\colon E\to\mathbb{R}$ を辺の重み、$s\in V$ を始点とする。辺の重みの和が負である閉じた歩道を 負の閉路 という。$d_k(v)$ を、$s$ から $v$ への辺が $k$ 本以下の歩道の重みの和の最小値とする(なければ $+\infty$)。辺の本数を添字に入れるのが要点で、$k$ が減るので依存に閉路ができない。

Bellman–Ford の再帰式
  1. $d_0(s)=0$、$v\ne s$ で $d_0(v)=+\infty$ であり、$k\ge1$ で
    $$ d_k(v)=\min\Bigl\{d_{k-1}(v),\ \min_{u\to v}\bigl(d_{k-1}(u)+w(u,v)\bigr)\Bigr\} $$
    が成り立つ。
  2. $s$ から到達できる負の閉路がなければ、$d_{n-1}(v)$ は $s$ から $v$ へのすべての歩道の重みの和の最小値であり、すべての $k\ge n-1$ で $d_k=d_{n-1}$ である。
  3. $s$ から到達できる負の閉路があれば、ある $v$ で $d_n(v)< d_{n-1}(v)$ である。
  1. 部分問題を $(k,v)$ とする。$k=0$ の選択は定数である。$k\ge1$ の選択は「とどまる」(子 $(k-1,v)$、結合の関数 $x$)と、辺 $u\to v$ ごとの「最後にこの辺を通る」(子 $(k-1,u)$、結合の関数 $x+w(u,v)$)である。どれも単調で、$k$ が減るので閉路はない。分解の解をたどって「とどまる」を除くと、辺が $k$ 本以下の歩道が得られ、値は重みの和である。逆にそのような歩道はすべてこの形で得られる。thm-dp-main より再帰式を得る。
  2. 同じ頂点を 2 度通る歩道は、閉じた部分を含む。始点は $s$ なのでこの閉じた部分は $s$ から到達でき、仮定より重みの和は $0$ 以上である。閉じた部分を除いても歩道は同じ端点をもち、重みの和は増えず、辺の本数は減る。これを繰り返すと、同じ頂点を通らない、辺が $n-1$ 本以下の歩道になる。よって最小値は $d_{n-1}$ で達成され、辺の本数の上限を増やしても変わらない。
  3. すべての $v$ で $d_n(v)=d_{n-1}(v)$ と仮定する。$s$ から到達できる負の閉路 $v_0\to v_1\to\dots\to v_l=v_0$ をとる。各 $v_i$ は $s$ から到達でき、同じ頂点を通らない歩道で $n-1$ 本以下の辺でたどれるので、$d_{n-1}(v_i)$ は有限である。(1) より
    $$ d_{n-1}(v_{i+1})=d_n(v_{i+1})\le d_{n-1}(v_i)+w(v_i,v_{i+1}) $$
    である。$i=0,\dots,l-1$ で足すと、左辺と右辺の $d_{n-1}$ の和は打ち消し合い、$0\le\sum_iw(v_i,v_{i+1})$ となる。これは負の閉路であることに反する。$\square$
  1. の式を $k=1,\dots,n-1$ の順に計算するのが Bellman–Ford 法の再帰式による形である(Eri19 §8.7、pp. 294–295)。配列 1 本を書き換えていく手順としての形は Bellman–Ford法 で扱う。(3) により、もう 1 回計算して値が変われば負の閉路が検出できる。辺の重みが $0$ 以上なら Dijkstra法 の方が速い。

計算の手順

  1. 部分問題を決める:「残りを解くのに、ここまでの選択のうち何を覚えていれば足りるか」と問う。答えが部分問題の添字である。
  2. 再帰式を立てる:解の最後の決定(または最初の決定)で場合分けする。条件 (iii) を確かめ、基底の場合(空の語、上限 $0$ など)を書く。
  3. 依存を確かめる:再帰式の右辺の添字が、左辺より小さい何かになっていることを確かめる(条件 (i))。結合の関数の単調性を確かめる(条件 (ii))。thm-dp-main により、ここまでで再帰式の正しさが示せる。
  4. 順序を決める:子が親より先に来る順を決める。表の型ごとの順は下の表のとおりである。
  5. 表を埋める:基底の場合から順に再帰式を計算する。
  6. 解を復元する:表の値と再帰式から、最小を与えた選択を逆にたどる。thm-dp-main の (3) である。
  7. 手間を見積もる:(表のマスの数)$\times$(1 マスの選択の数)である(prop-dp-cost)。
    手順の 1・3・4・7 に対応する段取りは Eri19 §3.4、pp. 106–107 にも書かれている。
    部分問題の型添字埋める順例
    列の前の部分$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$ の増える順巡回セールスマン問題 の定理「部分集合についての動的計画法」
    表の計算メモ化
    :--:--:--
    順序自分で決める再帰が自動で決める
    計算する部分問題すべて到達できるものだけ
    向く場面表が密で順序が簡単なとき使われる部分問題が少ないとき
    大きい値 $W$ に対して使われるマスが少ない問題では、メモ化の方が速いことがある。記録の表そのものが手間になるので、動的計画法がいつも再帰より速いわけではない(Eri19 §3.8、p. 117)。

例題

MATRIX と MAXIMA の最長共通部分列

使う公式:prop-dp-lcs。
答え:長さは $3$ で、最長の共通部分列は MAX と MAI の 2 つである。

表を開く

行が MATRIX、列が MAXIMA である。各マスは $L(i,j)$ で、右下が答えである。

MAXIMA
0000000
M0111111
A0122222
T0122222
R0122222
I0122333
X0123333

右下から、文字が一致して値が 1 減る斜めの移動をたどると解が復元できる。X の行の X の列の斜めの移動をたどると MAX、I の行の I の列をたどると MAI が得られる。

GAUSS と GALOIS の編集距離

使う公式:公式の表の編集距離の行。
答え:$3$ である。U を L に、最初の S を O に置き換え、I を挿入すればよい。

表を開く

行が GAUSS、列が GALOIS である。

GALOIS
0123456
G1012345
A2101234
U3211234
S4322233
S5433333

0-1 ナップサック

整数計画法 の例「荷物を選ぶ 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$01234567
000000000
100161616161616
200161919353535
300161923353942
400161923353944

$K(4,7)=\max\{K(3,7),\ K(3,2)+28\}=\max\{42,\ 44\}=44$ なので品物 4 を選び、残りは $K(3,2)=16$ で、これは品物 1 である。

4 つの行列の積

$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$1234
1010002500900
203000500
30300
40

$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)$
00$+\infty$$+\infty$$+\infty$
1042$+\infty$
20$-1$26
30$-1$21
40$-1$21

$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 の閉路

補足

  • 分割統治との違い:分割統治も部分問題に分けるが、部分問題が重ならないので記録しても得がない。動的計画法が効くのは、異なる部分問題の数が再帰の呼び出しの数よりずっと少ないときである。
  • 道の問題としての見方:どの選択も子が 1 つで、結合の関数が定数を足すだけなら、$\min$ の再帰式は依存グラフの上の最短の道の問題である。重み付きグラフの最短経路 で扱う距離の式と同じ形になる。子が 2 つ以上あると、解は道ではなく木になる。
  • 多段の決定の問題:状態と行動で書ける問題、確率的な遷移のある問題、無限期間の問題は 動的計画法と最適制御 で扱う。
  • 計算の難しさ:巡回セールスマン問題 のように、部分問題が指数個になる問題もある。動的計画法は全列挙より速くても多項式時間とは限らない。ナップサック問題 は、価値と重さを等しくすると部分和の問題を含み、部分和の問題は NP 困難である(Eri19 §3.8、p. 117)。それでも、値を丸めて動的計画法を使うと、任意の精度の近似解が多項式時間で求まる(WS11 §3.1、定理 3.5、p. 68)。
  • 組合せ最適化の中で:線形計画の緩和に基づく方法との比較は 組合せ最適化 と 整数計画法 にある。

関連項目

参考文献

[1]
Jeff Erickson, Algorithms, Independently published, 2019, 第 3 章(§3.1 メモ化 p. 100、動的計画法の由来 p. 101、§3.4 pp. 105–107、§3.7 pp. 111–112、§3.8 pp. 116–117)、§6.4(pp. 234–236)、§8.7(pp. 289–295)
[2]
David P. Williamson, David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, 第 3 章(擬多項式時間 p. 65、§3.1 ナップサック問題 pp. 65–68、定理 3.5 p. 68)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する