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

南京邮电大学计算机学院2008年3月,算法设计与分析,DeSignandAnalysisofAlgorithmsInC+,“十一五”国家级规划教材,陈慧南编著,电子工业出版社,南京邮电大学计算机学院2008年3月,第2部分算法设计策略,南京邮电大学计算机学院2008年3月,第7章动态规划法,南京邮电大学计算机学院2008年3月,7.1一般方法和基本要素7.2每对结点间的最短路径7.3矩阵连乘7.4最长公共子序列7.5最优二叉搜索树7.60/1背包7.7流水作业调度,南京邮电大学计算机学院2008年3月,7.1一般方法和基本要素,南京邮电大学计算机学院2008年3月,动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。,南京邮电大学计算机学院2008年3月,7.1.1一般方法,最优性原理指出，一个最优策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，其余决策必定构成最优策略。这便是最优决策序列的最优子结构特性。,南京邮电大学计算机学院2008年3月,设计一个动态规划算法，通常可以按以下几个步骤进行：（1）刻画最优解的结构特性；（2）递归定义最优解值；（3）以自底向上方式计算最优解值；（4）根据计算得到的信息构造一个最优解。其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值。,南京邮电大学计算机学院2008年3月,7.1.2基本要素,一个最优化多步决策问题适合用动态规划法求解有两个要素：最优子结构特性和重叠子问题。,南京邮电大学计算机学院2008年3月,7.1.3多段图问题,例71多段图G=(V,E)是一个带权有向图，它具有如下特性：图中的结点被划分成k2个互不相交的子集Vi，1ik。其中V1和Vk分别只有一个结点，V1包含源点（source）s，Vk包含汇点（sink）t。对所有边E，多段图要求若uVi，则vVi1，1i=0;j-)floatmin=INFTY;for(ENode*r=aj;r;r=r-nextArc)intv=r-adjVex;if(r-w+costvw+costv;q=v;costj=min;dj=q;p0=0;pk-1=n-1;for(j=1;j=k-2;j+)pj=dpj-1;deletecost;deleted;,南京邮电大学计算机学院2008年3月,7.1.4资源分配问题,【例72】将n个资源分配给r个项目，已知如果把j个资源分配给第i个项目，可以收益N(i,j)，0jn，1ir。求总收益最大的资源分配方案。,南京邮电大学计算机学院2008年3月,南京邮电大学计算机学院2008年3月,7.2每对结点间的最短路径,南京邮电大学计算机学院2008年3月,7.2.1问题描述,设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数，每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径。,南京邮电大学计算机学院2008年3月,7.2.2动态规划法求解,最优子结构设图G=(V,E)是带权有向图，(i,j)是从结点i到结点j的最短路径长度，k是这条路径上的一个结点，(i,k)和(k,j)分别是从i到k和从k到j的最短路径长度，则必有(i,j)=(i,k)+(k,j)。因为若不然，则(i,j)代表的路径就不是最短路径。这表明每对结点之间的最短路径问题的最优解具有最优子结构特性。,南京邮电大学计算机学院2008年3月,最优解的递推关系,重叠子问题：为了计算dkij时，必须先计算dk1ij、dk1ik和dk1ik，dk1的元素被多个dk的元素的计算共享。,南京邮电大学计算机学院2008年3月,7.2.3弗洛伊德算法,弗洛伊德算法的基本思想是：令k=0,1,n-1，每次考察一个结点k。二维数组d用于保存各条最短路径的长度，其中，dij存放从结点i到结点j的最短路径的长度。在算法的第k步上应作出决策：从i到j的最短路径上是否包含结点k。,南京邮电大学计算机学院2008年3月,【程序72】弗洛伊德算法templatevoidMGraph:Floyd(T*,南京邮电大学计算机学院2008年3月,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),南京邮电大学计算机学院2008年3月,南京邮电大学计算机学院2008年3月,7.2.4算法正确性,定理71弗洛伊德算法得到的dij，0i,jn-1是从i到j的最短路径。,南京邮电大学计算机学院2008年3月,7.3矩阵连乘,南京邮电大学计算机学院2008年3月,7.3.1问题描述,给定n个矩阵A0,A1,An1，其中Ai，i=0,n-1的维数为pipi+1，并且Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A0A1An1，由于矩阵乘法满足结合律，所以计算矩阵的连乘可有许多不同的计算次序。矩阵连乘问题是确定计算矩阵连乘积的计算次序，使得按照这一次序计算矩阵连乘积，需要的“数乘”次数最少。,南京邮电大学计算机学院2008年3月,完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。,南京邮电大学计算机学院2008年3月,例744个矩阵连乘积ABCD，设它们的维数分别为A:5010，B:1040,C:4030,D:305。,南京邮电大学计算机学院2008年3月,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。,南京邮电大学计算机学院2008年3月,矩阵连乘A0:n-1的最优计算次序的计算量等于A0:k和Ak+1:n-1两者的最优计算次序的计算量之和，再加上A0:k和Ak+1:n-1相乘的计算量。如果两个矩阵子序列的计算次序不是最优的，则原矩阵的计算次序也不可能是最优的。这就是说，矩阵连乘问题的最优解具有最优子结构特性。,南京邮电大学计算机学院2008年3月,最优解的递推关系先定义一个二维数组m，用来保存矩阵连乘时所需的最少计算量。,南京邮电大学计算机学院2008年3月,7.3.3矩阵连乘算法,【程序73】矩阵连乘算法classMatrixChainpublic:MatrixChain(intmSize,int*q);intMChain();intLookupChain();voidTraceback();,南京邮电大学计算机学院2008年3月,private:voidTraceback(inti,intj);intLookupChain(inti,intj);int*p,*m,*s,n;,intMatrixChain:MChain()/求A0:n-1的最优解值for(inti=0;in;i+)mii=0;,南京邮电大学计算机学院2008年3月,for(intr=2;r=n;r+)for(inti=0;i=n-r;i+)intj=i+r-1;mij=mi+1j+pi*pi+1*pj+1;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;,南京邮电大学计算机学院2008年3月,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);cout0)returnmij;if(i=j)return0;intu=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;,南京邮电大学计算机学院2008年3月,intMatrixChain:LookupChain()returnLookupChain(0,n-1);,南京邮电大学计算机学院2008年3月,7.5最优二叉搜索树,南京邮电大学计算机学院2008年3月,7.5.1问题描述,设有元素集合a1,a2,an，其中，a1a2an，p(i)是在集合中成功查找ai的概率，1in，q(i)是待查元素x值满足aixai+1的概率,0in（假定a0=,an+1=+）。最优二叉搜索树问题是指设法构造一棵具有最小平均搜索时间的二叉搜索树。,南京邮电大学计算机学院2008年3月,7.5.2动态规划法求解,设c(0,n)是由元素值集合a1,an所构造的最优二叉搜索树的代价，则,南京邮电大学计算机学院2008年3月,一般地，c(i,j),ij是元素值集合ai+1,aj所构造的最优二叉搜索树的代价，设r(i,j)=k为该树的根，要求结点k满足,南京邮电大学计算机学院2008年3月,例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。,南京邮电大学计算机学院2008年3月,南京邮电大学计算机学院2008年3月,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;,南京邮电大学计算机学院2008年3月,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;,南京邮电大学计算机学院2008年3月,for(intm=2;m0，0i0，pi0，1iP1)xn1=1;elsexn1=0;回溯确定xn2,xn-3,x0;,南京邮电大学计算机学院2008年3月,7.6.5性能分析,在最坏情况下，算法的空间复杂度是O(2n)。在最坏情况下，算法的时间复杂度是O(2n)。,南京邮电大学计算机学院2008年3月,7.7流水作业调度,南京邮电大学计算机学院2008年3月,7.7.1问题描述,假定处理一个作业需要执行若干项不同类型的任务，每一类任务只能在某一台设备上执行。设一条流水线上有n个作业J=J0,J1,Jn1和m台设备P=P1,P2,Pm。每个作业需依次执行m个任务，其中第j个任务只能在第j台设备上执行，1jm。设第i个作业的第j项任务Tji所需时间为tji，1jm，0i2则不然）。,南京邮电大学计算机学院2008年3月,定理73流水作业调度问题具有最优子结构的性质。,南京邮电大学计算机学院2008年3月,如果在调度方案的作业排列中，作业i和j满足minbi,ajminbj,ai，则称作业i和j满足Johnson不等式。可以设计下列作业排列方法。这样做能得到最优调度方案(1)如果mina0,a1,an1,b0,b1,bn1是ai，则ai应是最优排列的第一个作业；(2)如果mina0,a1,an-1,b0,b1,bn1是bj，则bj应是最优排列的最后一个作业；(3)继续（1）和（2）的做法，直到完成所有作业的排列。,南京邮电大学计算机学院2008年3月,例711设n4，（a0,a1,a2,a3）=(3,4,8,10)（b0,b1,b2,b3）=(6,2,9,15)。设=(0),(1),(2),(3)是最优作业排列。先将任务按处理时间的非减次序排列成：（b1,a0,a1,b0,a2,b2,a3,b3）=(2,3,4,6,8,9,10,15)先选b1，将其加在最优作业排列的最后，故(3)=1再选a0，应加在最优作业排列的最前面，故(0)=0考察a1和b0，因作业1和0已调度，接着考察a2，应有(1)=2，再考察b2和a3，令(2)=3。所以最优解为：(0),(1),(2),(3)（0,2,3,1）。,南京邮电大学计算机学院2008年3月,7.7.3Johnso