Dynamic Programming

3.1 Shortest Paths

  考虑一个具有非负弧长$c_{ij}$的图$G=(V,A)$，找出从s到t的最短路径。

一个最直接的方法：

• 找出所有从s到t的路径
• 评估所有s-t路径的长度
• 找出最短的长度
  s−t路径的数量呈指数增长，对于大的图是不可行的。

  用$d(v)$表示从s到v的最短路径，那么

$$d(v)=\underset{i\in V^{-}(v)}{min}\{d(i)+c_{iv}\}$$

对于$i\ne s$，计算$d(v)$的复杂度为$O(m)$。

  假设$|V|=n$和$|A|=m$，对节点进行排序使得对于所有的$(i,j)\in A$都有$i\le j$。$D_k(j)=$从s到j的最短路径长度，最多经过$k$条弧，那么

$$D_k(j)=min\{D_{k-1}(j),\underset{i\in V^{-}(j)}{min}[D_{k-1}(i)+c_{ij}]\}$$

将$k$从1增大到$m-1$，即可得到最短路径。算法的复杂度为$O(mn)$。

例：找出从A到J的最短路径

3.2 Priciple of Optimality

Richard Bellman(1952)提出了最优性和动态规划的原理。
— Richard Bellman on the Birth of Dynamic Programming. Stuart Dreyfus. Operations Research, Vol. 50, No. 1, 48-51, 2002

Principle of optimality：在决策或选择的最优序列中，每个子序列也必须是最优的。

  最优原理适用于多阶段决策问题，有非常多的优化问题都满足这个原理，它适用于一类问题（而不是一个算法）。阶段可以指每个需要被计算值的节点，或者决定顺序的步骤。

3.3 0-1 Knapsack Problem

  考虑0-1背包问题

$$f^{\ast }=max\{{\mathbf{c}}^{\mathrm{\top }}\mathbf{x}\mid {\mathbf{a}}^{\mathrm{\top }}\mathbf{x}\le b,\mathbf{x}\in \{0,1{\}}^n\}$$

  要用动态规划解决背包问题，首先要从多阶段决策的角度来分析这个问题。决定每个物品要不要拿可以看作一次决策，在这个过程中背包的容量会变化。定义$1\le k\le n$为阶段，$0\le \lambda \le b$为状态。最优价值函数：

$$f_k(\lambda )=max\{\sum _{j=1}^k{c}_j{x}_j\mid \sum _{j=1}^k{a}_j{x}_j\le \lambda ,\mathbf{x}\in \{0,1{\}}^k\}$$

显然，当$k=n,\lambda =b$时有最优解，即$f^{\ast }=f_n(b)$。

  下面，将问题写成递归的形式。对于第$k$个物品，只有拿和不拿两种情况。

$$f_k(\lambda )=max\{f_{k-1}(\lambda ),c_k+f_{k-1}(\lambda -a_k)\}$$

初始条件：$f_0(\lambda )=0$或$f_1(\lambda )=0,\text{ if }0\le \lambda <a_1$，且$f_1(\lambda )=max(c_1,0),\text{ for }\lambda \ge a_1$。

  如何求最优解呢？令$p_l(\lambda )=0,\text{ if }{f}_k(\lambda )=f_{k-1}(\lambda )$，否则，令其为1。

  计算复杂度：$O(nb)$。（伪多项式时间）

例：0-1背包问题

3.4 Integer Knapsack Problem

  考虑整数背包问题

$f^{\ast }=max\{\sum _{j=1}^n{c}_j{x}_j\mid \sum _{j=1}^n{a}_j{x}_j\le b,x\in {\mathbb{Z}}_{+}^n\}$ 其中，$c_j<0,a_j>0,j=1,\dots ,n$。

  下面，用动态规划来解决这个问题。定义$r$为阶段，$\lambda$为状态，得到问题

$$g_r(\lambda )=max\{\sum _{j=1}^r{c}_j{x}_j\mid \sum _{j=1}^r{a}_j{x}_j\le b,x\in {\mathbb{Z}}_{+}^r\}$$

显然，当$r=n,\lambda =b$时有最优解，即$z=g_n(b)$。

  递归方程：

