算法导论复习（六）| 动态规划

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

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

---

动态规划与分治法的联系

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

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

---

动态规划算法的步骤

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

---

动态规划问题的特点

考题：

最优子结构

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

无后效性

对任意的阶段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后用括号分隔。
  

时间复杂度分析

算法的主体由一个三层循环构成。MATRIX-CHAIN-ORDER的算法复杂度是Ω(n3)。另外，算法需要Θ(n2)的空间保存m和s。

最优化原理

---

最长公共子序列LCS

(1) 子序列
给定两个序列X=<x1,x2,…,xn>和序列Z=<z1,z2,…,zk>,若存在X的一个严格递增下标序列<i1,i2,…,ik>，使得对所有j=1,2,…,k，有x_ij=z_j，则称Z是X的子序列。

如：Z=<B,C,D,B>是X=<A,B,C,B,D,A,B>的一个子序列，相应下标序列为<2,3,5,7>。

2）公共子序列
对给定的两个序列X和Y，若序列Z既是X的的子序列，也是Y的子序列，则称Z是X和Y的公共子序列。

如，X=<A,B,C,B,D,A,B>,Y=<B,D,C,A,B,A>，则序列<B,C,A>是X和Y的一个公共子序列。

3）最长公共子序列
两个序列的长度最大的公共子序列称为它们的最长公共子序列。

如，<B,C,A>是上面X和Y的一个公共子序列，但不是X和Y的最长公共子序列。最长公共子序列是<B,C,B,A>。

证明最优子结构性




根据上述状态转移方程，从上到下画出m[i,j]表（左i上j）。

---

最优二叉搜索树

（1）二叉搜索树（二分检索树）
二叉搜索树Ｔ是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：
·Ｔ的左子树的所有元素比根结点中的元素小；
·Ｔ的右子树的所有元素比根结点中的元素大；
·Ｔ的左子树和右子树也是二叉搜索树。

注：二分检索树要求树中所有结点的元素值互异

（2）最优二叉搜索树

? 给定一个n个关键字的已排序的序列K=<k1,k2,…,kn>（不失一般性，设 k1<k2<…<kn），对每个关键字ki，都有一个概率pi表示其搜索频率。根据ki和pi构建一个二叉搜索树T，每个ki对应树中的一个结点。

1.若搜索对象x等于某个ki，则一定可以在T中找到结点ki；
2.若x<k1 或 x>kn 或 ki<x<ki+1(1≤i<n), 则在T中将搜索失败。

• 为此引入外部结点d0,d1,…,dn，用来表示不在K中的值，称为伪结点。
• 这里每个di代表一个区间， d0表示所有小于k1的值， dn表示所有大于kn的值，对于i=1,2,…,n-1，di表示所有在ki和ki+1之间的值。
• 同时每个di也有一个概率qi表示搜索对象x恰好落入区间di的频率。

最优二叉搜索树的定义
对给定的概率集合，期望搜索代价最小的二叉搜索树称为最优二叉搜索树。






重点是e表、w表、root表的计算。



根据root表构建搜索树。

---