§E16.18動的計画法

証明.主張 (1)を示す。$D$は有向非巡回グラフであるから、§D2.11 定理 2.3により$D$の位相順序が存在する。

主張 (2)を示す。位相順序$s_1,\dots,s_N$は$Q$のすべての状態をちょうど一度ずつ並べた列であるから、各$t\in Q$に対して$s_{\iota(t)}=t$を満たす添字$\iota(t)\in\{1,\dots,N\}$がただ一つ定まる。$s_i\notin Q_0$かつ$t\in N^{-}(s_i)$とすると$(t,s_i)\in A$である。$t=s_{\iota(t)}$かつ$s_i$は第$i$項であるから、位相順序の定義（$A$のすべての弧$(s_k,s_l)$について$k<l$）により$\iota(t)<i$である。よって$u_i$を定める式の右辺に現れる値はすべて添字が$i$より小さく、$i$の小さい順に定めれば既に定まっている。$i=1,\dots,N$の順に一つずつ定めれば、すべての$u_i$が定まる。

主張 (3)の一意性を示す。$V$と$V'$をともに$\Sigma$の解とする。述語$P(i)$を「$1\le i\le N$ならば$V(s_i)=V'(s_i)$である」と定め、$P$が全ての非負整数について成り立つことを累積帰納法（§D2.1 命題 1.2）で示す。$i$をとり、$i$より小さいすべての添字で$P$が成り立つと仮定する。$i=0$または$i>N$ならば$P(i)$は空虚に成り立つ。$1\le i\le N$とする。

$s_i\in Q_0$のときは、定義 1.2 条件 (a)により$V(s_i)=b(s_i)=V'(s_i)$である。

$s_i\notin Q_0$のときは、各$t\in N^{-}(s_i)$について主張 (2)により$\iota(t)<i$であるから、帰納法の仮定によって$V(s_{\iota(t)})=V'(s_{\iota(t)})$、すなわち$V(t)=V'(t)$である。したがって二つの族$(V(t))_{t\in N^{-}(s_i)}$と$(V'(t))_{t\in N^{-}(s_i)}$は$N^{-}(s_i)$上の写像として一致する。定義 1.2 条件 (b)により

である。よって$P(i)$が成り立ち、累積帰納法によりすべての$i$で$V(s_i)=V'(s_i)$である。位相順序はすべての状態を尽くすので$V=V'$である。

主張 (3)の存在を示す。主張 (2)により定まる$u_1,\dots,u_N$を用いて、写像$V:Q\to\R$を$V(s_i)=u_i$によって定める。位相順序は$Q$の各要素をちょうど一度ずつ並べるので、この定め方は矛盾なく$Q$全体で$V$を定める。定義から、各$t\in Q$に対し$V(t)=u_{\iota(t)}$である。

$V$が解の条件を満たすことを確かめる。$s_i\in Q_0$のとき、評価の定義により$V(s_i)=u_i=b(s_i)$であり、定義 1.2 条件 (a)が成り立つ。$s_i\notin Q_0$のとき、評価の定義により

であり、定義 1.2 条件 (b)が成り立つ。よって$V$は解である。

最後に、$u_i=V(s_i)$は$V$の定め方そのものであり、一意性により、この$V$が唯一の解である。▨

証明.定理 1.4 (3)により、$\Sigma$の解$V$はただ一つであり、$u_i=V(s_i)$かつ$u'_k=V(s'_k)$が成り立つ。$s_i=s'_k$ならば$u_i=V(s_i)=V(s'_k)=u'_k$である。▨

証明. 状態$s$の値を定めるのに要する基本操作の回数を$\theta(s)$と書く。$s\in Q_0$のときは$\deg^{-}(s)=0$であるから、仮定により$1+\deg^{-}(s)=1\le\theta(s)\le\kappa=\kappa\bigl(1+\deg^{-}(s)\bigr)$である。$s\notin Q_0$のときも仮定からそのまま同じ不等式が得られる。よってすべての$s\in Q$について

が成り立つ。

評価は各状態の値をちょうど一度ずつ定めるので$T=\sum_{s\in Q}\theta(s)$である。上の不等式を$s\in Q$について加え、§D2.11 命題 1.2による$\sum_{s\in Q}\deg^{-}(s)=\lvert A\rvert$を用いると

を得る。

使用セル数については、各状態の値を一つのセルへ保持し、状態は$\lvert Q\rvert$個であるから、値をすべて保持したままの評価の使用セル数は$\lvert Q\rvert$である。▨

証明.主張 (1)を示す。弧$(t,s)\in A$をとると層分解の定義により$\ell(t)=\ell(s)-1<\ell(s)$である。並べ方は層の番号が小さい状態を先に置くので、$t$は$s$より前に現れる。よってすべての弧が列の前から後ろへ向き、この列は位相順序である。