$$g_r(\lambda )=\underset{t=0,1,\dots ,\lfloor \lambda /a_r\rfloor }{max}\{c_{r}t+g_{r-1}(\lambda -a_{r}t)\}$$

对于$r=1,\dots ,n$和$\lambda =1,\dots ,b$，计算$g_r(\lambda )$最多需要$O(b)$次，所有$g_n(b)$的计算复杂度为$O(n{b}^2)$。

问：有更好的做法吗？
— 把每个阶段决定拿几个改成决定要不要拿一个，如果拿了一个要不要再拿下一个。

对于$x_r^{\ast }$有两种情况：
 (i) $x_r^{\ast }=0,g_r(\lambda )=g_{r-1}(\lambda )$
 (ii)$x_r^{\ast }\ge 1$，那么$x_r^{\ast }=1+t$，其中$t$是$\ge 0$的整数
  $\Rightarrow (x_1^{\ast },\dots ,x_{r-1}^{\ast },t)$对于有$r$个状态和$\lambda -a_r$个资源的背包问题是最优的。
  $\Rightarrow (g_r(\lambda )=c_r+g_r(\lambda -a_r))$。因此

$$g_r(\lambda )=max\{g_{r-1}(\lambda ),c_r+g_r(\lambda -a_r)\}$$

  计算复杂度：$O(nb)$。

例：整数背包问题

3.5 Uncapacitated Lot-Sizing

  生产计划中的批量问题指的是决定最小成本生产和产品的库存保持问题从而在有限个离散阶段内满足需求。

  $f_t$：$t$周期的固定生产成本；
  $p_t$：$t$周期的单位生产成本；
  $h_t$：$t$周期的固定储存成本；
  $d_t$：$t$周期的需求；
  $x_t$：$t$周期的产量；
  $s_t$：$t$周期末的库存，$s_0=0$，$s_n=0$；

  ULS可以被看作一个 fixed-charge network flow（固定费用网络流）问题，需要决定打开哪条边$(0,t)$（这些弧是生产周期），并找出通过网络的最小成本流。

  整数规划模型：

$$\begin{array}{ll}min& \sum _{t=1}^n{p}_t{x}_t+\sum _{t=1}^n{h}_t{s}_t+\sum _{t=1}^n{f}_t{y}_t\\ \text{s.t. }& s_{t-1}+x_t=d_t+s_t,t=1,\dots ,n,\\ & x_t\le M{y}_t,t=1,\dots ,n,\\ & s_0=0,s_n=0,s_t,x_t\ge 0,y_t\in \{0,1\},t=1,\dots ,n.\end{array}$$

其中，$M>0$是一个足够大的数（比如，各阶段的需求和）。

基本性质：
  存在一个最优解满足$s_{t-1}{x}_t=0$。
  存在一个最优解使得如果$x_t>0$，那么对于某个$k$有$x_t=\sum _{i=t}^{t+k}{d}_i$。

  令$d_{it}=\sum _{j=i}^t{d}_j$。因为$s_t=\sum _{i=1}^t{x}_i-\sum _{i=1}^t{d}_i$，目标函数可以表示成

$$\sum _{t=1}^n{p}_t{x}_t+\sum _{t=1}^n{h}_t{s}_t+\sum _{t=1}^n{f}_t{y}_t=\sum _{t=1}^n{c}_t{x}_t+\sum _{t=1}^n{f}_t{y}_t-\sum _{t=1}^n{h}_t{d}_{1t}$$

其中，$c_t=p_t+\sum _{i=t}^n{h}_i$。由于$-\sum _{t=1}^n{h}_t{d}_{1t}$为常数，所以可以从目标中去掉。

  假设$H(k)$为阶段$1,\dots ,k$的解对应的最小成本。如果$t\le k$为最后一次生产的阶段，那么$x_t=\sum _{i=t}{d}_i$，成本为$H(t-1)+f_t+c_t{d}_{tk}$。

  前向递归（Wagner-Whitin算法）：

$$H(k)=\underset{1\le t\le k}{min}\{H(t-1)+f_t+c_t{d}_{tk}\}$$

其中，$H(0)=0$。

  对$k=1,2,\dots ,n$计算$H(k)$，得到最优值$H(n)$。

  计算复杂度：$O(n^2)$。