动态规划基础详解(二)课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,要点,:,掌握动态规划算法的基本要素,（,1,）最优子结构性质,（,2,）重叠子问题性质,掌握设计动态规划算法的步骤。,(1),找出最优解的性质，并刻划其结构特征。,(2),递归地定义最优值。,(3),以自底向上的方式计算出最优值。,(4),根据计算最优值时得到的信息，构造最优解。,2,通过应用范例学习动态规划算法设计策略。,（,1,）矩阵连乘问题；,（,2,）最大子段和,（,3,）凸多边形最优三角剖分；,（,4,）多边形游戏；,（,5,）图像压缩；,（,6,）电路布线；,（,7,）流水作业调度；,（,8,）最优二叉搜索树。,3,矩阵连乘问题,给定,n,个矩阵 ，其中 与 是可乘的，。考察这,n,个矩阵的连乘积,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用,2,个矩阵相乘的标准算法计算出矩阵连乘积,4,（,1,）单个矩阵是完全加括号的；,（,2,）矩阵连乘积 是完全加括号的，则 可,表示为,2,个完全加括号的矩阵连乘积 和,的乘积并加括号，即,16000,10500,36000,87500,34500,完全加括号的矩阵连乘积可递归地定义为：,设有四个矩阵 ，它们的维数分别是：,总共有五中完全加括号的方式,完全加括号的矩阵连乘积,5,矩阵连乘问题,给定,n,个矩阵,A,1,A,2,A,n,，其中,Ai,与,Ai+1,是可乘的，,i=1,，,2,，,n-1,。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,穷举法,：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：,对于,n,个矩阵的连乘积，设其不同的计算次序为,P(n),。,由于每种加括号方式都可以分解为两个子矩阵的加括号问题：,(A1.Ak)(Ak+1An),可以得到关于,P(n),的递推式如下：,6,矩阵连乘问题,穷举法,动态规划,将矩阵连乘积 简记为,Ai:j,，这里,i,j,考察计算,Ai:j,的最优计算次序。设这个计算次序在矩阵,Ak,和,Ak+1,之间将矩阵链断开，,i,kj,，则其相应完全,加括号方式为,计算量：,Ai:k,的计算量加上,Ak+1:j,的计算量，再加上,Ai:k,和,Ak+1:j,相乘的计算量,8,建立递归关系,设计算,Ai:j,，,1ijn,，所需要的最少数乘次数,mi,j,，则原问题的最优值为,m1,n,当,i=j,时，,Ai:j=Ai,，因此，,mi,i=0,，,i=1,2,n,当,ij,时，,可以递归地定义,mi,j,为：,这里 的维数为,的位置只有,种,可能,9,计算最优值,对于,1ijn,不同的有序对,(i,j),对应于不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，,许多子问题被重复计算多次,。这也是该问题可用动态规划算法求解的又一显著特征。,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法,10,用动态规划法求最优解,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+),for(int i=1;i=n-r+1;i+),int j=i+r-1;,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;,A1,A2,A3,A4,A5,A6,30,35,35,15,15,5,5,10,10,20,20,25,算法复杂度分析：,算法,matrixChain,的主要计算量取决于算法中对,r,，,i,和,k,的,3,重循环。循环体内的计算量为,O(1),，而,3,重循环的总次数为,O(n,3,),。因此算法的计算时间上界为,O(n,3,),。算法所占用的空间显然为,O(n,2,),。,11,凸多边形最优三角剖分,用多边形顶点的逆时针序列表示凸多边形，即,P=v,0,v,1,v,n-1,表示具有,n,条边的凸多边形。,若,v,i,与,v,j,是多边形上不相邻的,2,个顶点，则线段,v,i,v,j,称为多边形的一条弦。弦将多边形分割成,2,个多边形,v,i,v,i+1,v,j,和,v,j,v,j+1,v,i,。,多边形的三角剖分,是将多边形分割成互不相交的三角形的弦的集合,T,。,给定凸多边形,P,，以及定义在由多边形的边和弦组成的三角形上的权函数,w,。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。,12,三角剖分的结构及其相关问题,一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积,(A,1,(A,2,A,3,)(A,4,(A,5,A,6,),所相应的语法树如图,(a),所示。,凸多边形,v,0,v,1,v,n-1,的三角剖分也可以用语法树表示。例如，图,(b),中凸多边形的三角剖分可用图,(a),所示的语法树表示。,矩阵连乘积中的每个矩阵,A,i,对应于凸,(n+1),边形中的一条边,v,i-1,v,i,。三角剖分中的一条弦,v,i,v,j,，,ij,，对应于矩阵连乘积,Ai+1:j,。,13,最优子结构性质,凸多边形的最优三角剖分问题有最优子结构性质。,事实上，若凸,(n+1),边形,P=v,0,v,1,v,n,的最优三角剖分,T,包含三角形,v,0,v,k,v,n,，,1kn-1,，则,T,的权为,3,个部分权的和：三角形,v0vkvn,的权，子多边形,v,0,v,1,v,k,和,v,k,v,k+1,v,n,的权之和。可以断言，由,T,所确定的这,2,个子多边形的三角剖分也是最优的。因为若有,v,0,v,1,v,k,或,v,k,v,k+1,v,n,的更小权的三角剖分将导致,T,不是最优三角剖分的矛盾。,14,最优三角剖分的递归结构,定义,tij,，,1ijn,为凸子多边形,vi-1,vi,vj,的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形,vi-1,vi,具有权值,0,。据此定义，要计算的凸,(n+1),边形,P,的最优权值为,t1n,。,tij,的值可以利用最优子结构性质递归地计算。当,j-i1,时，凸子多边形至少有,3,个顶点。由最优子结构性质，,tij,的值应为,tik,的值加上,tk+1j,的值，再加上三角形,v,i-1,v,k,v,j,的权值，其中,ikj-1,。由于在计算时还不知道,k,的确切位置，而,k,的所有可能位置只有,j-i,个，因此可以在这,j-i,个位置中选出使,tij,值达到最小的位置。由此，,tij,可递归地定义为：,15,多边形游戏,多边形游戏是一个单人玩的游戏，开始时有一个由,n,个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“,+”,或“*”。所有边依次用整数从,1,到,n,编号。,游戏第,1,步，将一条边删除。,随后,n-1,步按以下方式操作：,(1),选择一条边,E,以及由,E,连接着的,2,个顶点,V1,和,V2,；,(2),用一个新的顶点取代边,E,以及由,E,连接着的,2,个顶点,V1,和,V2,。将由顶点,V1,和,V2,的整数值通过边,E,上的运算得到的结果赋予新顶点。,最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。,问题,:,对于给定的多边形，计算最高得分。,16,最优子结构性质,在所给多边形中，从顶点,i(1in),开始，长度为,j(,链中有,j,个顶点,),的顺时针链,p(i,，,j),可表示为,vi,，,opi+1,，,，,vi+j-1,。,如果这条链的最后一次合并运算在,opi+s,处发生,(1sj-1),，则可在,opi+s,处将链分割为,2,个子链,p(i,，,s),和,p(i+s,，,j-s),。,设,m1,是对子链,p(i,，,s),的任意一种合并方式得到的值，而,a,和,b,分别是在所有可能的合并中得到的最小值和最大值。,m2,是,p(i+s,，,j-s),的任意一种合并方式得到的值，而,c,和,d,分别是在所有可能的合并中得到的最小值和最大值。依此定义有,am1b,，,cm2d,(1),当,opi+s=+,时，显然有,a+cmb+d,(2),当,opi+s=*,时，有,minac,，,ad,，,bc,，,bdmmaxac,，,ad,，,bc,，,bd,换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。,17,图像压缩,图象的变位压缩存储格式将所给的象素点序列,p1,p2,pn,0pi255,分割成,m,个连续段,S1,S2,Sm,。第,i,个象素段,Si,中,(1im),，有,l,i,个象素,且该段中每个象素都只用,bi,位表示。设 则第,i,个象素段,Si,为,设 ，则,hi,bi,8,。因此需要用,3,位表示,bi,如果限制,1,li,255,，则需要用,8,位表示,li,。因此，第,i,个象素段所需的存储空间为,li*bi+11,位。按此格式存储象素序列,p1,p2,pn,，需要 位的存储空间。,图象压缩问题要求确定象素序列,p1,p2,pn,的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过,256,位。,18,图像压缩,设,l,i,，,bi,，是,p1,p2,pn,的最优分段。显而易见，,l,1,，,b1,是,p,1,p,l1,的最优分段，且,l,i,，,bi,，是,p,l1+1,p,n,的最优分段。即图象压缩问题满足最优子结构性质。,设,si,，,1in,，是象素序列,p1,pn,的最优分段所需的存储位数。由最优子结构性质易知：,其中,算法复杂度分析：,由于算法,compress,中对,k,的循环次数不超这,256,，故对每一个确定的,i,，可在时间,O(1),内完成的计算。因此整个算法所需的计算时间为,O(n),。,19,电路布线,在一块电路板的上、下,2,端分别有,n,个接线柱。根据电路设计，要求用导线,(i,(i),将上端接线柱与下端接线柱相连，如图所示。其中,(i),是,1,2,n,的一个排列。导线,(i,(i),称为该电路板上的第,i,条连线。对于任何,1i(j),。,电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集,Nets=(i,(i),1in,的最大不相交子集。,20,记 。,N(i,j),的最大不相交子集为,MNS(i,j),。,Size(i,j)=|MNS(i,j)|,。,(1),当,i=1,时，,(2),当,i1,时，,2.1 j(i),。此时，。故在这种情况下，,N(i,j)=N(i-1,j),，从而,Size(i,j)=Size(i-1,j),。,2.2 j(i),，,(i,(i),M,NS(i,j),。,则对任意,(t,(t),M,NS(i,j),有,ti,且,(t)(i),。在这种情况下,MNS(i,j)-(i,(i),是,N(i-1,(i)-1),的最大不相交子集。,2.3,若 ，则对任意,(t,(t),M,NS(i,j),有,t1,时,21,流水作业调度,n,个作业,1,，,2,，,，,n,要在由,2,台机器,M1,和,M2,组成的流水线上完成加工。每个作业加工的顺序都是先在,M1,上加工，然后在,M2,上加工。,M1,和,M2,加工作业,i,所需的时间分别为,a,i,和,b,i,。,流水作业调度问题要求确定这,n,个作业的最优加工顺序，使得从第一个作业在机器,M1,上开始加工，到最后一个作业在机器,M2,上加工完成所需的时间最少。,分析：,直观上，一个最优调度应使机器,M1,没有空闲时间，且机器,M2,的空闲时间最少。在一般情况下，机器,M2,上会有机器空闲和作业积压,2,种情况。,设全部作业的集合为,N=1,，,2,，,，,n,。,S,N,是,N,的作业子集。在一般情况下，机器,M1,开始加工,S,中作业时，机器,M2,还在加工其它作业，要等时间,t,后才可利用。将这种情况下完成,S,中作业所需的最短时间记为,T(S,t),。流水作业调度问题的最优值为,T(N,0),。,22,流水作业调度,设,是所给,n,个流水作业的一个最优调度，它所需的加工时间为,a,(1),+T,。其中,T,是在机器,M2,的等待时间为,b,(1),时，安排作业,(2),，,，,(n),所需的时间。,记,S=N-,(1),，则有,T=T(S,b,(1),),。,证明：,事实上，由,T,的定义知,T,T(S,b,(1),),。若,TT(S,b,(1),),，设,是作业集,S,在机器,M2,的等待时间为,b,(1),情况下的一个最优调度。则,(1),，,(2),，,，,(n),是,N,的一个调度，且该调度所需的时间为,a,(1),+T(S,b,(1),)a,(1),+T,。这与,是,N,的最优调度矛盾。故,T,T(S,b,(1),),。从而,T=T(S,b,(1),),。这就证明了流水作业调度问题具有最优子结构的性质。,由流水作业调度问题的最优子结构性质可知，,23,Johnson,不等式,对递归式的深入分析表明，算法可进一步得到简化。,设,是作业集,S,在机器,M2,的等待时间为,t,时的任一最优调度。若,(1)=i,(2)=j,。则由动态规划递归式可得,:,T(S,t)=a,i,+T(S-i,b,i,+maxt-a,i,0)=a,i,+a,j,+T(S-i,j,t,ij,),其中，,如果作业,i,和,j,满足,minb,i,a,j,minb,j,a,i,，则称作业,i,和,j,满足,Johnson,不等式,。,24,流水作业调度的,Johnson,法则,交换作业,i,和作业,j,的加工顺序，得到作业集,S,的另一调度，它所需的加工时间为,T(S,t)=a,i,+a,j,+T(S-i,j,t,ji,),其中，,当作业,i,和,j,满足,Johnson,不等式时，有,由此可见当作业,i,和作业,j,不满足,Johnson,不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度,，使得作业,(i),和,(i+1),满足,Johnson,不等式。进一步还可以证明，调度满足,Johnson,法则当且仅当对任意,ij,有,由此可知，,所有满足,Johnson,法则的调度均为最优调度。,25,算法描述,流水作业调度问题的,Johnson,算法,(1),令,(2),将,N,1,中作业依,a,i,的非减序排序；将,N,2,中作业依,b,i,的非增序排序；,(3)N,1,中作业接,N,2,中作业构成满足,Johnson,法则的最优调度。,算法复杂度分析：,算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为,O(nlogn),。所需的空间为,O(n),。,26,最优二叉搜索树,二叉搜索树,（,1,）若它的左子树不空，则左子树上,所有,节点的值,均小于,它的根节点的值；,（,2,）若它的右子树不空，则右子树上,所有,节点的值,均大于,它的根节点的值；,（,3,它的左,、,右子树也分别为二叉排序树,45,12,53,3,37,24,100,61,90,78,在随机的情况下，二叉查找树的平均查找长度,和 是等数量级的,27,查找成功与不成功的概率,二查找树的期望耗费,有 个节点的二叉树的个数为：,穷举搜索法的时间复杂度为指数级,二叉查找树的期望耗费,28,二叉查找树的期望耗费示例,29,最优二叉搜索树,最优二叉搜索树,T,ij,的平均路长为,p,ij,，则所求的最优值为,p,1,n,。由最优二叉搜索树问题的最优子结构性质可建立计算,p,ij,的递归式如下,记,w,i,j,p,i,j,为,m(i,j),，则,m(1,n)=w,1,n,p,1,n,=p,1,n,为所求的最优值。计算,m(i,j),的递归式为,注意到，,可以得到,O(n,2,),的算法,