主張 (2)を示す。$s\in L_0$とし、$(t,s)\in A$を満たす$t$が存在すると仮定する。層分解の定義により$\ell(t)=\ell(s)-1=-1$となるが、$\ell$の値域は$\{0,1,\dots,L\}$であるから、これは起こらない。よって$\deg^{-}(s)=0$、すなわち$s\in Q_0$である。

主張 (3)を示す。まず、$r\ge1$と$s\in L_r$に対し$N^{-}(s)\subseteq L_{r-1}$である。実際$t\in N^{-}(s)$ならば$(t,s)\in A$であるから$\ell(t)=\ell(s)-1=r-1$である。したがって第$r$層の値を定めるのに必要な値は第$r-1$層の値だけであり、手続きは矛盾なく定まる。

次に、この手続きが与える族が$V$に一致することを$r$についての帰納法で示す。$r=0$のとき、主張 (2)により第$0$層のすべての状態は境界状態であるから、手続きは$b(s)$を与え、定義 1.2 条件 (a)により$V(s)=b(s)$である。$r\ge1$とし、第$r-1$層で一致していると仮定する。$s\in L_r$をとる。$s\in Q_0$ならば手続きは$b(s)$を与え、定義 1.2 条件 (a)により$V(s)=b(s)$である。$s\notin Q_0$ならば、$N^{-}(s)\subseteq L_{r-1}$と帰納法の仮定により、手続きが$g_s$へ与える引数の族は$(V(t))_{t\in N^{-}(s)}$に一致するので、手続きが与える値は$g_s\bigl((V(t))_{t\in N^{-}(s)}\bigr)=V(s)$である。よって第$r$層でも一致する。

使用セル数については、第$r$層を定めているあいだ、手続きが保持しているのは第$r-1$層の値と、それまでに定めた第$r$層の値だけである。その個数は$\lvert L_{r-1}\rvert+\lvert L_r\rvert$以下であり、$r$は$1$から$L$までを動くので、主張の上界を得る。▨

証明. 境界の場合。$i=0$のとき$\{1,\dots,0\}=\emptyset$であるから$\mathcal F(0,j)=\{\emptyset\}$であり、$\emptyset$に対する価値の総和は$0$である。よって$\mathrm{OPT}(0,j)=0$である。

$i\ge1$の場合。$\mathcal F(i,j)$を、第$i$番目の品物を含まないものと含むものへ分ける。すなわち

と置くと、$\mathcal F(i,j)=\mathcal F_{\mathrm{out}}\cup\mathcal F_{\mathrm{in}}$であり、この二つは交わらない。

第一に$\mathcal F_{\mathrm{out}}=\mathcal F(i-1,j)$である。実際、$T\subseteq\{1,\dots,i\}$かつ$i\notin T$は$T\subseteq\{1,\dots,i-1\}$と同値であり、重さの条件は両者で同じ式である。価値の総和も同じ式であるから

である。とくに$\mathcal F_{\mathrm{out}}$は空でない。

第二に$\mathcal F_{\mathrm{in}}$を調べる。$T\in\mathcal F_{\mathrm{in}}$ならば$w_i\le\sum_{k\in T}w_k\le j$であるから、$j<w_i$のとき$\mathcal F_{\mathrm{in}}=\emptyset$である。この場合は$\mathcal F(i,j)=\mathcal F_{\mathrm{out}}$となり、主張の第一の場合が従う。

