动态规划基础详解(二)概要

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,动态规划,一些应用实例,2,要点:,把握动态规划算法的根本要素,1最优子构造性质,2重叠子问题性质,把握设计动态规划算法的步骤。,(1)找出最优解的性质，并刻划其构造特征。,(2)递归地定义最优值。,(3)以自底向上的方式计算出最优值。,(4)依据计算最优值时得到的信息，构造最优解。,3,通过应用范例学习动态规划算法设计策略。,1矩阵连乘问题；,2最大子段和,3凸多边形最优三角剖分；,4多边形玩耍；,5图像压缩；,6电路布线；,7流水作业调度；,8最优二叉搜寻树。,4,矩阵连乘问题,给定n个矩阵 ，其中 与 是可乘的，。考察这n个矩阵的连乘积,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有很多不同的计算次序。这种计算次序可以用加括号的方式来确定。,假设一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,5,（,1,）单个矩阵是完全加括号的；,（,2,）矩阵连乘积 是完全加括号的，则 可,表示为,2,个完全加括号的矩阵连乘积 和,的乘积并加括号，即,16000,10500,36000,87500,34500,完全加括号的矩阵连乘积可递归地定义为：,设有四个矩阵 ，它们的维数分别是：,总共有五中完全加括号的方式,完全加括号的矩阵连乘积,6,矩阵连乘问题,给定,n,个矩阵,A,1,A,2,A,n,，其中,Ai,与,Ai+1,是可乘的，,i=1,，,2,，,n-1,。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,穷举法：列举出全部可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：,对于,n,个矩阵的连乘积，设其不同的计算次序为,P(n),。,由于每种加括号方式都可以分解为两个子矩阵的加括号问题：,(A1.Ak)(Ak+1An),可以得到关于,P(n),的递推式如下：,7,矩阵连乘问题,穷举法,动态规划,将矩阵连乘积 简记为,Ai:j,，这里,i,j,考察计算,Ai:j,的最优计算次序。设这个计算次序在矩阵,Ak,和,Ak+1,之间将矩阵链断开，,i,kj,，则其相应完全,加括号方式为,计算量：,Ai:k,的计算量加上,Ak+1:j,的计算量，再加上,Ai:k,和,Ak+1:j,相乘的计算量,8,特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子构造性质。问题的最优子构造性质是该问题可用动态规划算法求解的显著特征。,分析最优解的构造,9,建立递归关系,设计算,Ai:j,，,1ijn,，所需要的最少数乘次数,mi,j,，则原问题的最优值为,m1,n,当,i=j,时，,Ai:j=Ai,，因此，,mi,i=0,，,i=1,2,n,当,ij,时，,可以递归地定义,mi,j,为：,这里 的维数为,的位置只有,种,可能,10,计算最优值,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，很多子问题被重复计算屡次。这也是该问题可用动态规划算法求解的又一显著特征。,用动态规划算法解此问题，可依据其递归式以自底向上的方式进展计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简洁查一下，从而避开大量的重复计算，最终得到多项式时间的算法,11,用动态规划法求最优解,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(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间明显为O(n2)。,12,凸多边形最优三角剖分,用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。,假设vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。,多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。,给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。,13,三角剖分的构造及其相关问题,一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积,(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,。,14,最优子构造性质,凸多边形的最优三角剖分问题有最优子构造性质。,事实上，假设凸(n+1)边形P=v0,v1,vn的最优三角剖分T包含三角形v0vkvn，1kn-1，则T的权为3个局部权的和：三角形v0vkvn的权，子多边形v0,v1,vk和vk,vk+1,vn的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。由于假设有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的冲突。,15,最优三角剖分的递归构造,定义tij，1i1时，,2.1 j(i)。此时，。故在这种状况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。,2.2 j(i)，(i,(i)MNS(i,j)。则对任意(t,(t)MNS(i,j)有ti且(t)(i)。在这种状况下MNS(i,j)-(i,(i)是N(i-1,(i)-1)的最大不相交子集。,2.3 假设 ，则对任意(t,(t)MNS(i,j)有,t1,时,22,流水作业调度,n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的挨次都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。,流水作业调度问题要求确定这n个作业的最优加工挨次，使得从第一个作业在机器M1上开头加工，到最终一个作业在机器M2上加工完成所需的时间最少。,分析：,直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般状况下，机器M2上会有机器空闲和作业积压2种状况。,设全部作业的集合为N=1，2，n。SN是N的作业子集。在一般状况下，机器M1开头加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。将这种状况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。,23,流水作业调度,设,是所给,n,个流水作业的一个最优调度，它所需的加工时间为,a,(1),+T,。其中,T,是在机器,M2,的等待时间为,b,(1),时，安排作业,(2),，,，,(n),所需的时间。,记,S=N-,(1),，则有,T=T(S,b,(1),),。,证明：事实上，由T的定义知TT(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的最优调度冲突。故TT(S,b(1)。从而T=T(S,b(1)。这就证明白流水作业调度问题具有最优子构造的性质。,由流水作业调度问题的最优子构造性质可知，,24,Johnson,不等式,对递归式的深入分析说明，算法可进一步得到简化。,设是作业集S在机器M2的等待时间为t时的任一最优调度。假设(1)=i,(2)=j。则由动态规划递归式可得:,T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij),其中，,假设作业i和j满足minbi,ajminbj,ai，则称作业i和j满足Johnson不等式。,25,流水作业调度的,Johnson,法则,交换作业i和作业j的加工挨次，得到作业集S的另一调度，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji),其中，,当作业i和j满足Johnson不等式时，有,由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工挨次后，不增加加工时间。对于流水作业调度问题，必存在最优调度，使得作业(i)和(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意ij有,由此可知，全部满足Johnson法则的调度均为最优调度。,26,算法描述,流水作业调度问题的Johnson算法,(1)令,(2)将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序；,(3)N1中作业接N2中作业构成满足Johnson法则的最优调度。,算法简单度分析：,算法的主要计算时间花在对作业集的排序。因此，在最坏状况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。,27,最优二叉搜寻树,二叉搜寻树,1假设它的左子树不空，则左子树上全部,节点的值均小于它的根节点的值；,2假设它的右子树不空，则右子树上全部,节点的值均大于它的根节点的值；,3 它的左、右子树也分别为二叉排序树,45,12,53,3,37,24,100,61,90,78,在随机的情况下，二叉查找树的平均查找长度,和 是等数量级的,28,查找成功与不成功的概率,二查找树的期望消耗,有 个节点的二叉树的个数为：,穷举搜寻法的时间简单度为指数级,二叉查找树的期望消耗,29,二叉查找树的期望消耗例如,30,最优二叉搜寻树,最优二叉搜寻树Tij的平均路长为pij，则所求的最优值为p1,n。由最优二叉搜寻树问题的最优子构造性质可建立计算pij的递归式如下,记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为,留意到，,可以得到O(n2)的算法,