第3章动态规划(上课)

单击此处编辑标题,单击此处编辑文本,第二级,第三级,第四级,第五级,*,算法设计与分析,2,第三章 动态规划,本章主要知识点：,(11),3.1,矩阵连乘问题,3.2,动态规划算法的基本要素,3.3,最长公共子序列问题,3.4,最大子段和,3.5,凸多边形的最优三角剖分,3.6,多边形游戏,3.7,图像压缩,3.8,电路布线,3.9,流水作业调度,3.10 0-1,背包问题,3.11,最有二叉搜索树,3.12,动态规划加速原理,3,4,5,6,7,8,9,10,11,引言,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n,=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,n/2,T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),T(n/4),T(n),Those who cannot remember the past are doomed to repeat it.,George Santayana,The life of Reason,Book I: Introduction and Reason,in Common Sense (1905),12,最优化原理与无后效性,一般来说，能够采用动态规划方法求解的问题必须满足,.,最优化原理,和,.,无后效性原则,。,1),动态规划的最优化原理,。作为整个过程的最优策略具有如下性质：无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。在例题,1,最短路径问题中，,A,到,E,的最优路径上的任一点到终点,E,的路径也必然是该点到终点,E,的一条最优路径，满足最优化原理。下面来讨论另外一个问题。,13,(2),动态规划的无后效性原则,。所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段,I,中的状态只能由阶段,I+1,中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。从图论的角度去考虑，如果把这个问题中的状态定义成图中的顶点，两个状态之间的转移定义为边，转移过程中的权值增量定义为边的权值，则构成一个有向无环加权图，因此，这个图可以进行“拓扑排序”，至少可以按他们拓扑排序的顺序去划分阶段。,14,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。,递归地定义最优值。,以自底向上的方式计算出最优值。,根据计算最优值时得到的信息，构造最优解。,15,3.1,矩阵连乘问题,给定,n,个矩阵,A,1,A,2,.,A,n,，其中,A,i,与,A,i+,1,是可乘的，,i,=1,2,.,n-,1,。考察这,n,个矩阵的连乘积,A,1,A,2,.A,n,。,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用,2,个矩阵相乘的标准算法计算出矩阵连乘积。,完全加括号的矩阵连乘积可递归地定义为：,单个矩阵是完全加括号的；,矩阵连乘积,A,是完全加括号的，则,A,可表示为,2,个完全加括号的矩阵连乘积,B,和,C,的乘积并加括号，即,A=(BC),。,设有四个矩阵,A,B,C,D,，它们的维数分别是：,A=5010,，,B=1040,，,C=4030,，,D=305,总共有五种完全加括号的方式：,(A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D),其数乘次数分别为：,16000, 10500, 36000, 87500, 34500,16,穷举搜索法,问题描述：给定,n,个矩阵,A,1,A,2,A,n,，其中,A,i,与,A,i+1,是可乘的，,i,=1,，,2,，,n-,1,。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：,对于,n,个矩阵的连乘积，设其不同的计算次序为,P(n),。,由于每种加括号方式都可以分解为两个子矩阵的加括号问题：,(,A,1,.,A,k,)(,A,k+,1,A,n,),可以得到关于,P(n),的递推式如下：,也就是说，,P,(,n,),是随,n,的增长成指数增长的。,17,动态规划法,1.,分析最优解的结构,下面我们考虑用求解。,预处理：,将矩阵连乘积,A,i,A,i+1,.A,j,简记为,A,i,:,j,，这里,i,j,。,考察计算,A,i,:,j,的最优计算次序。设这个计算次序在矩阵,A,k,和,A,k+,1,之间将矩阵链断开，,i,k,j,，则其相应完全加括号方式为（,A,i,A,i+1,. A,k,）（,A,k+,1,A,k+2,. A,j,）。,计算量：,A,i,:,k,的计算量加上,A,k,+1:,j,的计算量，再加上,A,i,:,k,和,A,k,+1:,j,相乘的计算量。,分析最优解的结构,特征,：计算,A,i,:,j,的最优次序所包含的计算矩阵子链,A,i,:,k,和,A,k,+1:,j,的次序也是最优的。,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为,最优子结构性质,。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,18,2.,建立递归关系,设计算,A,i,:,j,，,1,i,j,n,，所需要的最少数乘次数,m,i,j,，则原问题的最优值为,m,1,n,。,当,i,=,j,时，,A,i,:,j,=,A,i,，因此，,m,i,i,=0,，,i,=1,2,n,。,当,i,j,时，,m,i,j,=,m,i,k,+,m,k,+1,j,+,p,i-1,p,k,p,j,，这里,A,i,的维数为,p,i-1,p,i,。,可以递归地定义,m,i,j,为：,k,的位置只有,j,-,i,种可能。,19,3.,计算最优值,对于,1,i,j,n,不同的有序对,(,i,j,),对应于不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，,许多子问题被重复计算多次,。这也是该问题可用动态规划算法求解的又一显著特征。,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。,20,算法,MatrixChain,首先计算出,mii=0,i=1,2,3,.n,，然后，根据递归式，按矩阵链的方式依次计算,mii+1(,矩阵链长度为,2,，两个相邻矩阵相乘，,A1*A2,A2*A3,.An-1* An,）,mii+2(,矩阵链长度为,3,）；在计算,mij,时，只用到已计算出的,mik,和,mk+1j,21,算法描述,算法描述：,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 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;,算法复杂性：,T(n)=O(n,3,),28,关于动态规划算法和备忘录方法的,适用条件,综上所述，矩阵连乘积的最优计算次序问题可用自顶向下的备忘录方法或自底向上的动态规划算法在,O(n,3,),计算时间内求解。,这两个算法都利用了,子问题重叠性质,。总共有,(n,2,),个不同的子问题，对每个子问题两种算法都只解一次并记录答案。当再次遇到该子问题时，简单地取用已得到的答案，节省了计算量，提高了算法的效率。,适用条件,：一般来说，当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录方法好。此时，动态规划算法没有任何多余的计算，还可以利用其规则的表格存取方式来减少在动态规划算法中的计算时间和空间需求。当子问题空间中部分子问题可以不必求解时，易用备忘录方法则较为有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题。,29,3.3,最长公共子序列,概述：,若给定序列,X=x1,x2,xm,，则另一序列,Z=z1,z2,zk,，是,X,的,子序列,是指存在一个严格递增下标序列,i1,i2,ik,使得对于所有,j=1,2,k,有：,zj=xij,。例如，序列,Z=B,，,C,，,D,，,B,是序列,X=A,，,B,，,C,，,B,，,D,，,A,，,B,的子序列，相应的递增下标序列为,2,，,3,，,5,，,7,。,给定,2,个序列,X,和,Y,，当另一序列,Z,既是,X,的子序列又是,Y,的子序列时，称,Z,是序列,X,和,Y,的,公共子序列,。,给定,2,个序列,X=x1,x2,xm,和,Y=y1,y2,yn,，找出,X,和,Y,的,最长公共子序列,。,30,最长公共子序列的结构,设序列,X=x1,x2,xm,和,Y=y1,y2,yn,的最长公共子序列为,Z=z1,z2,zk,，则,若,xm=yn,，则,zk=xm=yn,，且,Zk-1,是,Xm-1,和,Yn-1,的最长公共子序列。,若,xmyn,且,zkxm,，则,Z,是,Xm-1,和,Y,的最长公共子序列。,若,xmyn,且,zkyn,，则,Z,是,X,和,Yn-1,的最长公共子序列。,由此可见，,2,个序列的最长公共子序列包含了这,2,个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有,最优子结构性质,。,31,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用,cij,记录序列和的最长公共子序列的长度。其中，,Xi=x1,x2,xi,；,Yj=y1,y2,yj,。当,i=0,或,j=0,时，空序列是,Xi,和,Yj,的最长公共子序列。故此时,Cij=0,。其它情况下，由最优子结构性质可建立递归关系如下：,32,计算最优值,由于在所考虑的子问题空间中，总共有,(mn),个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,void LCSLength(int m,，,int n,，,char *x,，,char *y,，,int *c,，,int *b),int i,，,j;,for (i = 1; i = m; i+) ci0 = 0;,for (i = 1; i = n; i+) c0i = 0;,for (i = 1; i = m; i+),for (j = 1; j =cij-1) ,cij=ci-1j; bij=2;,else cij=cij-1; bij=3; ,33,构造最长公共子序列,算法描述：,void LCS(int i,，,int j,，,char *x,，,int *b),if (i =0 | j=0) return;,if (bij= 1) LCS(i-1,，,j-1,，,x,，,b); coutxi; ,else if (bij= 2) LCS(i-1,，,j,，,x,，,b);,else LCS(i,，,j-1,，,x,，,b);,34,算法的改进,在算法,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),。,35,3.4,最大子段和,问题描述：,给定由,n,个整数（包含负整数）组成的序列,a,1,a,2,.,a,n,，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为,0,。,依此定义，所求的最优值为：,例如，当,(,a,1,a,2,a,3,a,4,a,5,a,6,)=(-2,11,-4,13,-5,-2),时，最大子段和为：,36,1.,一个简单算法,一个简单算法：,int MaxSum(int n, a, &besti, &bestj),int sum=0;,for(i=1;i=n;i+),for(j=1;j=n;j+),int thissum=0;,for(k=i;ksum),sum=thissum;,besti=i;,Bestj=j;,return sum;,算法有,3,重循环，复杂性为,O(,n,3,),。,由于有：,算法可作如下改进：,int MaxSum(int n, a, &besti, &bestj),int sum=0;,for(i=1;i=n;i+),int thissum=0;,for(j=1;jsum),sum=thissum;,besti=i;,bestj=j;,改进后的算法复杂性为,O(,n,2,),。,37,2.,分治方法求解,从问题的解的结构可以看出，它适合于用分治策略求解：,如果将所给的序列,a1:n,分为长度相等的两段,a1:n/1,和,an/2+1:n,，分别求出这两段的最大子段和，则,a1:n,的最大子段和有三种情形：,a1:n,的最大子段和与,a1:n/2,的最大子段和相同；,a1:n,的最大子段和与,an/2+1:n,的最大子段和相同；,a1:n,的最大子段和为下面的形式。,A,、,B,这两种情形可递归求得。对于情形,C,，容易看出，,an/2,与,an/2+1,在最优子序列中。因此，我们可以在,a1:n/2,和,an/2+1:n,中分别计算出如下的,s1,和,s2,。则,s1+s2,即为出现情形,C,使得最优值,。,从而设计出下面所示的分治算法。,int MaxSubSum(int a, int left, int right), int sum=0;,if (left=right)sum=aleft0?aleft:0;,elseint center=(left+right)/2;,int leftsum=MaxSubSum(a,left,center);,int rightsum=MaxSubSum(a,center+1,right);,int s1=0;lefts=0;,for (int i=center;i=left;i-), lefts+=ai;,if (leftss1) s1=lefts;,int s2=0;rights=0;,for (int i=center+1;is2) s2=rights;,sum=s1+s2;,if (sumleftsum) sum=leftsum;,if (sum,0,时,b,j,=,b,j-1,+,a,j,，否则,b,j,=,a,j,。由此可得计算,bj,的动态规划递归式,b,j,=max,b,j-1,+,a,j,，,a,j,，,1,j,n,。,据此，可设计出求最大子段和的动态规划算法如下：,int MaxSum(int n, int a),int sum=0; b=0;,for (i=1;i0) b+=ai; else b=ai;,if (bsum) sum=b;,return sum;,显然该算法的计算时间为,O,(,n,),。,39,4.,算法的推广,最大矩阵和问题，,略,最大,m,子段和问题，,略,40,3.5,凸多边形最优三角剖分,用多边形顶点的逆时针序列表示凸多边形，即,P=v0,v1,vn-1,表示具有,n,条边的凸多边形。,若,vi,与,vj,是多边形上不相邻的,2,个顶点，则线段,vivj,称为多边形的一条弦。弦将多边形分割成,2,个多边形,vi,vi+1,vj,和,vj,vj+1,vi,。,多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合,T,。,给定凸多边形,P,，以及定义在由多边形的边和弦组成的三角形上的权函数,w,。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小。,41,三角剖分的结构及其相关问题,一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积,(A1(A2A3)(A4(A5A6),所相应的语法树如图,(a),所示。,凸多边形,v0,v1,vn-1,的三角剖分也可以用语法树表示。例如，图,(b),中凸多边形的三角剖分可用图,(a),所示的语法树表示。,矩阵连乘积中的每个矩阵,Ai,对应于凸,(n+1),边形中的一条边,vi-1vi,。三角剖分中的一条弦,vivj,，,ij,，对应于矩阵连乘积,Ai+1:j,。,42,最优子结构性质,凸多边形的最优三角剖分问题有最优子结构性质。,事实上，若凸,(n+1),边形,P=v0,v1,vn-1,的最优三角剖分,T,包含三角形,v0vkvn,，,1kn-1,，则,T,的权为,3,个部分权的和：三角形,v0vkvn,的权，子多边形,v0,v1,vk,和,vk,vk+1,vn,的权之和。可以断言，由,T,所确定的这,2,个子多边形的三角剖分也是最优的。因为若有,v0,v1,vk,或,vk,vk+1,vn,的更小权的三角剖分将导致,T,不是最优三角剖分的矛盾。,43,最优三角剖分的递归结构,定义,tij,，,1ijn,为凸子多边形,vi-1,vi,vj,的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形,vi-1,vi,具有权值,0,。据此定义，要计算的凸,(n+1),边形,P,的最优权值为,t1n,。,tij,的值可以利用最优子结构性质递归地计算。当,j-i1,时，凸子多边形至少有,3,个顶点。由最优子结构性质，,tij,的值应为,tik,的值加上,tk+1j,的值，再加上三角形,vi-1vkvj,的权值，其中,ikj-1,。由于在计算时还不知道,k,的确切位置，而,k,的所有可能位置只有,j-i,个，因此可以在这,j-i,个位置中选出使,tij,值达到最小的位置。由此，,tij,可递归地定义为：,44,计算最优值,凸,n+1,边形,P=v,0,v,1,.,v,n,的最有三角剖分动态规划算法,MinWT,：,void MinWT(int n, type *t, int *s),for (int i=1;i=n;i+) tii=0;,for (int r=2; r=n; r+),for (i=1; i=n; i+),int j=i+r-1;,tij=tii+ti+1j+w(i-1,i,j);,sij=i;,for (int k=i+1;kj;k+),int u=tik+tk+1j+w(i-1,k,j);,if (utij)tij=u;sij=k;,复杂性：,T(n)=O(n,3,) S(n)=O(n,2,),45,构造最优解,思考：构造一个在,O(n),时间内的求最优解的算法。,46,3.6,多边形游戏,多边形游戏,是一个单人玩的游戏，开始时有一个由,n,个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“,+”,或“*”。所有边依次用整数从,1,到,n,编号。,游戏第,1,步，将一条边删除。,随后,n-1,步按以下方式操作：,(1),选择一条边,E,以及由,E,连接着的,2,个顶点,V1,和,V2,；,(2),用一个新的顶点取代边,E,以及由,E,连接着的,2,个顶点,V1,和,V2,。将由顶点,V1,和,V2,的整数值通过边,E,上的运算得到的结果赋予新顶点。,最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。,问题,:,对于给定的多边形，计算最高得分。,47,最优子结构性质,设所给的多边形的定点和便的顺时针序列为：,op1, v1, op2, v2, ., opn, vn,在所给多边形中，从顶点,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,换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。,48,递归求解,由前面的分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值。,设,mi,j,0,是链,p(i,j),合并的最小值，,mi,j,1,是最大值。,若最优合并在,opi+s,处将,p(i,j),分为,2,个长度小于,j,的子链,p(i,s),和,p(i+s,j-s),，且从顶点,i,开始的长度小于,j,的子链的最大值和最小值均已计算出。为叙述方便，记,a=mi,s,0,，,b=mi,s,1,，,c=mi+s,j-s,0,，,d=mi+s,j-s,0,(1),当,opi+s=+,时，,mi,j,0=a+c,，,mi,j,1=b+d,(2),当,opi+s=*,时，,mi,j,0=minac,ad,bc,bd,，,mi,j,1=maxac,ad,bc,bd,综合,(1),和,(2),，将,p(i,j),在,opi+s,处断开的最大值为,maxf(i,j,s),，最小值为,minf(i,j,s),，则,由于最优断开位置,s,有,1sj-1,的,j-1,种情况，由此可知,初始边界值显然为,mi,1,0=vi, mi,1,1=vi, 1in,。,49,算法描述,算法描述：,P,63,算法复杂性：,O(n,3,),50,3.7,图像压缩,图象的变位压缩存储格式将所给的象素点序列,p1,p2,pn,0pi255,分割成,m,个连续段,S1,S2,Sm,。第,i,个象素段,Si,中,(1im),，有,li,个象素,且该段中每个象素都只用,bi,位表示。设则第,i,个象素段,Si,为,设 ，则,hibi8,。因此需要用,3,位表示,bi,如果限制,1li255,，则需要用,8,位表示,li,。因此，第,i,个象素段所需的存储空间为,li*bi+11,位。按此格式存储象素序列,p1,p2,pn,，需要位的存储空间。,图象压缩问题要求确定象素序列,p1,p2,pn,的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过,256,位。,51,最优子结构性质,设,li,，,bi,，是,p1,p2,pn,的最优分段。显而易见，,l1,，,b1,是,p1,pl1,的最优分段，且,li,，,bi,，是,pl1+1,pn,的最优分段。即图象压缩问题满足最优子结构性质。,设,si,，,1in,，是象素序列,p1,pn,的最优分段所需的存储位数。由最优子结构性质易知：,其中,算法复杂度分析：由于算法,compress,中对,k,的循环次数不超这,256,，故对每一个确定的,i,，可在时间,O(1),内完成的计算。因此整个算法所需的计算时间为,O(n),。,52,递归计算最优值与构造最优解,递归计算最优值算法描述：,P,64,65,构造最优解算法描述：,P,65,66,Compress,：,S(n)=O(n),，,T(n)=O(n),53,3.8,电路布线,在一块电路板的上、下,2,端分别有,n,个接线柱。根据电路设计，要求用导线,(i,(i),将上端接线柱与下端接线柱相连，如图所示。其中,(i),是,1,2,n,的一个排列。导线,(i,(i),称为该电路板上的第,i,条连线。对于任何,1i(j),。,电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集,Nets=(i,(i),1in,的最大不相交子集。,=,8,，,7,，,4,，,2,，,5,，,1,，,9,，,3,，,10,，,6,54,最优子结构性质,记,N(i,j)=t|(t,(t)Nets,ti,(t)j,，,N(i,j),的最大不相交子集为,MNS(i,j),，,Size(i,j)=|MNS(i,j)|,。,(1),当,i=1,时，,(2),当,i1,时，,j(i),。此时，,(i,(i)N(i,j),。故在这种情况下，,N(i,j)=N(i-1,j),，从而,Size(i,j)=Size(i-1,j),。,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),的最大不相交子集。若,(i,(i)N(i,j),，则对任意,(t,(t) MNS(i,j),有,ti,。从而,MNS(i,j)N(i-1,j),。因此，,Size(i,j)Size(i-1,j),。另一方面,MNS(i-1,j)N(i,j),，故又有,Size(i,j)Size(i-1,j),，从而,Size(i,j)=Size(i-1,j),。,综上可知，电路布线问题满足最优子结构性质。,55,递归计算最优值,算法描述：详见,P6768,，计算最优值，构造最优解。,算法复杂性：,MNS,算法：,T(n)=O(n,2,),，,S(n)=(n,2,),Traceback,算法：,T(n)=O(n),思考：求解目标为最少层数时的算法问题。,void MNS(C, n, *size),for (j=0; jC1; j+) size1j=0;,for (j=C1; j=n; j+) size1j=0;,for (i=2; in; i+), for (j=0; jCi; j+) sizeij=sizei-1j;,for (j=Cj; j1; i-),if (sizeij!=sizei-1jNetm+=i; j=Ci-1;,if (j=C1) Netm+=1;,56,3.9,流水作业问题,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,。,S,是,N,的作业子集。在一般情况下，机器,M1,开始加工,S,中作业时，机器,M2,还在加工其他作业，要等时间,t,后才可利用。将这种情况下完成,S,中作业所需的最短时间记为,T(S,t),。流水作业调度问题的最优值为,T(N,0),。,57,最优子结构性质,设,是所给,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),),。这就证明了流水作业调度问题具有最优子结构的性质。,由流水作业调度问题的最优子结构性质可知，,思考,：直接利用该递归关系构造动态规划算法。,58,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,不等式,。,59,流水作业调度的,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,法则的调度均为最优调度。,60,算法及其复杂性,流水作业调度问题的,Johnson,算法：,令,N,1,=i|a,i,2n,时，算法需要,(n2n),计算时间。,64,算法改进,由,m(i,j),的递归式容易证明，在一般情况下，对每一个确定的,i(1in),，函数,m(i,j),是关于变量,j,的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数,m(i,j),由其全部跳跃点惟一确定。如图所示。,对每一个确定的,i(1in),，用一个表,pi,存储函数,m(i,，,j),的全部跳跃点。表,pi,可依计算,m(i,，,j),的递归式递归地由表,pi+1,计算，初始时,pn+1=(0,，,0),。,示例：,n=3,，,c=6,，,w=4,3,2,，,v=5,2,1,。,x,(0,0),m(4,x),x,(2,1),m(4,x-2)+1,x,(0,0),(2,1),m(3,x),(3,2),x,m(3,x-3)+2,(5,3),x,(0,0),(2,1),m(2,x),(3,2),(5,3),x,m(2,x-4)+5,(4,5),(6,6),(7,7),(9,8),x,(0, 0),(2, 1),m(1,x),(3,2),(5,3),(4,5),(6,6),(7,7),(9,8),x,(0,0),(2,1),m(3,x),x,(0,0),(2,1),m(2,x),(3,2),(5,3),66,关于,m(i,j),函数,m(i,j),是由函数,m(i+1,j),与函数,m(i+1,j-wi)+vi,作,max,运算得到的。因此，函数,m(i,j),的全部跳跃点包含于函数,m(i+1,，,j),的跳跃点集,pi+1,与函数,m(i+1,，,j-wi)+vi,的跳跃点集,qi+1,的并集中。易知，,(s,t)qi+1,当且仅当,wisc,且,(s-wi,t-vi)pi+1,。因此，容易由,pi+1,确定跳跃点集,qi+1,如下,qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1,另一方面，设,(a,，,b),和,(c,，,d),是,pi+1qi+1,中的,2,个跳跃点，则当,ca,且,db,时，,(c,，,d),受控于,(a,，,b),，从而,(c,，,d),不是,pi,中的跳跃点。除受控跳跃点外，,pi+1qi+1,中的其他跳跃点均为,pi,中的跳跃点。,由此可见，在递归地由表,pi+1,计算表,pi,时，可先由,pi+1,计算出,qi+1,，然后合并表,pi+1,和表,qi+1,，并清除其中的受控跳跃点得到表,pi,。,67,另一个例子,实例：,n=5,，,c=10,，,w=2,2,6,5,4,，,v=6,3,5,4,6,。,初始时,p6=(0,0),，,(w5,v5)=(4,6),。,因此，,q6=p6,(w5,v5)=(4,6),。,p5=(0,0),(4,6),。,q5=p5,(w4,v4)=(5,4),(9,10),。从跳跃点集,p5,与,q5,的并集,p5,q5=(0,0),(4,6),(5,4),(9,10),中看到跳跃点,(5,4),受控于跳跃点,(4,6),。将受控跳跃点,(5,4),清除后，得到,p4=(0,0),(4,6),(9,10),q4=p4,(6,，,5)=(6,，,5),，,(10,，,11),p3=(0,，,0),，,(4,，,6),，,(9,，,10),，,(10,，,11),q3=p3,(2,，,3)=(2,，,3),，,(6,，,9),p2=(0,，,0),，,(2,，,3),，,(4,，,6),，,(6,，,9),，,(9,，,10),，,(10,，,11),q2=p2,(2,，,6)=(2,，,6),，,(4,，,9),，,(6,，,12),，,(8,，,15),p1=(0,，,0),，,(2,，,6),，,(4,，,9),，,(6,，,12),，,(8,，,15),p1,的最后的那个跳跃点,(8,15),给出所求的最优值为,m(1,c)=15,。,68,算法复杂度分析,算法描述：,P7475,上述算法的主要计算量在于计算跳跃点集,pi(1in),。由于,qi+1=pi+1,(wi,，,vi),，故计算,qi+1,需要,O(|pi+1|),计算时间。合并,pi+1,和,qi+1,并清除受控跳跃点也需要,O(|pi+1|),计算时间。从跳跃点集,pi,的定义可以看出，,pi,中的跳跃点相应于,xi,xn,的,0/1,赋值。因此，,pi,中跳跃点个数不超过,2,n-i+1,。由此可见，算法计算跳跃点集,pi,所花费的计算时间为,从而，改进后算法的计算时间复杂性为,O(2n),。当所给物品的重量,w,i,(1in),是整数时，,|pi|c+1,，,(1in),。在这种情况下，改进后算法的计算时间复杂性为,O(minnc,2,n,),。,69,3.11,最优二叉搜索树,什么是二叉搜索树？,若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；,若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；,它的左、右子树也分别为二叉排序树,在随机的情况下，二叉查找树的平均查找长度和,logn,是等数量级的。,45,12,53,3,37,24,100,61,90,78,70,基本概念,具体地，设,S=x,1,x,2,.,x,n,是一个有序集，且,x,1,x,2,.x,n,。表示有序集,S,的二叉搜索树利用二叉树的结点来存储有序集中的元素。它具有下述性质：存储于每个结点中的元素,x,大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。二叉搜索树的叶结点是形如,(x,i,，,x,i+1,),的开区间。在表示,S,的二叉搜索树中搜索一个元素,x,，返回的结果有两种情形：,在二叉搜索树的内结点中找到,x=x,i,。,在二叉搜索树的叶结点中确定,x(x,i,，,x,i+1,),。,设第一种情形中找到元素,x=x,i,的概率为,b,i,；在第二种情形中确定,x(x,i,，,x,i+1,),的概率为,a,i,。并约定,x,0,=-,，,x,n+1,=+,。显然有,(a,0,b,1,a,1,.,b,n,a,n,),称为集合,S,的存取概率分布。,在表示,S,的二叉搜索树,T,中，设存储元素,x,i,的结点深度为,c,i,；存储叶结点,(x,j,x,j+1,),的结点深度为,d,j,，则,表示在二叉搜索树,T,中作一次搜索所需要的平均比较次数。,P,又称为二叉搜索树,T,的平均路长。在一般情况下，不同的二叉树的平均路长时不相同的。,71,二叉查找树的期望耗费示例,72,最优二叉搜索树,最优二叉搜索树问题是对于有序集,S,及