$j\ge w_i$とする。写像$T'\mapsto T'\cup\{i\}$を考える。$T'\in\mathcal F(i-1,j-w_i)$ならば$T'\subseteq\{1,\dots,i-1\}$かつ$\sum_{k\in T'}w_k\le j-w_i$であるから、$T=T'\cup\{i\}$は$T\subseteq\{1,\dots,i\}$、$i\in T$かつ$\sum_{k\in T}w_k=\sum_{k\in T'}w_k+w_i\le j$を満たし、$T\in\mathcal F_{\mathrm{in}}$である。逆に$T\in\mathcal F_{\mathrm{in}}$に対して$T'=T\setminus\{i\}$と置くと、$T'\subseteq\{1,\dots,i-1\}$かつ$\sum_{k\in T'}w_k=\sum_{k\in T}w_k-w_i\le j-w_i$であるから$T'\in\mathcal F(i-1,j-w_i)$である。二つの対応は互いに逆であるから、$T'\mapsto T'\cup\{i\}$は$\mathcal F(i-1,j-w_i)$から$\mathcal F_{\mathrm{in}}$への全単射である。さらに$i\notin T'$であるから

である。よって

である。$\mathcal F(i-1,j-w_i)$は空でないので$\mathcal F_{\mathrm{in}}$も空でない。

最後に、有限集合$X$が二つの空でない部分$X_1$と$X_2$の交わらない合併であるとき、実数値関数$f$について

が成り立つ。実際、$X_1$と$X_2$は空でない有限集合であるから右辺の三つの最大値はいずれも存在する。$X_1\subseteq X$と$X_2\subseteq X$により$\max_{X}f\ge\max_{X_1}f$かつ$\max_{X}f\ge\max_{X_2}f$であるから、左辺は右辺以上である。逆に、$\max_{X}f=f(x)$を満たす$x\in X$をとると、$X=X_1\cup X_2$より$x\in X_1$または$x\in X_2$であり、前者ならば$f(x)\le\max_{X_1}f$、後者ならば$f(x)\le\max_{X_2}f$であるから、左辺は右辺以下である。よって等号が成り立つ。

これを$X=\mathcal F(i,j)$、$X_1=\mathcal F_{\mathrm{out}}$、$X_2=\mathcal F_{\mathrm{in}}$へ適用すると、$j\ge w_i$の場合の主張を得る。上で$\mathcal F_{\mathrm{out}}$と$\mathcal F_{\mathrm{in}}$がともに空でないことを確かめたのは、この適用のためである。▨

証明.主張 (1)を示す。まず$A\subseteq Q\times Q$であり、各弧の始点と終点は第一成分が異なるので相異なる。よって$D$は§D2.11 定義 1.1の意味での有向グラフである。$A$のどの弧$(t,s)$についても、$t$の第一成分に$1$を加えたものが$s$の第一成分である。有向閉路$u_0,u_1,\dots,u_k=u_0$（$k\ge1$）が存在すると仮定し、$u_l$の第一成分を$a_l$と書くと$a_l=a_0+l$であるから$a_k=a_0+k>a_0$となる。ところが$u_k=u_0$より$a_k=a_0$であり、矛盾する。よって$D$は有向非巡回グラフである。

$A$のすべての弧の終点は第一成分が$1$以上であるから、$(0,j)$の入次数は$0$である。逆に$1\le i\le n$のとき、弧$\bigl((i-1,j),(i,j)\bigr)$が$A$に属するので$(i,j)$の入次数は$1$以上である。よって$Q_0=\{(0,j)\}$である。

主張 (2)を示す。$1\le i\le n$とする。$j<w_i$のとき$N^{-}\bigl((i,j)\bigr)=\{(i-1,j)\}$であり、$j\ge w_i$のとき$w_i\ge1$より$j-w_i\ne j$であるから$N^{-}\bigl((i,j)\bigr)=\{(i-1,j),\ (i-1,j-w_i)\}$である。よって上で定めた$g_s$は$\R^{N^{-}(s)}$上の写像として矛盾なく定まる。命題 3.2では、写像$(i,j)\mapsto\mathrm{OPT}(i,j)$が定義 1.2の二条件を満たすことがそのまま述べられている。よって$\mathrm{OPT}$は$\Sigma$の解であり、定理 1.4 (3)により解は一つしかないので、$\mathrm{OPT}$が唯一の解である。

主張 (3)を示す。$A$のどの弧$(t,s)$についても$\ell(s)=\ell(t)+1$であることは 1 で確かめた。$\ell$の値域は$\{0,1,\dots,n\}$である。第$i$層は$\{(i,j):0\le j\le W\}$であるから、その要素数は$W+1$である。

主張 (4)を示す。$\lvert Q\rvert=(n+1)(W+1)$は直積の要素数である。$A$を定める二つの集合は交わらない。実際、第一の集合の弧は終点$(i,j)$に対する始点の第二成分が$j$であり、第二の集合の弧は$j-w_i$であって、$w_i\ge1$より両者は相異なるからである。第一の集合の要素数は$n(W+1)$である。第二の集合の要素数は$\sum_{i=1}^{n}\lvert\{j:\ w_i\le j\le W\}\rvert$であり、各項は$0$以上$W+1$以下であるから、この和は$0$以上$n(W+1)$以下である。よって$n(W+1)\le\lvert A\rvert\le2n(W+1)$である。▨

証明.主張 (1)を示す。命題 2.2により$\lvert Q\rvert+\lvert A\rvert\le T\le\kappa\bigl(\lvert Q\rvert+\lvert A\rvert\bigr)$である。命題 3.3 (4)により

であるから、主張の第一の不等式が従う。$n\ge1$かつ$W\ge1$のときは$nW\le(n+1)(W+1)\le2n\cdot2W=4nW$であるから$nW\le T\le12\kappa\,nW$である。

主張 (2)を示す。命題 2.2の後半と$\lvert Q\rvert=(n+1)(W+1)$による。

主張 (3)を示す。命題 3.3 (3)により$\ell(i,j)=i$は層分解であり、各層の要素数は$W+1$である。命題 2.4 (3)により、この手続きは各層の上で唯一の解$\mathrm{OPT}$に一致する族を与え、使用セル数は$\max_{1\le r\le n}\bigl(\lvert L_{r-1}\rvert+\lvert L_r\rvert\bigr)=2(W+1)$以下である。第$n$層は$\{(n,j):0\le j\le W\}$であるから、そこに$\mathrm{OPT}(n,W)$が含まれる。▨