动态规划(第7章)

2020/1/4AlgorithmsDesignTechniquesandAnalysis算法设计技巧与分析0华南师范大学计算机学院2020/1/4华南师范大学计算机学院1第七章动态规划动态规划的基本模式7.1引言7.2最长公共子序列问题7.3矩阵链乘7.4动态规划的基本模式应用7.5所有点对间的最短路问题7.60-1背包问题2020/1/4华南师范大学计算机学院27.1引言问题1：计算Fibonaccisequence:f(n)=f(n-1)+f(n-2),n2;f(1)=1,f(2)=1.算法1（直接递归法）2020/1/4华南师范大学计算机学院37.1引言根据递推公式，当n很大时，其时间时间复杂度分析：O(1.618n)(见例2.20)。也就是，计算f(n)所需要的运行时间对于n的值是指数的。该算法的特点：子问题的求解有大量的重复时间复杂度分析：O(1.618n)2020/1/4华南师范大学计算机学院4算法2（备忘录方法）算法特点：从上到下计算子问题，每个子问题只计算一次时间复杂度分析：O(n)intfibonacci(Integern){if(list.get(n-1)!=0){returnlist.get(n-1);}list.add(n-1,fibonacci(n-1)+fibonacci(n-2));returnlist.get(n-1);}7.1引言2020/1/4华南师范大学计算机学院5算法3（动态规划法）算法特点：从下到上计算子问题，每个子问题只计算一次时间复杂度分析：O(n)for(inti=2;i=n;i++){result=f1+f2;f1=f2;f2=result;}7.1引言2020/1/4华南师范大学计算机学院6问题2：计算二项式系数Cnk。算法1——直接递归计算算法特点：有大量的重复计算7.1引言2020/1/4华南师范大学计算机学院7问题2：计算二项式系数Cnk。算法2算法特点：用帕斯卡三角从下到上来计算，每个子问题只算一次。即可以用下列填矩阵的方式求出C(n，k)。7.1引言2020/1/4华南师范大学计算机学院8算法复杂度大概的估计一下，只填了下三角矩阵，算法复杂度大概的估计一下，只填了下三角矩阵，为n*k/2=n*k，具体的次数为：为n*k/2=n*k，具体的次数为：7.1引言2020/1/4华南师范大学计算机学院9算法伪代码第一个for是控制行的，要填到第n行。第二个for来控制每行填到哪的，到i和k的较小值。从这2个for也可以看出复杂度为n*k。7.1引言2020/1/4华南师范大学计算机学院107.2最长公共子序列问题问题给定某字母表上的两个长度分别为n和m的串A和B,要求确定A和B的最长公共子序列的长度。穷举法2020/1/4华南师范大学计算机学院11动态规划算法命题7.1设L(i,j)表示A=a1a2…ai和B=b1b2…bj的最长公共子序列的长度。则L(i,0)=0L(0,j)=0ifai=bj,L(i,j)=L(i-1,j-1)+1ifaibj，L(i,j)=max{L(i-1,j),L(i,j-1)}其中，1in,1jn.7.2最长公共子序列问题12Algorithm7.1LCS7.2最长公共子序列问题2020/1/4华南师范大学计算机学院137.2最长公共子序列问题2020/1/4华南师范大学计算机学院147.2最长公共子序列问题2020/1/4华南师范大学计算机学院157.3矩阵链乘问题求对n个矩阵进行连乘积M1M2…Mn的最小乘法次数。2020/1/4华南师范大学计算机学院167.3矩阵链乘穷举法2020/1/4华南师范大学计算机学院177.3矩阵链乘2020/1/4华南师范大学计算机学院187.3矩阵链乘动态规划算法设C(i,j)表示求MiMi+1…Mj的最少乘法次数。则C(i,i)=0ifij，C(i,j)=minikj{C(i,k-1)+C(k,j)+rirkrj+1}特别，C(1,n)=min1kn{C(1,k-1)+C(k,n)+r1rkrn+1}其中，1ijn.2020/1/4华南师范大学计算机学院197.3矩阵链乘2020/1/4华南师范大学计算机学院20Algorithm7.2MATCHAIN7.3矩阵链乘2020/1/4华南师范大学计算机学院217.3矩阵链乘2020/1/4华南师范大学计算机学院227.3矩阵链乘2020/1/4华南师范大学计算机学院237.3矩阵链乘2020/1/4华南师范大学计算机学院247.3矩阵链乘2020/1/4华南师范大学计算机学院25时间复杂度——定理7.27.3矩阵链乘2020/1/4华南师范大学计算机学院26适用范围多阶段决策的最优化问题最优解满足最优性原理子问题的重叠性基本思想设计一个动态规划算法有四个步骤7.4动态规划的基本模式2020/1/4华南师范大学计算机学院27适用问题多阶段决策的最优化问题问题的求解过程分阶段来完成，在每阶段需要做出一个决策，形成一个决策序列。每个决策序列对应一个目标函数值。要求求出目标值最优（最大或最小）的决策序列，即最优决策序列（最优解），所对应的目标值为最优值。阶段1阶段2阶段n终止状态初始状态7.4动态规划的基本模式2020/1/4华南师范大学计算机学院28最优性原理当问题的最优解包含有子问题的最优解时，称该问题满足最优性原理。因此，问题的最优解可在其子问题的最优解中寻找。这就决定了计算过程是：首先将问题分解为子问题，求得子问题的最优解，由此再构造得到原问题的最优解。子问题重叠性原问题的子问题中由于可能有大量重复的子问题，而相同的子问题只求解一次，因而其效率往往高于枚举法。且子问题重复的越多，其效率越高。7.4动态规划的基本模式2020/1/4华南师范大学计算机学院29动态规划法的基本思想将原问题转化为若干个子问题来解决。但是每个子问题只计算一次。因此，一般需要将子问题的解保存起来以避免重复计算。对所考虑的每个子问题都求出最优解，然后由子问题的最优解递推地构造原问题的最优解。但是，在求解过程中由于需要将子问题的解保存下来以备将来使用，所以该方法往往需要较多的附加空间。7.4动态规划的基本模式2020/1/4华南师范大学计算机学院30动态规划法的基本步骤1.证明满足最优性原理实际上即是说明大问题的最优解可从子问题的最优解答中找。这就决定了计算是从下而上地进行根据子问题的最优解逐步构造出整个问题的最优解的过程。2.递归定义最优解的值即找出如何由子问题的最优解得到原问题的最优解的关系式。3.按自下而上的方式计算最优解的值4.由计算的结果构造出一个最优解7.4动态规划的基本模式2020/1/4华南师范大学计算机学院317.5所有结点对间的最短路问题问题设G=V,E是一个有向图，图中每条边i,j都有一个成本（长度）l[i,j]，若从结点i到结点j没有边，则令l[i,j]=。要求找出从每个结点到所有其它结点的长度最短的路。假定图中没有负长度的回路。2020/1/4华南师范大学计算机学院32动态规划算法设dk(i,j)表示从i到j的一条中间不经过比k大的结点的最短路径的长度。则d0(i,j)=l[i,j],当nk1时,dk(i,j)=min{dk-1(i,j)，dk-1(i,k)+dk-1(k,j)}特别，dn(i,j)=min{dn-1(i,j)，dn-1(i,n)+dn-1(n,j)}7.5所有结点对间的最短路问题2020/1/4华南师范大学计算机学院332020/1/4华南师范大学计算机学院347.5所有结点对间的最短路问题2020/1/4华南师范大学计算机学院35例7.5Algorithm7.3FLOYD时间复杂度:(n3)空间复杂度:(n2)习题7.32Warshall算法习题7.337.5所有结点对间的最短路问题2020/1/4华南师范大学计算机学院367.60-1背包问题问题设U={u1,u2,…,un}是n个待放入容量为C的背包的物品集.任意i:ni1,设si和vi分别是第i种物品的重量和价值。每个物品要么整个放入背包，要么不放。且已知物品i放入背包能产生vi的价值(ni1)。其中C和si、vi（n1）均为正整数。如何装包才能获得最大价值？2020/1/4华南师范大学计算机学院377.60-1背包问题动态规划算法设V(i,j)表示从{u1,u2,…,ui}挑选物件装入容量为j的背包中的最优装包的价值。则V(i,0)=0V(0,j)=0若i0且jsi,V(i,j)=V(i-1,j)若i0且jsi,V(i,j)=max{V(i-1,j),V(i-1,j-si)+vi}2020/1/4华南师范大学计算机学院387.60-1背包问题Algorithm7.4KNAPSACK定理7.3时间复杂度:(nC)空间复杂度:(C)2020/1/4华南师范大学计算机学院39一个实例设0-1背包问题中n=4,C=9,n个物品的重量分别为{2,3,4,5}，其价值分别{3,4,5,7}。使用动态规划法求解最优装包方法的过程即是填写如下表格：0123456789000000000001003333333320034477777300344789912400345781011127.60-1背包问题2020/1/4华南师范大学计算机学院40练习题Page140-1437.5，7.11，7.15，7.22