计算机算法设计与分析--第3章动态规划.ppt

计算机算法设计与分析 Design and Analysis of Computer Algorithms,第三章 动态规划 Dynamic Programming,2019年4月16日,2,理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。,学习要点:,2019年4月16日,3,提纲,一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树,2019年4月16日,4,提纲,一、动态规划算法的思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树,2019年4月16日,5,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,1.1算法总体思想,2019年4月16日,6,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,1.1算法总体思想,2019年4月16日,7,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,1.1算法总体思想,2019年4月16日,8,1.1 总体思想,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但分解后的子问题往往不是相互独立的。 Divide-and-conquer技术的问题 子问题是相互独立的； 如果子问题不是相互独立的，分治方法将重复计算公共子问题，效率很低。 Dynamic Programming特点 把原始问题划分成一系列子问题； 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间； 自底向上地计算。,2019年4月16日,9,1.2 适用范围,适用范围 一类最优化问题：可分为多个相关子问题，子问题的解被重复使用。 最优化问题 给定一组约束条件和一个代价函数，在解空间中搜索具有最小或最大代价的最优解； 很多最优化问题可分为多个子问题，子问题相互关联，子问题的解被重复使用。,2019年4月16日,10,1.3 基本要素,使用动态规划算法的条件： 最优子结构(optimal sub-structure) 当一个问题的最优解包含了子问题的最优解时，称这个问题具有最优子结构； 最优子结构使得能自底而上地完成求解过程； 通常可用“剪贴”(cut and paste)技术判定最优子结构。 重叠子问题(overlapping sub-problems) 在问题的求解过程中，很多子问题的解将被多次使用。,2019年4月16日,11,1.4 设计步骤,1.分析最优解的结构； 2.递归地定义最优值； 3.自底向上地计算出最优值，并获取构造最优解的信息； 4.根据构造最优解的信息构造优化解。,2019年4月16日,12,提纲,一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树,2019年4月16日,13,2.1 问题定义,Matrix-chain Multiplication 输入：,Ai是矩阵，Ai与Ai1可乘，i1,2,(n-1)； 输出：计算A1A2.An的最小代价方法,矩阵乘法的代价/复杂性: 乘法的次数 若A是pq矩阵，B是qr矩阵，则AB 的代价是O(pqr),2019年4月16日,14,2.1 问题定义,矩阵连乘法的实现 矩阵乘法满足结合律； 计算一个矩阵链的乘法可有多种方法: 例如, （A1A2A3A4） =（A1(A2(A3A4) =（(A1A2)(A3A4）) = (（A1A2）A3)A4),2019年4月16日,15,2.1 问题定义,完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可 表示为2个完全加括号的矩阵连乘积B和 C 的乘积并加括号，即A=(B*C),给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，设矩阵Ai的维数为pi-1 pi，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序（即如何完全加括号），使得依此次序计算矩阵连乘积需要的乘法次数最少。,2019年4月16日,16,2.1 问题定义,矩阵连乘法的代价与计算顺序的关系 设A1=10100矩阵, A2=1005矩阵, A3=550矩阵 T(A1A2)A3)=101005+10550=7500 T(A1(A2A3)=100550+1010050=75000,结论: 不同计算顺序有不同的代价！,2019年4月16日,17,16000, 10500, 36000, 87500, 34500,设有四个矩阵 ，它们的维数分别是：,总共有五中完全加括号的方式,不同计算顺序有不同的代价！,2019年4月16日,18,矩阵连乘问题,给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,2019年4月16日,19,矩阵连乘问题,给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,2019年4月16日,20,p(n)= 1 if n=1 p(n)= if n1 p(n)=C(n-1)=Catalan数= = (4n/n3/2),设p(n)=计算n个矩阵乘积的不同计算次序 p(n)的递归方程：,（A1 Ak)(Ak+1An),如此之大的解空间是无法用枚举方法求出最优解的！,2.2 矩阵连乘问题的解空间,2019年4月16日,21,Catalan数是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁查理卡塔兰 (18141894)命名。 原理： 令h(0)=1,h(1)1,catalan数满足递归式： h(n)= h(0)*h(n-1) + h(1)*h(n-2) + . + h(n-1)h(0) (其中n=2) 该递推关系的解为： h(n)=C(2n,n)/(n + 1) (n=1,2,3,.),2019年4月16日,22,2.3求解矩阵连乘问题的动态规划算法,分析最优解的结构； 递归地定义最优值； 自底向上地计算出最优值，并获取构造最优解的信息； 根据构造最优解的信息构造优化解。,2019年4月16日,23,2.3.1 分析最优解的结构,两个记号 Ai:j=AiAi+1Aj mij=计算Ai:j的最少乘法次数 最优解的结构 若计算A1:n的最优顺序在k处断开矩阵链, 即A1:n=A1:kAk+1:n，则在A1:n的最优顺序中，对应于子问题A1:k的解必须是A1:k的最优解，对应于子问题Ak+1:n的解必须是Ak+1:n的最优解。,具有最优子结构： 问题的最优解包括子问题的最优解,2019年4月16日,24,2.3.1 分析最优解的结构,子问题重叠性,A1A2A3A4,(A1)(A2A3A4),(A1A2)(A3A4 ),(A1A2 A3)(A4 ),具有子问题重叠性,2019年4月16日,25,2.3.2递归地定义最优值,假设 mij=计算Ai:j的最小乘法数 设（Ai.Ak）（Ak+1 .Aj)是最优化解(k实际上是不可预知),考虑到所有的k，最优值的递归方程为： mi j= 0 if i=j mi j= minikj mi k+mk+1 j+pi-1 pk pj if ij,其中, pi-1pkpj是计算Ai:kAk+1:j所需乘法数,Ai:k和Ak+1:j分别是pi-1pk和pkpj矩阵.,这里 的维数为,2019年4月16日,26,建立递归关系,的位置只有 种可能,可以递归地定义mi,j为：,k(i,i+1,j-1),2019年4月16日,27,2.3.3计算最优值,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法,2019年4月16日,28,自底向上计算最优值,mi j= mini k j mi k + mk+1 j + pi-1 pk pj ,m15,m11,m44,m55,m22,m33,m45,m34,m23,m12,m13,m24,m35,m14,m25,m24 = min,m22+m34 p1p2p4 m23+m44 p1p3p4,2019年4月16日,29,2.3.3自底向上计算最优值,mij= mini k j mik + mk+1j + pi-1 pk pj ,m15,m11,m44,m55,m22,m33,m45,m34,m23,m12,m13,m24,m35,m14,m25,2019年4月16日,30,2.3.3自底向上计算最优值,void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) /* 计算第r个对角线 */ for (int i = 1; i = n - r+1; i+) int j=i+r-1; /* 计算mij */ mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; ,获取构造最优解的信息：Sij记录Ai:j的最优次序的断开位置k,2019年4月16日,31,算法复杂度分析： 算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。,2019年4月16日,32,2019年4月16日,33,消除重复的矩阵连乘算法,Void MatrixChain(int p, int n, int *m, int *s) for (int i = 1; i = n; i+) mii = 0; /将对角线元素赋值为零，即单个矩阵计算量为0 for (int r = 2; r = n; r+) for (int i = 1; i = n r +1; i+) int j = i + r 1; (5) mij = mi+1j + pi1*pi*pj; /计算Ai, j = Ai: i Ai+1: j sij = i; /记下断点i (7) for (int k = i + 1; k j; k+) int t = mik + mk+1j + pi1*pk*pj; /对ikj, 逐个计算Ai, j = Ai: k Ak+1: j if (t mij) mij = t; sij = k; /记下较小的mij及相应的断点k ,第(5)步与第(7)步 能否合在一起?,能。此处分开是为 了给mij赋初值。,2019年4月16日,34,MatrixChain的运行举例,设要计算矩阵连乘积A1A2A3A4A5A6，其维数分别为3535, 3515, 155, 510, 1020, 2025, 即p0=35, p1=35, p2=15, p3=5, p4=10, p5=20, p6=25。,MatrixChain用矩阵mij, sij存放子问题Ai: j的最小计算量以及相应的断点。,1 2 3 4 5 6,1 2 3 4 5 6,mij,1 2 3 4 5 6,1 2 3 4 5 6,sij,MatrixChain将如下面红色箭头所示的过程逐个计算子问题Ai: j：,执行for (int i = 1; i = n; i+) mii = 0后将对角线元素全部置零，即子问题Aii = 0。,0,0,0,0,0,0,当r=2，执行第(5)句完成了相邻矩阵Aii+1=pi1*pi*pj 的计算，并在sij中添入了相应的断点。其中的第(7)句因为j = i+1(k=i+1)而被跳过去了，实际并没有执行。,15750,2625,750,1000,5000,1,2,3,4,5,当r=3，i=1时，执行第(5)句计算A1:12:3， m13 = m23 + p0*p1*p3 = 2625 +30*35*5 = 7875,7875,1,执行第(7)句计算A1:23:3， t = m12 + m33 + p0*p2*p3 = 15750+0+35*15*5 = 183757875，所以m13不变，断点仍为1。,当r=3，i=2时，执行第(5)句计算A2:23:4，m24 = m34 + p1*p2*p4 = 750 +35*15*10 = 6000,6000,2,执行第(7)句计算A2:34:4， t = m23+m44+ p1*p3*p4 = 2625+0+35*5*10 = 43756000，所以m24改为4375，断点改为3。,4375,3,当r=3，i=3时，执行第(5)句计算A3:34:5，m35 = m45 + p2*p3*p5 = 1000 +15*5*20 = 2500,2500,3,执行第(7)句计算A3:45:5， t = m34+m55+ p2*p4*p5 = 750+0+15*10*20 = 37502500，所以m35仍为2500，断点仍为3。,当r=3，i=4时，执行第(5)句计算A4:45:6，m46 = m56 + p3*p4*p6 = 5000 +5*10*25 = 6250,6250,4,执行第(7)句计算A4:56:6， t = m45+m66+ p3*p5*p6 = 1000+0+5*20*25 = 35006250，所以m46改为3500，断点改为5。,3500,5,类似的，当r=4、5、6时，可以计算出相应的mij及其相应的断点sij，如下图中所示：,9375,3,7125,3,5375,3,11875,3,10500,3,15125,3,由m16=15125可知这6个矩阵连乘积的最小运算次数为15125。由s16 = 3可知A1: 6的最优计算次序为A1: 3 A4: 6；由s13=1可知A1: 3的最优计算次序为A1: 1 A2: 3；由s46=5可知A4: 6的最优计算次序为A4: 5 A6: 6；因此最优计算次序为：(A1(A2A3)(A4A5)A6)。,2019年4月16日,35,2.3.4 构造最优解,void Traceback(int i, int j, int* *s) if (i = =j) return; Traceback(i,sij,s); Traceback(sij+1,j,s); cout “Multiply A”i“,”sij; cout “and A”(sij+1)“,”j; endl; ,调用Traceback(1, n,s) 即可输出A1:n的最优计算顺序,2019年4月16日,36,2.4 算法复杂度分析,时间复杂性 计算代价的时间 三层循环, 循环体内的计算量O(1)； O(n3) 构造最优解的时间: O(n) 总时间复杂性为：O(n3) 空间复杂性 使用数组m和S 需要空间O(n2),2019年4月16日,37,动态规划算法的基本要素,一、最优子结构,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,2019年4月16日,38,动态规划算法的基本要素,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,2019年4月16日,39,直接递归中有大量重复计算,直接递归中有大量重复计算，如A1: 4计算中：,1: 4,1: 1,2: 4,1: 2,3: 4,1: 3,4: 4,2: 2,3: 4,2: 3,4: 4,1:1,2: 2,3: 3,4: 4,1: 1,2: 3,1: 2,3: 3,3: 3,4: 4,2: 2,3: 3,2: 2,3: 3,1: 1,2: 2,图中红框标出的都是重复计算。,2019年4月16日,40,直接递归的时间复杂性,根据前面的递归式不难得出的时间复杂性为,n1 1 + (T(k) + T(nk) + 1) k=1,T(n) ,n1 = 1 + (n 1) +(T(k) + T(nk) k=1,n1 n1 = n +T(k) + T(nk) k=1 k=1,可用数学归纳法证明T(n)2n1 = (2n)。,直接递归算法的时间复杂性随n的指数增长。,n1 = n + 2T(k) k=1,2019年4月16日,41,动态规划中采用自底向上的方式。但是在递归定义中往往是自上而下的描述。备忘录方法就采用与递归定义一致的自上而下的方式。 备忘录方法同样用表格来保存已解子问题的信息。每个子问题初始化时都标记为尚未求解。在递归求解过程中，对每个待解子问题，先查看它是否已求解。若未求解，则计算其解并填表保存。若已求解，则查表取出相应的结果。 备忘录方法同样避免了子问题的重复计算，因而和动态规划算法具有同样效率。,2019年4月16日,42,2.5 备忘录方法,动态规划算法是自底向上递归的； 备忘录方法是自顶向下递归的；,int LookupChain(int i，int j) if (mij 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; ,int MemoizedMatrixChain (int n, int *m, int *s) for(int i=1; i=n; i+) for(int j=I; j=n; j+) mij=0; return LookupChain(1, n); ,2019年4月16日,43,2019年4月16日,44,提纲,一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树,2019年4月16日,45,3.1 问题定义,Longest Common Subsequence (LCS) 定义一：若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B,C,B,A是序列X=A,B,C,B,D,A,B的子序列，相应的递增下标序列为2,3,5,7。 定义二：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。,2019年4月16日,46,给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 例如： X=A,B,C,B,D,A,B，Y=B,D,C,A,B,A，则X和Y的公共子序列有B,C,A；B,C,B；B,C,B,A 最长公共子序列:公共子序列中长度最长的子序列。,2019年4月16日,47,最长公共子序列问题 给定两个序列X=x1,x2,xm和Y=y1,y2, yn，找出X和Y的一个最长公共子序列,？,2019年4月16日,48,例子,X = A, B, C, B, D, A, B X = A, B, C, B, D, A, B Y = B, D, C, A, B, A Y = B, D, C, A, B, A B, C, B, A和B, D, A, B都是X和Y 的最长公共子序列(长度为4) 但是,B, C, A就不是X和Y的最长公共子序列,2019年4月16日,49,穷举法,对于每一个Xm的子序列,验证它是否是Yn的子序列. Xm有2m个子序列 每个子序列需要(n)的时间来验证它是否是Yn的子序列. 从Yn的第一个字母开始扫描下去,如果不是则从第二个开始 运行时间: (n2m),2019年4月16日,50,3.1 问题定义,最长公共子序列（LCS）问题 输入：X = (x1,x2,.,xm)，Y = (y1,y2,.yn) 输出：Z = X与Y的一个最长公共子序列,步骤： 最长公共子序列 (LCS) 结构分析; 建立求解LCS长度的递归方程 ; 自底向上计算LCS的长度; 构造最优解。,2019年4月16日,51,3.2 LCS结构分析,第i前缀定义： 设X=(x1, x2, ., xm)是一个序列，X的第i前缀Xi是一个序列，定义为Xi=(x1, ., xi ) 例. X=(A, B, D, C, A), X1=(A), X2=(A, B), X3=(A, B, D),2019年4月16日,52,递归方程,第1种情况: xi = yj 例如: Xi = A, B, D, E Yj = Z, B, E 把xi=yj 添加到Xi-1和Yj-1最长共同子序列中. 一定可以找到Xi-1和Yj-1的最长共同子序列 一个问题的最优解一定包含了子问题的最优解.,2019年4月16日,53,递归解法,第2种情况: xi yj 例子: Xi = A, B, D, G Yj = Z, B, D 需要解决两个问题 找到 Xi-1和Yj的一个最长共同子序列: Xi-1 = A, B, D,Yj = Z, B, D 找到一个Xi和Yj-1的一个最长共同子序列: Xi = A, B, D, G, Yj-1 = Z, B 一个问题的最优解一定包含了子问题的最优解,ci, j =,max ci - 1, j, ci, j-1 ,2019年4月16日,54,重叠子问题,找Xm和Yn的最长共同子序列 我们可能需要在Xm和Yn-1中找最长共同子序列,或者是在Xm-1和Yn中. 上面的问题都有一个在Xm-1和Yn-1中找最长共同子序列的子问题. 子问题又有子子问题,2019年4月16日,55,3.2 LCS结构分析,最优子结构：设X=(x1, ., xm)、Y=(y1, ., yn) 是两个序列，Z=(z1, ., zk)是X与Y的一个LCS，则有： 如果xm=yn, 则zk=xm=yn, Zk-1是Xm-1和Yn-1的LCS， 即，LCS(X,Y) = LCS(Xm-1,Yn-1)+ . 如果xmyn，且zkxm，则Z是Xm-1和Y的LCS， 即，LCS(X,Y) = LCS(Xm-1,Y) 如果xmyn,且zkyn,则Z是X与Yn-1的LCS， 即，LCS(X,Y) = LCS(X,Yn-1),由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,2019年4月16日,56,3.2 LCS结构分析,子问题重叠性,LCS(X,Y),LCS(Xm-1,Yn-1),LCS(Xm-1,Y),LCS(X,Yn-1),LCS(Xm-2,Yn-2),LCS(Xm-2,Yn-1),LCS(Xm-1,Yn-2),LCS问题具有子问题重叠性,2019年4月16日,57,3.3建立LCS的递归方程,Cij = Xi与Yj 的LCS的长度 LCS长度的递归方程:,2019年4月16日,58,3.4自底向上计算LCS的长度,基本思想：,计算过程：,C00,C01,C03,C02,C04,C10,C20,C30,C11,C21,C31,C12,C13,C14,C22,C23,C24,C32,C33,C34,2019年4月16日,59,3.4自底向上计算LCS的长度,void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i =cij-1) cij=ci-1j; bij= “”; else cij=cij-1; bij= “”; ,cij存储Xi和Yj的最长公共子序列的长度； 获取构造最优解的信息：bij是指针，指向计算cij时所选择的子问题的最优解所对应的c表的表项。,2019年4月16日,60,例子,X = A, B, C, B, D, A,B Y = B, D, C, A, B, A,0 当i=0或者j=0 ci, j = ci-1, j-1 + 1 当 xi = yj max(ci, j-1, ci-1, j) 当xi yj,0,1,2,6,3,4,5,yj,B,D,A,C,A,B,5,1,2,0,3,4,6,7,D,A,B,xi,C,B,A,B, 0, 0, 0,1,1,1, 1,2,2019年4月16日,61,3.5 构造最优解,基本思想 从Bm n开始按指针搜索 若Bi j=“”，则xi=yj是LCS的一个元素 如此找到的“LCS”是X与Y的LCS的Inverse,void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij=“ ”) LCS(i-1，j-1，x，b); coutxi; else if (bij= “”) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); ,2019年4月16日,62,找出最长共同子序列,从bm, n开始并跟着箭头走. 当我们在bi, j中碰到 “ ” xi = yj 是最长共同子序列中的一个元素,0,1,2,6,3,4,5,yj,B,D,A,C,A,B,5,1,2,0,3,4,6,7,D,A,B,xi,C,B,A,B, 0, 0, 0,1,1,1, 1,2,2019年4月16日,63,思考： 若有两个字符串A=“xyxxzxyzxy” 和B=“zxzyyzxxyxxz”，试用LCS算法求出最长公共子序列。,2019年4月16日,64,3.6 算法复杂度分析,时间复杂性 计算代价的时间 (i, j)两层循环,i循环m步, j循环n步 O(mn) 构造最优解的时间: O(m+n) 总时间复杂性为：O(mn) 空间复杂性 使用数组c和b 需要空间O(mn),2019年4月16日,65,算法的改进,在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。 如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。,2019年4月16日,66,提纲,一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树,2019年4月16日,67,最大子段和问题,给定由n个整数组成的序列(a1, a2, , an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。,（1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； （2）比较不同算法的时间性能； （3）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。,2019年4月16日,68,提纲,一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树,2019年4月16日,69,5.1 问题定义,0/1 Knapsack Problem 给定n种物品和一个背包，物品i的重量是wi，价值vi,背包容量为C，问如何选择装入背包的物品，使装入背包中的物品的总价值最大？ 对于每种物品只能选择完全装入或不装入，一个物品至多装入一次。 输入：C0, wi0, vi0, 1 in 输出：(x1, x2, , xn), xi0, 1, 满足 1inwi xi C, 1invi xi 最大,2019年4月16日,70,5.1 问题定义,0-1背包问题是一个特殊的整数规划问题：,0/1背包问题可以看作是决策一个序列(x1, x2, , xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, , xi-1)，在决策xi时，问题处于下列两种状态之一： （1）背包容量不足以装入物品i，则xi=0，背包不增加价值； （2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。,2019年4月16日,71,5.2 最优解结构的分析,最优子结构：如果(y1, y2, , yn)是0-1背包问题的一个最优解，则(y2, , yn)是如下子问题的一个最优解：,max 2 i n vi xi 2in wixi C w1 y1 xi0, 1, 2 i n,证明：如果(y2, , yn)不是子问题优化解, 则存在(z2, , zn)是子问题更优的解。于是, (y1, z2, , zn)是原问题比(y1, y2, , yn)更优解，矛盾。,2019年4月16日,72,5.3 建立求解最优值的递归方程,设所给0-1背包问题的子问题：,的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下：,2019年4月16日,73,template void Knapsack(Type v,int w,int c,int n,Type*m) int jMax=min(wn-1,c); for(int j=0;j1;i-) int jMax=min(wi-1,c); for(int j=0;j=w1) m1c=max(m2c,m2 c-w1 +v1); ,2019年4月16日,74,template void Traceback(Type*m,int w,int c,int n,int x) for(int i=1;in;i+) if(mic=mi+1c) xi=0; else xi=1;c-=wi; xn=(mnc)?1:0; ,2019年4月16日,75,假设w=2,2,6,5,4 v=6,3,5,4,6 该程序按循环顺序运行的时候先是由语句for(int j=0;j=jMax;j+)和for(int j=wn;j=c;j+)进行初始化： m50=0 m51=0 m52=0 m53=0 m54=6 ： ： m510=6,2019年4月16日,76,接着由循环体 for(int i=n-1;i1;i-) int jMax=min(wi-1,c); for(int j=0;j=jMax;j+) mij=mi-1j; for(int j=wi;j=c;j+) mij=max(mi+1j,mi+1 j-wi +vi); 完成由i从4到2的计算,2019年4月16日,77,当i =4时 m40=0 m41=0 m42=0 m43=0 m44=6 ： ： m48=6 m49=10 m410=10,2019年4月16日,78,当i =3时 m30=0 m31=0 m32=0 m33=0 m34=6 ： ： m38=6 m39=10 m310=11,2019年4月16日,79,当i =2时 m20=0 m21=0 m22=3 m23=3 m24=6 m25=6 m26=9 ： ： m28=6 m29=10 m210=11,2019年4月16日,80,最后是对于i=1时的处理。 m1c=m2c; if(c=w1) m1c=max(m2c,m2 c-w1 +v1); m110=15,2019年4月16日,81,I=1 I=2 I=3 I=4 I=5,2019年4月16日,82,5.4 自底向上计算最优值,计算m(i, j)需要 m(i+1, j-wi)和m(i+1, j),令wi=整数, n=4,m(2,C-w1),m(1,C),m(2,C),m(4, 0),m(3, C-w1-w2),m(3,C-w1),m(4,C-w2),m(4,C-w1),m(4,C),m(3,C),m(3,C-w2),m(3, 0),m(2, 0),m(4, C-w1-w2),2019年4月16日,83,5.5构造最优解,1. m(1, C)是最优解代价值，相应解计算如下： If m(1, C)=m(2, C) Then x1=0 Else x1=1; 2. 如果x1=0, 由m(2, C)继续构造最优解； 3. 如果x1=1, 由m(2, C-w1)继续构造最优解。,2019年4月16日,84,5.6 算法复杂性分析,Knapsack的计算时间：O(nc)； Traceback的计算时间：O(n)； 当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要(n2n)计算时间。 可以对 Knapsack算法进行改进，详见课本。,2019年4月16日,85,设 表示从前i项中取出来的装入体积为j的背包的物品的最大值， 。其中 ，表示没有东西装入体积为j的背包中； 而 表示没有东西可以装入体积为0的背包中。 我们要寻求的是值 。,0-1背包另一种思路：,2019年4月16日,86,如果将背包的容量作为多阶段决策，当 时，有如下结论： 是下面两个量的最大值。 （1） ：仅用最优的方法取自前i-1项的物品装入容量为j的背包所得到的价值的最大值。 （2） ：用最优的方法取自前i-1项的物品装入容量为 的背包所得到的价值的最大值加上物品i的价值。当且仅当 以及它等于把物品i加到背包上的情况。,2019年4月16日,87,因此得到如下递推关系式：,2019年4月16日,88,动态规划算法,算法knapsack 输入：重量分别为 ， 价值分别为 的物品， 背包的容量为 正整数C。 输出： 的最大价值，且满足 ，,2019年4月16日,89,1. for to n 2. 3. end for 4. for to c 5. 6. end for 7.for to n 8.for to c 9. .,10. If then,11. end for 12. end for 13. Return,2019年4月16日,90,算法分析：第1-3步计算时间为 ；第4-6步计算时间为 ；第7-12步两个for 循环计算时间为 ，所以算法的时间复杂度为 。空间复杂性也是 。 背包问题的最优解能够在 的时间内和 的空间内得到。,2019年4月16日,91,提纲,一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树,2019年4月16日,92,6.1 问题定义,二叉搜索树The Optimal binary search trees 给定一个由n个互异的关键字组成的序列S=x1,x2,xn，并且关键字有序，即x1x2xn。根据这些关键字构造的一颗二叉搜索树满足： （1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； （2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； （3）它的左、右子树也分别为二叉搜索树。,2019年4月16日,93,6.1 问题定义,二叉搜索树T S=x1, x2, , xn，关键字 Y=y0, y1, , yn，虚拟键 yi对应区间(xi, xi+1) y0对应区间(-, x1) yn对应区间(xn,+) 搜索xi的概率为bi 搜索yi的概率为ai,2019年4月16日,94,6.1 问题定义,二叉搜索树的平均路长（期望代价）：,其中， 是关键字 的结点深度； 是虚拟关键字 的结点深度。,2019年4月16日,95,6.1 问题定义,例如：,期望搜索代价为2.80,2019年4月16