第3章动态规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,syzhanglily,第,3,章 动态规划,1,要点,理解动态规划算法的概念,掌握动态规划算法的基本要素,掌握设计动态规划算法的设计策略,2,本章主要内容,矩阵连乘问题 掌握,动态规划算法的基本要素 熟练掌握,流水作业调度 了解,0-1,背包问题 熟练掌握,最优二叉搜索树 熟练掌握,3,1,n,=0,F,(,n,)=1,n,=1,F,(,n,-1)+,F,(,n,-2),n,1,例,3,1,Fibonacci,数列问题,F(4),F(3),F(2),F(2),F(1),F(1),F(0),动态规划算法,F1),F(0),4,动态规划算法,将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而,避免计算重复的子问题,，再由子问题的解得到原问题的解。,算法思想,5,动态规划与分治的联系区别,都是分解成子问题，由子问题的解得到原问题的解。,分治中子问题相互独立，而动态规划中子问题互相有联系，且存在重复计算，即存在,重叠子问题,。,6,动态规划算法设计步骤,（,1,）找出最优解的性质，刻画其结构特征,（,2,）递归地定义最优值,（,3,）以自底向上的方式计算出最优值,（,4,）根据计算最优值时得到的信息，构造一个最优解,7,3.1,矩阵连乘问题,给定,n,个矩阵,A,1,A,2,A,n,其中,A,i,是一个,r,i-1,r,i,矩阵,(1,i,n,),，即,A,i,A,i+,1,是可乘的，求出,n,个矩阵相乘的最优计算次序，使得计算量最小。,问题提出,设三个矩阵,A,1,A,2,A,3,大小分别为,10100,，,1005,，,550,，考虑,(,A,1,(,A,2,A,3,),(,A,1,A,2,),A,3,的结果与相乘的次数。,8,矩阵相乘满足结合律，连乘积可以有许多不同的次序。这种次序可以用加括号的方式确定。,考查两个矩阵相乘的情形：,C=AB,。如果矩阵,A,，,B,分别是,pr,和,rq,矩阵，则它们的乘积,C,将是,pq,矩阵，其,(i,j),元素为,则共需要,pqr,次数乘。,矩阵连乘问题,A,1,A,2,A,3,大小分别为,10100,，,1005,，,550,，,(,A,1,(,A,2,A,3,),(,A,1,A,2,),A,3,),的结果相同，都是,1050,的矩阵，计算量分别为,75000,，,7500,9,完全加括号的矩阵连乘积,单个矩阵是完全加括号的；,矩阵连乘积,A,是完全加括号的，则,A,可表示为,2,个完全加括号的矩阵连乘积,B,和,C,的乘积并加括号，即,A=(BC),。,考虑,n,=4,的情况，此时矩阵运算,A,*,B,*,C,*,D,可按以下方式（顺序）计算,(,完全加括号方式,),：,A,*(,B,*,C,)*,D,),，A,*(,B,*(,C,*,D,),，,(,A,*,B,)*(,C,*,D,),，,(,A,*(,B,*,C,)*,D,矩阵连乘问题,10,两个矩阵的乘法,void,MatrixMultiply(int,*a,int,*b,int,*c,int,ra,int,ca,int,rb,int,cb,),if(ca,!=,rb,)error(“,矩阵不可乘”,),；,for(int,i=0;i,ra,;i+),for(int,j=0;j,cb,;j+),int,sum=ai0*b0j;,for(int,k=1;k ca;k+),sum+=,aik,*,bkj,;,cij,=sum;,矩阵连乘问题,11,穷举搜索法,对于,n,个矩阵的连乘积，设有,p(n,),个计算次序。我们可以在第,k,个和第,k,1,个矩阵之间将原矩阵划分为两个子矩阵序列，然后分别对这两个矩阵子序列完全加括号，最后对所得的结果加括号，则,其中,P,(,n,)=,C,(,n,-1),，,矩阵连乘问题,12,1.,分析最优解的结构,设,A i:j,为矩阵连乘积,A,i,A,i+1,A,j,计算,A1:n,的最优次序，设该次序在矩阵,A,k,和,A,k,1,之间断开，,1,kn,则完全加括号方式为,(A,1,A,k,)(A,k+1,A,n,),总计算量为,A 1:k,的加上,A k+1:n,的计算量，再加上,A 1:k,和,A k+1:n,相乘的计算量。,矩阵连乘问题,13,最优子结构特征,计算,A1:n,的一个最优次序所包含的计算矩阵子链,A1:k,和,Ak+1:n,的次序也是最优的,矩阵连乘积计算次序问题的最优解包含着其子问题的最优解，也就是最优子结构性质。,矩阵连乘问题,考虑,A1:k,和,Ak+1:n,相乘所需的计算量，,A i:k,和,A k+1:j,相乘呢,A1:k,的结果为,r,0,*,r,k,的矩阵，,Ak+1:n,的结果为,r,k,*,r,n,的矩阵，则它们相乘的计算量为,p,0,*,p,k,*,p,n,14,2.,建立递归关系,设计算,A i:j,所需的最少次数为,mij,原问题的最优解为,m1n,。,当,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,k,i,i+1,j-1,矩阵连乘问题,15,采用递归方法计算,int,RecurMatrixChain,(,int,i,int,j,int,p),if,(),return 0;,int,u=,RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j,p),+pi-1*,pi,*,pj,;,sij,=i;,for(int,k=i+1;kj;k+),int,t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j,p),+pi-1*,pi,*,pj,;,if(t1,时，,可用数学归纳法证明,矩阵连乘问题,18,对于,1i j n,不同的有序对,(,i,j,),对应于不同的子问题,mij,，因此，不同的子问题的个数最多只有,用动态规划解此问题时，在计算过程中，保存已解决的子问题答案，每个子问题只计算一次，而在后面用到时简单地查一下，从而避免了大量的重复计算,矩阵连乘问题,19,2,4,2,2,3,4,1,2,3,3,4,4,1,1,1,4,1,3,2,3,矩阵连乘问题,3.,计算最优值,20,3.,计算最优值,对于,m1n,可以按照下面顺序构成,m12 m23 m34 m45 mn-1n,m13 m24 m35 mn-2n,m14 m25 m36 mn-3n,m1n-1 m2n,m1n,矩阵连乘问题,计算,m i j,时，只用到已计算出的,m i k,和,m k+1 j,21,3.,计算最优值,置所有只有一个矩阵的矩阵链计算量为,0,，即,mii,=0,，,i=1,2,n,。,通过上一步的结果可以得到所有矩阵链长度为,2,的子问题的最优计算量。,通过上两步的结果可以得到所有矩阵链长度为,3,的子问题的最优计算量,矩阵连乘问题,计算,m i j,时，只用到已计算出的,m i k,和,m k+1 j,22,A,1,A,2,A,3,A,4,A,5,A,6,3035 3515 155 510 1020 2025,例,3,2,设要计算矩阵连乘积,A,1,A,2,A,3,A,4,A,5,A,6,其中各矩阵的维数分别为,1 2 3 4 5 6,0,0,0,0,0,0,15750,2625,750,1000,5000,m11+m23+p0p1p3=7875,m13=min,m12+m33+p0p2p3=15750,9375,11875,15125,4375,7125,10500,2500,5375,3500,7875,i,j,23,3.,计算最优值,void,MatrixChain(int,p,int,n,int,*m,int,*s),forint,i=1;i=n;i+),mii,=,;/,单个矩阵的计算量,for(,int,r=2;r=n;,r+)/r,为每次循环矩阵链的长度,for(,int,i=1;i=,;i+),int,j=i+r-1;,mij,=mi+1j+pi-1*,pi,*,pj,;,sij,=i;,for(,int,k=i+1;kj;k+),int,t=,mik,+mk+1j+,;,if(t,mij,),mij,=t;,sij,=k;,矩阵连乘问题,0,n r+1,取第一个可取位置，即断开位置为,i,循环取,k,的可取位置,pi-1*,pk,*,pj,24,计算过程,先计算出,mii,=0,i=1,2,n,然后依次计算,mii+1,i=1,2,n-1(,矩阵长度为,2),；,mii+2,i=1,2,n-2,(,矩阵链长度为,3),；,.,每次计算只用到已计算出的,mik,和,mk+1j,计算顺序,m11,m22,m33.,mnn,m12,m23,m34mn-1n,m13,m24,m35mn-2n,m1n-1,m2n,m1n,矩阵连乘问题,25,算法复杂度,算法,MatrixChain,的主要计算量取决于程序中对,r,i,和,k,的三重循环，,循环体内的计算量为,O(1),，三重循环的总次数是,O(n,3,),，所以，算法的计算时间上界为,O(n,3,),。,26,4.,构造最优解,上述算法只是明确给出了矩阵最优连乘次序所用的数乘次数,m1n,，并未明确给出最优连乘次序，即完全加括号方法。但是以,sij,为元素的,2,维数组却给出了足够的信息。事实上，,sij,=k,说明，计算连乘积,Ai:j,的最佳方式应该在矩阵,Ak,和,Ak+1,之间断开，即最优加括号方式为,(Ai:k)(Ak+1:j),。,27,1 2 3 4 5 6,0 1 1 3 3 3,0 2 3 3 3,0 3 3 3,0 4 5,0 5,0,考虑计算,A16,时的顺序,S16,(A,1,A,3,)(A,4,A,6,),S13,A,1,(A,2,A,3,),S46,(A,4,A,5,),A,6,S11=0,S23=0,A1,(A,2,)(A,3,),S22=S33=0,S66=0,S45=0,(A,4,)(A,5,),A,6,S44=S55=0,28,根据最优值算法构造最优解,Void,Traceback(int,i,int,j,int,*s),if(i=j)return;,Traceback(i,sij,s);,Traceback(sij+1,j,s);,cout,“Multiply A”i “,”,sij,;,cout,“and A”(,sij,+1)“,”j;,endl,;,调用,Traceback(1,n,s),即可得到,A1:n,29,作业,1,当,A,1,A,2,A,3,A,4,A,5,分别为,2025,，,2510,，,105,，,515,，,1520,的矩阵时，填写相应的,mij,和,sij,，并给出最优计算次序。,2 p82,，,3-6,30,3.2,动态规划算法的基本要素,1,最优子结构性质,2,重叠子问题性质,31,1.,最优子结构,当问题的最优解包含了其子问题的最优解时，称该问题具有,最优子结构性质,。,分析最优子结构性质时，一般假设由问题的最优解导出的子问题不是最优的，然后再设法说明在这个假设下可以构造出一个比原问题更优解更好的解，从而导出矛盾。,动态规划算法的基本要素,32,2.,重叠子问题,在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法对每个问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法通常只需要多项式时间。,动态规划算法的基本要素,33,3.,备忘录方法,用一个表格来保存已解决的子问题的答案，用的时候查表即可。,采用的递归方式是,自顶向下,，动态规划是,自低向上,控制结构与直接递归相同，区别在于备忘录方式为每个解过的子问题建立备忘录。,初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问题的解答即可。,动态规划算法的基本要素,34,备忘录方法解矩阵乘,int,MemoizedMatrixChain(int,n,int,*,m,int,*s),for(int,i=1;i=,n;i,+),for(int,j=,i;j,0)return,mij,;,if(i,=j)return 0;,int,u=LookupChain(i,i)+LookupChain(i+1,j),+pi-1*,pk,*,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,0,，其价值为,v,i,0,，背包的容量为,c,。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？,要求一组数,i,(,i,=0,或,，,i,=0,表示,物体,不放入背包，,i,1,表示把,物体,放入背包），,使得,v,i,x,i,最大，即将尽量多的价值装入背包。,1,i,n,40,考虑有三种物品,它们的,重量为,(w,1,w,2,w,3,)=(2,3,4),价值为,(v,1,v,2,v,3,)=(1,2,5),当背包容量为,c=6,时，如何装背包总价值最大？,x,1,x,2,x,3,=1,0,1,v,1,*x,1,+v,2,*x,2,+v,3,*x,3,=6,x,1,x,2,x,3,=0,0,0 1,0,0 0,1,0 0,0,1 1,1,0 1,0,1,41,给定,c,0,w,i,0,v,i,0,1,i,n,要求找出一个,n,元向量,(,x,1,x,2,x,n,),x,i,0,1,1,i,n,使得 ，,而且 达到最大，用,knap(1,n,c),表示。,约束条件：背包容量限制,v,i,x,i,效益值最大化,42,1.,最优子结构性质,证明,0/1,背包问题具有最优子结构性质,即若背包容量为,c,时，,(,y,1,y,2,y,n,),为待选物品为,1,到,n,时,knap(1,n,c),的最优解，则,(y,2,y,n,),将是物品,1,作出选择后的子问题,的最优解,当第一个物品做出决策后，有两种状态,y,1,=0,，则背包容量没有影响，,(y,2,y,n,),是,的最优解,y,1,=1,，则背包减少,w,1,，价值增长,v,1,，,(y,2,y,n,),是,的最优解,x,1,v,i,x,i,knap(2,n,c-w1*y1),knap(2,n,c,),knap(2,n,c,w1),43,证明：,因为，若,(z,2,z,n,),是下述子问题的一个最优解，而,(y,2,y,n,）不是它的最优解,这说明,(y,1,z,2,z,n,),是所给问题的一个更优解，,从而,(y,1,y,2,y,n,),不是原问题的最优解，矛盾,x,1,v,i,x,i,则,因此,44,2.,递归关系,设背包问题的子问题的最优值为,m(i,j),即,mi,j),是背包容量为,j,，可选择物品为,i,，,i,1,，,n,时的最优值。,当选择第,i,个物品时，,。,如果不选择第,i,个物品，则,。,由问题的最优子结构性质，我们可以建立计算,m(i,j),的递归式如下：,m(i,j)=,m(i,+1,j-,wi,)+vi,m(i,j)=,m(i,+1,j),45,例,:,四个物品，背包容积为,5,，,w4=2,1,3,2,，,v4=12,10,20,15,，求最大价值,m1c,及选取的物品编号,4,3,2,1,4,3,2,1,0,5,0,0,0,0,0,10,15,15,15,15,15,15,20,20,35,35,30,25,37,i,j,x,4,X,3,X,2,X,1,1,m15m25,所以物品,1,被选,c w1=3,查看,m23m33,1,j w2=2,查看,m32=m42,0,查看,m420,1,46,3.,算法描述,template,void,Knapsack(Type,v,int,w,int,c,int,n,Type*,m,),int,jMax,=min(,wn,-1,c);,for(,int,j=0;j=,jMax,;j+)/,出口,m n j =,;,for(,int,j=,wn,;j 1;i-),jMax,=min(w i -1,c);,for(int,j=0;j=,jMax,;j+),m i j =,;,for(int,j=w i;j=w1),m1c=max(m1c,m2c-w1+v1);,0,vn,m i+1 j,m 2 c,初始化,mnj,只剩下第一个物品时，如果剩余背包容积大于,w1,时，要进行选择,47,m15 m25,4,3,2,1,4,3,2,1,0,5,0,0,0,0,0,10,10,15,15,15,15,15,20,20,35,35,30,25,37,i,j,构造最优解,x1=1 c=5-w1=3,m23 m33,x2=1 c=3-w2=2,m32=m42,x3=0 c=2,m42 0,x4=1,48,构造最优解,Template,Void,Traceback(Type,*,m,int,w,int,c,int,n,int,x),for(int,i=1;i2,n,时，算法需要,(n2,n,),n=3,(w1,w2,w3)=(2,3,4),v1,v2,v3=(1,2,5),c=5,50,设有,n,种不同面值的硬币，各硬币的面值存于数组,T1:n,中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数不限。,(1),当只用硬币面值,T1,T2,Ti,时，可找出钱数,j,的最少硬币个数记为,C(i,j),。若只用这些硬币面值，找不出钱数,j,时，记,C(i,j)=,。给出,C(i,j),的递归表达式及初始条件。,1i n,1j L,。,(2),设计一个动态规划算法，对,1j L,，计算出所有的,C(n,j,),。算法中只允许使用一个长度为,L,的数组。用,L,和,n,作为变量来表示算法的计算时间复杂性。,作业：教材,P82:3-4,中,(1)(2),51,3.5,最优二叉搜索树,Optimal Binary Search Trees,52,二叉搜索树,最优二叉搜索树,最优二叉搜索树问题描述,最优子结构证明,递归计算最优值,算法,53,是一棵空树或者满足以下的性质：,每个结点作为搜索对象，它的关键字是,互不相同,的。,对于树上的所有结点，如果它有,左子树,，那么左子树上所有结点的关键字都,小于,该结点的关键字。,对于树上的所有结点，如果它有,右子树,，那么右子树上所有结点的关键字都,大于,该结点的关键字,1,、二叉搜索树定义,54,xal,wan,wil,wen,wim,wul,zol,yo,zom,xul,yum,xem,yon,zi,搜索过程：从根结点开始，如果根为空，则搜索不成功；否则使用待搜索值与根结点比较，如果待搜索值等于根结点关键字，则搜索成功返回，如果小于根结点，则向左子树搜索；如果大于根结点，则向右子树搜索。,1,、二叉搜索树,55,构造不同的二叉搜索树,就有不同的性能特征。,二叉搜索树,a,在,最坏情况,下找一个标识符需要,4,次比较,，而,b,表示的二分检索树最坏情况下只需,3,次比较,。,假设只,作成功的检索,并且,检索每个标识符的概率相同,，则两棵二分检索树在平均情况下各需要,12/5,和,11/5,次比较。,if,for,while,loop,repeat,if,while,loop,repeat,for,a,b,1,、二叉搜索树,56,2,、最优二叉搜索树,存在的两个问题,1,在实际中也会遇到,不成功,检索的情况。,2,在实际中，不同标识符会有,不同,的检索概率。,对给定的标识符集合，希望给出构造二分搜索树的方法，使得所构造的二分搜索树具有,最优的性能,。,最优二叉搜索树,57,扩充二叉树：当二叉树里出现空的子树时，就增加新的、特殊的结点,空树叶,。对于原来二叉树里度数为,1,的分支结点，在它下面增加一个空树叶；对于原来二叉树的树叶，在它下面增加两个空树叶。,扩充二叉树是,满二叉树,，新增加的空树叶（以下称外部结点）的个数等于原来二叉树的结点（以下称内部结点）个数加,1,在实际中也会遇到,不成功,检索的情况。,最优二叉搜索树,58,xal,wan,wil,wen,wim,wul,zol,yo,zom,xul,yum,xem,yon,zi,A,A,代表其值处于,wim,和,wul,之间的可能关键码集合,最优二叉搜索树,59,设,S,=,x,1,x,2,x,n,是一个有序集合，且,x,1,x,2,x,n,表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素，而且具有性质：,存储于每个顶点中的元素x,大于其左子树中任一个顶点中存储的元素，小于其右子树中任意顶点中存储的元素。二叉树中的叶顶点是形如,(,x,i,x,i+1,),的开区间。,在二叉搜索树中搜索一个元素,x,(1),在二叉树的内部顶点处找到：,x,=,x,i,(2),在二叉树的叶顶点中确定：,x,(,x,i,x,i,+1,),最优二叉搜索树,60,在实际中，不同标识符会有,不同,的检索概率。,设,Pi,是对,ai,检索的概率，,设,qi,是对满足,ai,Xai+1,0,i,n,的标识符,X,检索的概率，,(,假定,a,0,=-,且,a,n+1,=,),。,a,1,Q(0),E,0,P(1),a,2,E,1,Q(1),P(2)a,i,P(i),a,i+1,E,i,Q(i),P(i+1),a,n,P(n),E,n,Q(n),最优二叉搜索树,61,最优二叉搜索树,利用动态规划构造对标识符集合,a1,a2,an,的,最优二叉搜索树,算法,包括,成功检索,和,不成功检索,）。,最优二叉搜索树,62,例 标识符集,1,2,3,do,if,stop,可能的二分 检索树为,(a),2,3,1,3,2,1,3,2,1,(b),(c),3,1,2,(d),3,1,2,(e),设每个内、外结点检索的概率相同：,p,i,=,q,i,=1/7,求每棵树的平均比较次数（成本）。,若,P,1,=0.5,P,2,=0.1,P,3,=0.05,q,0,=0.15,q,1,=0.1,q,2,=0.05,q,3,=0.05,求每棵树的平均比较次数（成本）。,63,例：,P,1,=0.5,P,2,=0.1,P,3,=0.05,q,0,=0.15,q,1,=0.1,q,2,=0.05,q,3,=0.05,1,2,3,q,0,q,1,q,2,q,3,1,2,3,q,0,q,1,q,2,q,3,q,0,1,2,3,q,1,q,2,q,3,1,2,3,q,0,q,1,q,2,q,3,1,2,3,q,0,q,1,q,2,q,3,考虑平均搜索次数，也叫做平均路长,P,a,(,n,)=1,p,1,+2,p,2,+3,p,3,+1,q,0,+2q,1,+3(,q,2,+,q,3,),=1 0.5+2 0.1+3 0.05+10.05+20.1+3(0.05+0.05),=1.5,最优二叉搜索树,64,分析,对于图的内结点而言，第,0,层需要比较操作次数为,1,，第,1,层需要比较,2,次，第,2,层需要,3,次,P,b,(,n,)=1,p,1,+2,p,3,+3,p,2,+1,q,0,+3(,q,2,+,q,3,),=1 0.5+2 0.05+3 0.1,+10.15,+20.05+3(0.05,+0.05,),=1.6,P,c,(,n,)=1,p,2,+2 (,p,1,+,p,3,),+2(,q,0,+,q,1,+,q,2,+,q,3,),1 0.1+2 (0.5+0.05)+2(0.15+0.1+0.05+0.05),=1.9,P,d,(,n,)=1,p,3,+2,p,1,+3,p,2,+1,q,3,+2,q,0,+3 (,q,1,+,q,2,),=1 0.05+2 0.5+3 0.1+10.05+2 0.15+3 (0.1+0.05),=2.15,P,d,(,n,)=1,p,3,+2,p,1,+3,p,2,+1,q,3,+2,q,0,+3 (,q,1,+,q,2,),=1 0.05+2 0.5+3 0.1+10.05+2 0.15+3 (0.1+0.05),=2.15,最优二叉搜索树,65,找到元素,x,=,x,i,的概率为,b,i,；确定,x,(,x,i,x,i,+1,),的概率为,a,i,。,其中约定,x,0,=,x,n+1,=+,有,最优二叉搜索树,66,在一个表示,S,的二叉树,T,中，设存储元素,x,i,的结点深度为,c,i,；叶结点（,x,j,，,x,j,1,）的结点深度为,d,j,表示在二叉搜索树,T,中作一次搜索所需的平均比较次数。,P,又称为二叉搜索树,T,的平均路长，在一般情况下，不同的二叉搜索树的平均路长是不同的。,最优二叉搜索树,67,3,、最优二叉搜索树问题,对于有序集,S,及其存取概率分布,（,a,0,b,1,a,1,b,n,a,n,），在所有表示有序集,S,的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。,结点在二叉搜索树中的层次越深，需要比较的次数就越多，因此要构造一棵最小二叉树，一般尽量把搜索概率较高的结点放在较高的层次。,最优二叉搜索树问题,68,4,、最优子结构性质,假设选择,k,为,树根，则,1,2,k-1,和,a,0,a,1,a,k-1,都将,位于左子树,L,上，其余结点,(k+1,n,和,a,k,a,k+1,a,n,),位于右子树,R,上。,k,L,R,1,2,k-1,a,0,a,1,a,k-1,k+1,n,a,k,a,k+1,a,n,最优子结构性质,69,51,14,72,06,33,53,97,64,25,43,13,99,84,最优子结构性质,70,51,14,72,06,33,53,97,64,25,43,13,99,84,最优子结构性质,71,设,COST(L),和,COST(R),分别是二分检索树,T,的左子树和右子树的,成本,则检索树,T,的成本是：,P(k,)+COST(L)+COST(R),若,T,是最优的，则上式及,COST(L),和,COST(R),必定都取最小值。,最优子结构性质,72,4,、最优子结构性质,二叉搜索树,T,的一棵含有顶点,x,i,x,j,和叶顶点,(,x,i,-1,x,i,),(,x,j,x,j,+1,),的子树可以看作是有序集,x,i,x,j,关于全集为,x,i,-1,x,j,1,的一棵二叉搜索树T,自身可以看作是有序集,),。根据,S,的存取分布概率，在子树的顶点处被搜索到的概率是,最优子结构性质,73,左子树的搜索概率,右子树的搜索概率,设,Tij,是有序集,x,i,x,j,关于存储概率分布为,a,i-1,b,i,b,j,a,j,的一棵最优二叉搜索树,P,ij,：,平均路长,x,m,：,T,ij,的根顶点存储的元素,p,l,和,p,r,:,左子树,T,l,和右子树,T,r,的平均路长,x,i,xj,的存储概率分布为,a,i-1,b,i,b,j,a,j,，其中，,a,h,，,b,k,分别是下面的条件概率：,74,构造最优二叉搜索树时，可以选择先构造其左右子树，使其左右子树最优，然后构造整棵树,最优子结构性质,75,5,、递归计算最优值,最优二叉搜索树,T,ij,的平均路长为,p,ij,，则所求的最优值为,p,1,n,。由二叉树的花费公式,根据最优二叉搜索树问题的最优子结构性质可建立计算,p,ij,的递归式如下,初始时,递归计算最优值,76,记,w,i,j,p,i,j,为,m,(,i,j,),递归计算最优值,77,根据该公式，计算树,Tij,的花费只用到了,Tik-1,，,Tk+1j,可得到具体求解过程如下：,1,）构造只有,1,个内部结点的最优二叉搜索树,T11,T22,Tnn,，可以求得,mii,同时可以用一个数组存做根结点元素为：,s11=1,s22=2,snn,n,2),构造具有,2,个内部结点的最优二叉搜索树,78,例,给出,标识符集,1,2,3,do,if,stop,存取概率,若,P,1,=0.5,P,2,=0.1,P,3,=0.05,q,0,=0.15,q,1,=0.1,q,2,=0.05,q,3,=0.05,构造一棵最优二叉搜索树,递归计算最优值,79,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,1,q0,q1,T11,w11=0.75,m11=0.75,2,q1,q2,T22,w22=0.25,m22=0.25,3,q2,q3,T33,w33=0.15,m33=0.15,1,2q0,q1,q2,1,2,q0,q1,q2,T12,w12=0.9,m12=0.9+,m11+m32,=1.65,w12=0.9,m12=0.9+,m10+m22,=1.15,q0,T10,w10=0.15,m10=0,q1,T21,w21=0.1,m21=0,q2,T32,w32=0.05,m32=0,q3,T43,w43=0.05,m43=0,80,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,1,q0,q1,T11,w11=0.75,m11=0.75,2,q1,q2,T22,w22=0.25,m22=0.25,3,q2,q3,T33,w33=0.15,m33=0.15,1,2,q0,q1,q2,1,2,q0,q1,q2,T12,w12=0.9,m12=0.9+,m11+m32,=1.65,w12=0.9,m12=0.9+,m10+m22,=1.15,2,3,q1,q2,q3,2,3,q1,q2,q3,T23,w23=0.5,m23=0.5,m23=0.6,81,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,1,q0,q1,T11,w11=0.75,m11=0.75,2,q1,q2,T22,w22=0.25,m22=0.25,3,q2,q3,T33,w33=0.15,m33=0.15,1,2,q0,q1,q2,1,2,q0,q1,q2,T12,w12=0.9,m12=0.9+,m11+m32,=1.65,w12=0.9,m12=0.9+,m10+m22,=1.15,2,3,q1,q2,q3,2,3,q1,q2,q3,T23,w23=0.5,m23=0.5,m23=0.6,82,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,T12,m12=1.15,1,2,q0,q1,q2,2,3,q1,q2,q3,T23,m23=0.5,2,3,q2,q3,1,q0,q1,T13,W13=1,m13=15,2,3,q2,q3,1,q0,q1,m13=1.9,2,3,q2,q3,1,q0,q1,m13=2.15,83,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,T12,m12=1.15,1,2,q0,q1,q2,2,3,q1,q2,q3,T23,m23=0.5,2,3,q2,q3,1,q0,q1,T13,W13=1,m13=1.5,2,3,q2,q3,1,q0,q1,m13=1.9,2,3,q2,q3,1,q0,q1,m13=2.15,84,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,0,1,2,3,1,2,3,0,0,0,0,4,0 1 2 3,1,2,3,4,W(i,j),0 1 2 3,1,2,3,4,0,0,0,0,0.15,0.1,0.05,0.05,0.75,0.75,1,0.25,0.15,0.25,0.15,2,3,0.9,1.15,1,0.35,1,0.5,2,1.5,1,m(i,j),s(i,j),85,具体求解过程,递归出口，没有内部节点时，构造,T10,T21,T32,，,Tn+1n,2),构造具有,2,个、,3,个、,、,n,个内部结点的最优二叉搜索树,r,（起止下标的差）,0,T11,T22 ,，,Tnn,，,1,T12,T23,Tn-1n,，,2,T13,T24,，,Tn-2n,，,r,T1r+1,T2r+2,，,Tii+r,，,，,Tn-rn,n-1,T1n,86,void OBST(,int,a,int,b,int,n,int,*,m,int,*,s,int,*,w,),for(,int,i=0;i=n;i+),wi+1i=,ai,;,mi+1i=0;,/,初始化，构造没有内部节点时的情况,for(int,r=0;rn;r+),for(int,i=1;i=,n-r,;i+),int,j=,j+r,;,构造,Tij,，填写,wij,mij,sij,87,构造,Tij,Tij,表示用第,i,到第,j,个内部节点构造的树，做根的结点可以是第,i,，,i+1,j,中任意一个。,1),首选,i,作为根，其左子树空，右子树为结点,i+1,i+2j,构成即,Ti+1j,。,mij,=wij+0+mi+1j,sij,=i,2),不选,i,做根，设,k,为其根，则,k=i+1,j,左子树为结点,i,i+1,k-1,右子树为,k+1,k+2,j,t=wij+mik-1+mk+1j,if(t,mij,),mij,=t;,sij,=k;,3)k=k+1,跳回,2,88,void,OptimalBinarySearchTree,(,int,a,int,b,int,n,int,*,m,int,*,s,int,*,w,),for(,int,i=0;i=n;i+),wi+1i=,ai,;,mi+1i=0;,for(int,r=0;rn;r+),for(int,i=1;i=n-r;i+),int,j=j+r;,wij,=wij-1+aj+bj;,mij,=mi+1j;,sij,=i;,for(int,k=i+1;k=j;k+),int,t=mik-1+mk+1j;,if(t,mij,),mij,=t;,sij,=k;,mij,+=,wij,;,初始化,对角线赋值,i,为起始元素下标,j,为终止元素下标,加第,j,个结点后，权值,w,改变,如第,i,个结点作根的值,取第,k,个结点作根,89,6,、构造最优解,90,7,计算复杂性,91,练习,设,n=4,，且,(1,2,3,4)=(do,if,read,while),。,又设,b(1:4)=(3,3,1,1),和,a(0:4)=(2,3,1,1,1),(,这些,b,a,都乘了,16,。,),写出数组,wij,mij,sij,及最后的最优二叉搜索树,92,作业,P84 3-15,93,动态规划总结,一、动态规划的基本思想：将问题分解为若干小问题，解子问题，然后从子问题得到原问题的解。,94,二、动态规划特点,将问题分解为子问题，这些子问题往往不相互独立。（如果可以用分治法求解，分解的子问题太多，因此，用分治法时间代价太高，消耗指数时间）,95,三、动态规划思路,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。,动态规划方法用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。,96,四、动态规划问题的特征：,动态规划算法的有效性依赖于问题本身所具有的两个重要性质：,最优子结构性质,和,子问题重叠,性质。,1,、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。,2,、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新