Dynamic Programming
Table of Contents
这篇主要是动态规划算法设计相关的笔记。关于算法其他方面的笔记，可以参考本博客 AlgorithmIntroduce 这篇文章。
<!–more–>
动态规划法
动态规划的特征
- 最优子结构
如果问题的一个最优解包含子问题的最优解，就称该问题具有最优子结构。
例如： 如果 z = LCS(x,y)，那么任何 z 序列的前缀也是 x 序列前缀和 y 序列前缀的最长公共子序列 - 重叠子问题，一个递归的过程包含少数独立的子问题被反复计算多次。
- 在动态规划法中，每一步都要做出选择，但是这些选择依赖于子问题的解。因此，解动态规划问题一般是自底向上，从小子问题处理至大子问题。这样可以避免子问题被反复计算。
找寻最优子结构的模式
- 问题的一个解可以是做一个选择。做这种选择会得到一个或多个有待解决的子问题。
- 假设对一个给定的问题，已知的是一个可以导致最优解的选择。不必关心如何确定这个选择，尽管假定它是已知的。
- 在已知这个选择后，要确定哪些子问题会随之发生，以及如何最好地描述所得到的子问题空间。
描述子问题空间的一个有效经验是，尽量保持这个空间简单，然后在需要时再扩充它。
在装配线调度问题中，我们所考虑的子问题空间就是从工厂入口通过装配站 \(S_{1,j}和 S_{2,j}\) 的最快路线。这个子问题空间很合适，因而没必要再去尝试一个更具一般性的子问题空间了。
在矩阵链乘积问题中，考虑的子问题空间是从第 1 个矩阵到第 j 个矩阵相乘时，最优化的加括号方法。 - 利用 cut-and-paste 技术，来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。
动态规划算法的设计步骤
算法导论列出的设计步骤
- 描述最优解的结构。即寻找最优子结构，利用子问题的最优解来构造原问题的一个最优解。
- 递归定义最优解的值。
- 按自底向上计算最优解的值。
- 由计算出的结果构造一个最优解。
另一种设计步骤
- 列出所有涉及到的变量
- 定义问题的状态
- 定义状态转移方程
这一步的本质，其实就是寻找最优子结构。找到最优子结构，就可以定义出状态转移方程！
首先，将问题划分为子问题。
划分子问题的方法：
- 问题的一个解可以是做一个选择。做这种选择会得到一个或多个有待解决的子问题。
- 观察状态转移方程。将自变量减去一个值（一般为 1），看看得到的子问题是什么问题。
- 问题的一个解可以是做一个选择。做这种选择会得到一个或多个有待解决的子问题。
- 然后，通过子问题来定义原问题，从而得出状态转移方程
- 求解问题
下面No description for this link中使用了该设计步骤。
实例
最长公共子序列
有两个序列 x[1…m] y[1…n], (1) 求这两个序列的最长公共子序列之一的长度 (2) 输出所有最长公共子序列
穷举法
取 x[1…m]的所有子序列，分别遍历 y[1…n]来查看是否该子序列是公共子序列，记录下当前最长的所有公共子序列。遍历完之后，依次输出。
- 算法分析
每次遍历 y[1…n]的消耗为 n，x[1…m]一共有 \(2^m\) 个子序列，所以总的时间消耗为 \(n2^m\)
动态规划法
教科书方式
定义 \(LCS(x,y)\) 为序列 x 和 y 的最长公共子序列之一
定义 \(|S|\) 为 \(S\) 序列的长度
定义 \(c[i,j] = |LCS(x[1,i],y(1,j))|\)
则 \(c[m,m] = |LCS(x,y)|\)
- 最坏情况分析
取上面的递归公式中最耗时的部分 \(c[i,j] = max(c[i,j-1], c[i-1,j])\) ，将其转化为递归树，可以计算出树的高度为 $m+n$，这个树的节点数目为 \(2^{m+n}\) - 子问题被重复计算
LCS 问题的子问题空间包含 \(m*n\) 个独立的子问题(c[i,j]一共有 m*n 种组合)，而在最坏情况分析中，一共需要解决的问题数目为 \(2^{m+n}\) ，可以通过记录已经求解过的问题的结果来避免重复的计算。
使用平摊分析可以得出采用记录求解过的问题结果后，LCS 的时间复杂度为 \(O(n*m)\)
另一种方式
所有涉及到的变量
\(序列 S1、序列 S2、最长公共子序列 S、最长公共子序列长度 LCS\)
\(隐含的变量 S1 第 i 个元素 S1_i、S2 第 j 个元素 S2_j\)
定义问题的状态
- 方案 1
LCS(S1,S2) 表示序列 S1 和序列 S2 的最长公共子序列的长度
更一般的描述是，LCS(s1,s2) 表示序列 s1 和序列 s2 的最长公共子序列的长度
使用序列最后一个值的索引值来表示也是等价的。即，LCS(i,j) - 方案 2
LCS(S1) 表示序列 S1 和序列 S2 的最长公共子序列的长度
更一般的描述是，LCS(s1) 表示序列 s1 和序列 S2 的最长公共子序列的长度
使用序列最后一个值的索引值来表示也是等价的。即，LCS(i) - 方案 3
LCS(S) 表示序列 S1 和序列 S2 的最长公共子序列 S 的长度
更一般的描述是，LCS(s) 表示序列 s1 和序列 s2 的最长公共子序列的长度
使用序列最后一个值的索引值来表示也是等价的。即，LCS(k)
定义状态转移方程
- 方案 1
将问题划分为多个子问题
\begin{align} &LCS(i-1,j) 如果不包含 s1 的最后一个值 \nonumber \\ &LCS(i-1,j)+1 如果包含 s1 的最后一个值 \nonumber \\ \end{align}
以最长公共子序列中是否包含当前 s1 序列中最后一个值来划分问题
通过子问题来定义原问题
\begin{eqnarray} LCS(i,j) = \begin{cases} LCS(i-1,j) & 包含 s1_i \\ LCS(i-1,j)+1 & 不包含 s1_i \\ \end{cases} \nonumber \end{eqnarray}
- 方案 2
将问题划分为多个子问题
\begin{align} &LCS(i-1) 如果不包含 s1 的最后一个值 \nonumber \\ &LCS(i-1)+1 如果包含 s1 的最后一个值 \nonumber \\ \end{align}
以最长公共子序列中是否包含当前 s1 序列中最后一个值来划分问题
通过子问题来定义原问题
\begin{eqnarray} LCS(i) = \begin{cases} LCS(i-1) & 包含 s1_i \\ LCS(i-1)+1 & 不包含 s1_i \\ \end{cases} \nonumber \end{eqnarray}
这种方案的缺点是去掉 s2 这个自变量以后，很难有效定义包含和不包含 \(s1_i\) 的条件。
- 方案 3
将问题划分为多个子问题
\begin{align} &LCS(k) 如果不包含 s1 的最后一个值 \nonumber \\ &LCS(k-1)+1 如果包含 s1 的最后一个值 \nonumber \\ \end{align}
以最长公共子序列中是否包含当前 s1 序列中最后一个值来划分问题
通过子问题来定义原问题
\begin{eqnarray} LCS(k) = \begin{cases} LCS(k-1) & 包含 s1_i \\ LCS(k-1)+1 & 不包含 s1_i \\ \end{cases} \nonumber \end{eqnarray}
求解问题
背包问题
求解过程
所有涉及到的变量
\(物品总数量 N；物品编号 i（物品 i 的价值 W_i 物品 i 的体积 C_i）；背包容量 V；装完背包后获得的最大总价值 F\)
定义问题的状态
- 方案 1
通过两个自变量来描述问题，即 F(N,V) 表示从 N 个物体中进行选取放入 V 空间中所获得的最大总价值
更一般的描述就是，F(i,v)表示从 i 个物体中进行选取放入 v 空间中所获得的最大总价值 - 方案 2
通过物品总数量这个自变量来描述问题，即 F(N)表示从 N 个物体中进行选取放入 V 空间中所获得的最大总价值
更一般的描述就是，F(i)表示从 i 个物体中进行选取放入 V 空间中所获得的最大总价值 - 方案 3
通过背包体积这个自变量来描述问题，即 F(V)表示从 N 个物体中进行选取放入 V 空间中所获得的最大总价值
更一般的描述就是，F(v)表示从 N 个物体中进行选取放入 v 空间中所获得的最大总价值
定义状态转移方程
方案 1
将问题划分为多个子问题
\begin{align} &F(i-1,v) 如果不选择第 i 个物品 \nonumber \\ &F(i-1,v-C_i)+W_i 如果选择第 i 个物品 \nonumber \\ \end{align}
以是否选择第 i 个物品来划分问题就会得到下面的子问题。
通过子问题来定义原问题
\begin{eqnarray} F(i,v) = \begin{cases} F(i-1,v) & 不选择物品 i \\ F(i-1,v-C_i)+W_i & 选择物品 i \\ \end{cases} \nonumber \end{eqnarray}
方案 2
将问题划分为多个子问题
\begin{align} &F(i-1) 如果不选择第 i 个物品 \nonumber \\ &F(i-1)+W_i 如果选择第 i 个物品 \nonumber \\ \end{align}
以是否选择第 i 个物品来划分问题就会得到下面的子问题。
通过子问题来定义原问题
\begin{eqnarray} F(i) = \begin{cases} F(i-1) & 不选择物品 i \\ F(i-1)+W_i & 选择物品 i \\ \end{cases} \nonumber \end{eqnarray}
从上面定义中可以看出没有考虑背包容量，所以通过子问题定义的原问题是错误的。
方案 3
将问题划分为多个子问题
\begin{align} &F(v) 如果不选择第 i 个物品 \nonumber \\ &F(v-C_i)+W_i 如果选择第 i 个物品 \nonumber \\ \end{align}
以是否选择第 i 个物品来划分问题就会得到下面的子问题。
通过子问题来定义原问题
\begin{eqnarray} F(v) = \begin{cases} F(v) & 不选择物品 i \\ F(v-C_i)+W_i & 选择物品 i \\ \end{cases} \nonumber \end{eqnarray}