算法导论复习（六）| 动态规划-易微帮

文章目录

最优化问题：这一类问题的可行解可能有很多个。每个解都有一个值，我们希望寻找具有最优值的解（最小值或最大值）。

求目标函数F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型。

动态规划与分治法的联系

动态规划与分治法：通过组合子问题的解来求解原问题。

分治法：互不相交的子问题，递归地求解子问题。如果子问题有重叠，则递归求解中就会反复地求解这些公共子问题，造成算法效率的下降。
动态规划：有子问题重叠的情况，即不同的子问题具有公共的子子问题。动态规划算法对每个这样的子子问题只求解一次，将其解保存在一个表格中，再次碰到时，无需重新计算，只从表中找到上次计算的结果加以引用即可。

动态规划算法的步骤

刻画一个最优解的结构特征；
递归地定义最优解的值；
计算最优解的值；
利用计算出的信息，构造一个最优解。

动态规划问题的特点

考题：

最优子结构

如果一个问题的最优解包含其子问题的最优解，就称此问题具有最优子结构的性质。

无后效性

对任意的阶段i，阶段i以后的行为仅依赖于i阶段的状态，而与i阶段之前过程是如何达到这种状态的方式无关，这种性质称为无后效性。

状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，而不能直接作用于未来的发展。

重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

利用动态规划求解问题的方法

第一步：证明问题满足最优性原理
第二步：获得问题状态的递推关系式（即状态转移方程）

证明最优子结构：“剪切-粘贴”法

证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。
利用反证法：假定子问题的解不是其自身的最优解，那么就可以~~从原问题的解中“剪切”掉这些非最优解，将最优解“粘贴”进去~~（把非最优解用最优解替换），从而得到原问题的一个更优的解，这与~~最初的解是原问题的最优解的前提~~假设矛盾。

状态转移方程

钢条切割

给定一段长度为n英寸的钢条和一个价格表P，求切割钢条方案，使得销售收益 r_n 最大。
分析：如果长度为n英寸的钢条的价格pn足够大，则可能完全不需要切割，出售整条钢条是最好的收益。
但由于每个pi不同，可能切割后出售会更好一些。

长度为n英寸的钢条共有2^n-1中不同的切割方案。

证明最优子结构性

求解过程

上述两种动态规划算法的时间复杂度均为Θ(n²)。

通常，自顶向下法和自底向上法具有相同的渐近运行时间。

递归调用树

子问题图

子问题图：用于描述子问题与子问题之间的依赖关系。

矩阵链乘法

已知A为p×r的矩阵，B为r×q的矩阵，则A与B的乘积是一个p×q的矩阵，记为C。计算C共需要pqr次标量乘法运算。

矩阵链相乘
n个要连续相乘的矩阵构成一个矩阵链<A1,A2,…,An>,计算矩阵链乘积。
1.矩阵链乘满足结合律。
2.相当于在矩阵之间加适当的括号

给定n个矩阵的链<A1,A2,…,An>，其中i=1,2,…,n，矩阵Ai的维数为p_i-1×p_i。求一个完全“括号化方案”，使得计算乘积A1A2…An所需的标量乘法次数最小。

证明最优子结构性

求解过程

其中，s[i,j]记录使m[i,j]取最小值的k。

下述过程MATRIX-CHAIN-ORDER采用自底向上表格法计算n个矩阵链乘的最优模式。

考试中求矩阵链乘法的最优括号化方案时，需要构建m表和s表，注意一些求解技巧（~~如果真的忘记算法的话）~~：

m表左j右i，第一行（最下一行）对角线元素全填0，第二行对角线元素是p_i-1*p_i*p_i+1,(i取1、3、…、2n-1)，往上依据状态转移方程求：
s表左j右i，记录m[i,j]取值最小时括号的位置，第一行对角线元素填1~n-1；所填数字i表示在Ai后用括号分隔。