《算法设计与分析》第07章

,第7章动态规划法,7.1一般方法和基本要素7.2每对结点间的最短路径7.3矩阵连乘7.4最长公共子序列7.5最优二叉搜索树7.60/1背包7.7流水作业调度,7.1一般方法和基本要素,动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。,引例：,Fibonacci数（数列）的计算其定义为F0=0,F1=1,Fn=Fn-1+Fn-2(n2)计算此数列可由递归函数完成intfibo(intn)intf;if(n2)f=n;elsef=fibo(n-1)+fibo(n-2);returnf;,当n=6时，函数fibo()的调用过程,6,5,4,4,3,3,2,3,2,2,1,2,1,1,0,2,1,1,0,1,0,3,3,1,0,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,改进：,intfibo(intn)inti,f,f0,f1;f0=0;f1=1;for(i=2;inextArc)intv=r-adjVex;if(r-w+costvw+costv;q=v;costj=min;dj=q;/q是j在最短子路径上的后继结点p0=0;pk-1=n-1;c=cost0;/p0和pn-1是源点和汇点for(j=1;j=k-2;j+)pj=dpj-1;/pi是最短路径上第i阶段的结点deletecost;deleted;returnc;,7.1.4资源分配问题,【例72】将n个资源分配给r个项目，已知如果把j个资源分配给第i个项目，可以收益N(i,j)，0jn，1ir。求总收益最大的资源分配方案。,动态规划算法的基本要素：,一个最优化多步决策问题适合用动态规划法求解有两个要素：最优子结构特性和重叠子问题。,最优性原理指出，一个问题的最优解包括了子问题的最优解时，则称该问题具有最优子结构特性。最优子结构特性从较小子问题的解构造较大问题的最优解时只需考虑小问题的最优解。,设计一个动态规划算法，通常可以按以下几个步骤进行：（1）刻画最优解的结构特性；（2）递归定义最优解值；（3）以自底向上方式计算最优解值；（4）根据计算得到的信息构造一个最优解。其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值。,7.2每对结点间的最短路径,7.2.1问题描述,设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数，每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径。,7.2.2动态规划法求解,最优子结构设图G=(V,E)是带权有向图，(i,j)是从结点i到结点j的最短路径长度。（1）如果k是这条路径上的一个结点，(i,k)和(k,j)分别是从i到k和从k到j的最短路径长度，则必有(i,j)=(i,k)+(k,j)。因为若不然，则(i,j)代表的路径就不是最短路径。,7.2.2动态规划法求解,最优子结构（2）如果k不是这条路径上的一个结点，(i,j)就是不包括k这个结点的子图中i与j之间的最短路径。这表明每对结点之间的最短路径问题的最优解具有最优子结构特性。,最优解的递推关系,设dn-1ij表示在从结点i到j的路径上只允许包含结点编号不大于n-1的结点时，所有可能路径中的最短路径的长度。（1）如果编号为n-1的节点不在最短路径上，那么：dn-1ij=dn-2ij（2）如果编号为n-1的节点在最短路径上，那么：dn-1ij=dn-2in-1+dn-2n-1j所以：dn-1ij=mindn-2ij,dn-2in-1+dn-2n-1j,一般地,设dkij为从i到j的只以(0-k)集合中的节点为中间结点的最短路径的长度。,重叠子问题：为了计算dkij时，必须先计算dk1ij、dk1ik和dk1kj，dk1的元素被多个dk的元素的计算共享。,7.2.3弗洛伊德算法,第一步，所有的d-1ij=wij；第二步，在当前i到j的最短路径中加入中间顶点0，取dij与di0+d0j中较小的值作dij的值，完成后得到d0ij；第三步，在当前i到j的最短路径中加入中间顶点1，取dij与di1+d1j中较小的值，完成后得到d1ij，如此进行下去，当第n步完成后，得到dn-1ij，dn-1ij表示顶点i到顶点j的最短距离。,记录i到j的最短路径pathij：结点i到j的最短路径上j之前的结点；通过对path数组的反向追溯，可得到结点i到j的最短路径。例如：结点2到3的最短路径可以这样确定：path23=1，path21=0，path20=2所以最短路径是2，0，1，3,1.初始化,【程序72】弗洛伊德算法templatevoidMGraph:Floyd(T*,for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jn;j+)if(dik+dkjdij)dij=dik+dkj;pathij=pathkj;弗洛伊德算法的时间复杂度为O(n3),7.2.4算法正确性,定理71弗洛伊德算法得到的dij，0i,jn-1是从i到j的最短路径。,7.3矩阵连乘,7.3.1问题描述,设给定矩阵为：=(aij)nm,B=(bij)mk,C=(cij)kr计算：D(AB)CA(BC)两次计算所需乘法运算次数分别为：nmk+nkrmkr+nmr运算结果相同，但进行的运算次数却差距很大。如:n=10,m=100,k=5,r=50.则有：nmk+nkr=7500mkr+nmr=75000,计算矩阵连乘积A=A1*A2*A3*A4*A5*A6，各矩阵的维数分别为：,A1:30*1；A2:1*40A3:40*10；A4:10*25矩阵相乘满足结合律。运算次数计算如下：(A1A2)A3)A4:20700(A1A2)(A3A4):41200(A1(A2A3)A4):8200A1(A2A3)A4):1400A1(A2(A3A4):11750,分析运算次数与结果。,给定n个矩阵A0,A1,An1，其中Ai，i=0,n-1的维数为pipi+1，并且Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A0A1An1，由于矩阵乘法满足结合律，所以计算矩阵的连乘可有许多不同的计算次序。矩阵连乘问题是确定计算矩阵连乘积的计算次序，使得按照这一次序计算矩阵连乘积，需要的“数乘”次数最少。,一般描述,(A1A2)A3)A4)完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。,例744个矩阵连乘积ABCD，设它们的维数分别为A:5010，B:1040,C:4030,D:305。,穷举搜索可以确定最优连乘积次序，但矩阵结合次序方法数随矩阵数量的增长呈指数级增长。显然不是有效算法。满足最优子结构、满足子结构重叠性质，可以采用动态规划求的最优解,7.3.2动态规划法求解,最优子结构矩阵连乘AiAi+1Aj简记为Ai:j，ij。于是矩阵连乘A0A1An-1可记作A0:n-1。将这一计算次序在矩阵Ak和Ak+1，0kn-1之间断开，则其相应的完全加括号形式为（A0A1Ak）（Ak+1Ak+2An1）。可先分别计算A0:k和Ak+1:n-1，然后将两个连乘积再相乘得到A0:n-1。,（A0A1Ak）（Ak+1Ak+2An1）矩阵连乘A0:n-1的最优计算次序的计算量等于A0:k和Ak+1:n-1两者的最优计算次序的计算量之和，再加上A0:k和Ak+1:n-1相乘的计算量。如果两个矩阵子序列的计算次序不是最优的，则原矩阵的计算次序也不可能是最优的。这就是说，矩阵连乘问题的最优解具有最优子结构特性。,最优解的递推关系先定义一个二维数组m，用来保存矩阵连乘时所需的最少计算量。mij表示AiAi+1Aj最少计算量,其中pi表示矩阵的行列数，Ai是pipi+1的矩阵。,重叠子问题：许多子问题被重复计算。,k此时并未确定，需要从i到j-1遍历以寻找一个最小的mij。我们把这个最小的k放在sij。,例756个矩阵连乘积A0A1A2A3A4A5，设它们的维数分别为A:3035，B:3515C:155D:510，E:1020，F:2025。,A0:3035，A1:3515,A2:155,A3:510，A4:1020，A5:2025。1、给mii置初值；(i=0,1,2,3,4,5)sii|i=0,1,2,3,4,5=(0,0,0,0,0,0)2、计算mii+1；sii+1(i=0,1,2,3,4),3、计算mii+2；(i=0,1,2,3)A0:3035，A1:3515A2:155A3:510，A4:1020，A5:2025。m02=minm00+m12+p0p1p3=0+2625+30*35*5=7875;m01+m22+p0p2p3=15750+0+30*15*5s02=0,4、计算mii+3；(i=0,1,2),m03=minm00+m13+p0p1p4=0+4375+30*35*10=14875;m01+m23+p0p2p4=15750+750+30*15*10;m02+m33+p0p3p4=7875+0+30*5*10=9375;s03=2,5、计算mii+4；(i=0,1)6、计算m05；得出最优分段位置sij，从而得到最优连乘积序列A0,n-1=(A0(A1A2)(A3A4)A5),因：s0,5=2，s0,2=0，s3,5=4所以有：A=A1*A2*A3*A4*A5*A6=(A0*A1*A2)*(A3*A4*A5)=(A0*(A1*A2)*(A3*A4)*A5)此序列为最佳序列，所需乘积次数为15125次。,7.3.3矩阵连乘算法,classMatrixChainpublic:MatrixChain(intmSize,int*q);/创建数组m和s，一维数组p，并初始化intMChain();/一般动态规划法求最优解值intLookupChain();/备忘录方法求最优解值voidTraceback();/构造最优解的公有函数private:voidTraceback(inti,intj);/构造最优解的私有递归函数intLookupChain(inti,intj);/备忘录方法私有递归int*p,*m,*s,n;,intMatrixChain:MChain()/求A0:n-1的最优解值for(inti=0;in;i+)mii=0;for(intr=1;rn;r+)for(inti=0;in-r;i+)intj=i+r;mij=mii+mi+1j+pi*pi+1*pj+1;/mij的初值sij=i;for(intk=i+1;kj;k+)intt=mik+mk+1j+pi*pk+1*pj+1;if(tmij)mij=t;sij=k;returnm0n-1;,voidMatrixChain:Traceback(inti,intj)if(i=j)coutAi;return;if(isij)cout(;Traceback(i,sij);if(isij)cout);if(sij+1j)cout(;Traceback(sij+1,j);if(sij+1j)cout);voidMatrixChain:Traceback()cout(;Traceback(0,n-1);cout);coutendl;,算法评估:三重循环，O(n3)，占用一定的空间，与穷举法相比，效率大幅度提高。,7.3.4备忘录方法,矩阵连乘的备忘录方法备忘录方法为每个已经计算的子问题建立备忘录，即保存子问题的计算结果以备需要时引用，从而避免了相同子问题的重复求解。,Fibonacci数（数列）的计算其定义为F0=0,F1=1,Fn=Fn-1+Fn-2(n2)计算此数列可由递归函数完成intfibo(intn)intf;if(n2)f=n;elsef=fibo(n-1)+fibo(n-2);returnf;,当n=6时，函数fibo()的调用过程,6,5,4,4,3,3,2,3,2,2,1,2,1,1,0,2,1,1,0,1,0,3,3,1,0,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,改进：,intfibo(intn)inti,f,f0=0,f1=1;for(i=2;i0)returnmij;if(i=j)return0;intu=LookupChain(i,i)+LookupChain(i+1,j)+pi*pi+1*pj+1;sij=i;for(intk=i+1;kj;k+)intt=LookupChain(i,k)+LookupChain(k+1,j)+pi*pk+1*pj+1;if(tu)u=t;sij=k;mij=u;returnu;,A0*A1*A2*A3*A4*A5,intMatrixChain:LookupChain()returnLookupChain(0,n-1);,7.5最优二叉搜索树,什么是二叉搜索树？若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左、右子树也分别为二叉搜索树,完全二叉搜索树具有最小的平均搜索代价，在随机的情况下，二叉搜索树的平均查找长度和logn是等数量级的。,平均搜索代价：A(T)=,当各个单词的查找概率不同时，完全二分搜索树就不一定最优了。,如：cat(0.12),come(0.08),of(0.35),the(0.45)所构成的不同的二分字典树，平均搜索代价是不同的。,2.37次比较，1.77次比较1.73次比较,实际问题中，还需考虑不成功的查找。可以扩充二分查找树。如下图：,根结点将原集合分成三部分：左子数（L），根结点ak、右子数（R）。内结点：集合中的一个元素，代表一次成功的查找。比较次数为：level(ai)外结点：一个查找区间，代表一次不成功的查找。比较次数为：level(Ei)-1,设有元素集合a1,a2,an，其中，a1a2an+，p(i)是在集合中成功查找ai的概率，1in，q(i)是待查元素x值满足aixai+1的概率,0in（假定a0=,an+1=+）。最优二叉搜索树问题是指设法构造一棵具有最小平均搜索时间的二叉搜索树。,7.5.1问题描述,7.5.2动态规划法求解,1.最优子结构,不失一般性，假设ak为这颗二叉数的根结点。,W(i,j)=,设c(0,n)是由元素值集合a1,an所构造的最优二叉搜索树的代价，则,2、递推关系,一般地，c(i,j),ij是元素值集合ai+1,aj所构造的最优二叉搜索树的代价，设r(i,j)=k为该树的根，要求结点k满足,c(i,j)的递推关系,w(i,j)的递推关系,构造最优二叉搜索树,1、计算主对角线的w、c、rw(i,i)=q(i),c(i,i)=0,r(i,i)=0,2、计算主对角线上最近的对角线的w、c、rw(i,i+1)=q(i)+q(i+1)+p(i+1)c(i,i+1)=c(i,i)+c(i+1,i+1)+w(i,i+1)=w(i,i+1)r(i,i+1)=i+13、依次计算其它对角线上的w、c、rw(i,j)=q(j)+p(j)+w(i,j-1)c(i,j)=minc(i,k-1)+c(k,j)+w(i,j)i+1kjr(i,j)=k,例77设n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。这里p和q都已乘了16。,w(0,1)=q(1)+p(1)+w(0,0)=3+3+2=8,c(0,1)=c(0,0)+c(1,1)+w(0,1)=0+0+8=8,r(0,1)=1,w(1,2)=q(2)+p(2)+w(1,1)=3+1+3=7,c(1,2)=c(1,1)+c(2,2)+w(1,2)=0+0+7=7,r(1,2)=2,例77设n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。这里p和q都已乘了16。,w(2,3)=q(3)+p(3)+w(2,2)=1+1+1=3,c(2,3)=c(2,2)+c(3,3)+w(2,3)=0+0+3=3,r(2,3)=3,w(3,4)=q(4)+p(4)+w(3,3)=1+1+1=3,c(3,4)=c(3,3)+c(4,4)+w(3,4)=0+0+3=3,r(3,4)=4,例77设n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。这里p和q都已乘了16。,w(0,2)=q(2)+p(2)+w(0,1)=1+3+8=12,c(0,2)=minc(0,0)+c(1,2)+w(0,2)=0+7+12=19,c(0,1)+c(2,2)+w(0,2)=8+0+12=20,r(0,2)=1,r(1,2)=2,w(1,3)=q(3)+p(3)+w(1,2)=1+1+7=9,c(1,3)=minc(1,1)+c(2,3)+w(1,3)=0+3+9=12,c(1,2)+c(3,3)+w(1,3)=7+0+12=19,例77设n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。这里p和q都已乘了16。,r(1,2)=3/4,w(2,4)=q(4)+p(4)+w(2,3)=1+1+3=5,c(2,4)=minc(2,2)+c(3,4)+w(2,4)=0+3+5=8,c(2,3)+c(4,4)+w(2,4)=3+0+5=8,例77设n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。这里p和q都已乘了16。,w(0,3)=q(3)+p(3)+w(0,2)=1+1+12=14,c(0,3)=minc(0,0)+c(1,3)+w(0,3)=0+12+14=26,c(0,1)+c(2,3)+w(0,3)=8+3+14=25c(0,2)+c(3,3)+w(0,3)=19+0+14=33=25,r(0,3)=2,例77设n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。这里p和q都已乘了16。,w(1,4)=q(4)+p(4)+w(1,3)=1+1+9=11,c(1,4)=minc(1,1)+c(2,4)+w(0,4)=0+8+11=19,c(1,2)+c(3,4)+w(0,4)=7+3+11=21c(1,3)+c(4,4)+w(0,4)=12+0+11=23=19,r(0,3)=2,例77设n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。这里p和q都已乘了16。,w(0,4)=q(4)+p(4)+w(0,3)=1+1+14=16,c(0,4)=minc(0,k-1)+c(k,4)+w(0,4)i+1kj=minc(0,0)+c(1,4),c(0,1)+c(2,4),c(0,2)+c(3,4),c(0,3)+c(4,4)+16=min19,16,22,25+16,=32k=2r(0,4)=k=2,r(0,4)=2,a2是根；左子树包括（a1）,r(0,1)=1,a1是根；右子树包括（a3,a4），r(2,4)=3,a3是根；右子树包括（a4），r(3,4)=4,a4是根；,7.5.3最优二叉搜索树算法,【程序77】构造最优二叉搜索树intFind(inti,intj,int*r,float*c)floatmin=INFTY;intk;for(intm=i+1;m=j;m+)if(cim-1+cmj)min)min=cim-1+cmj;k=m;returnk;,计算：c(i,j)=minc(i,k-1)+c(k,j)+w(i,j)i+1kjr(i,j)=k,voidCreateOBST(float*p,float*q,float*c,int*r,float*w,intn)for(inti=0;i=n-1;i+)wii=qi;cii=0.0;rii=0;wii+1=qi+qi+1+pi+1;cii+1=qi+qi+1+pi+1;rii+1=i+1;wnn=qn;cnn=0.0;rnn=0;,for(intm=2;m0，0i0，pi0，1iP1)xn1=1;elsexn1=0;回溯确定xn2,xn-3,x0;,7.6.5性能分析,在最坏情况下，算法的空间复杂度是O(2n)。在最坏情况下，算法的时间复杂度是O(2n)。,7.7流水作业调度,7.7.1问题描述,假定处理一个作业需要执行若干项不同类型的任务，每一类任务只能在某一台设备上执行。设一条流水线上有n个作业J=J0,J1,Jn1和m台设备P=P1,P2,Pm。每个作业需依次执行m个任务，其中第j个任务只能在第j台设备上执行，1jm。设第i个作业的第j项任务Tji所需时间为tji，1jm，0i2则不然）。,定理73流水作业调度问题具有最优子结构的性质。,如果在调度方案的作业排列中，作业i和j满足minbi,ajminbj,ai，则称作业i和j满足J