东北大学数据结构期末复习.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,期末复习,题型,选择题（,10,分）,填空题（,10,分）,算法应用题（算法填空，简单问题回答）（,3-4,个题，,35-40,分）,算法设计（按照已知条件设计算法或为算法补充完整）（,3,个题，,45-50,分）,10/28/2026,2,第,1,章,算法的性质及其与程序的区别,算法复杂性分析,渐进意义下的四种记号,简单的程序段的复杂度分析,10/28/2026,3,算法的五个重要特征,输入,有,零个或多个,由外部提供的量作为算法的输入,输出,算法产生,至少一个量,作为输出,.,确定性,组成算法的每条指令是清晰的,无歧义的,.,有限性,在执行了有穷步骤后运算终止,可行性,运算都是基本运算，原理上能在有限时间内完成。,10/28/2026,4,渐进意义下的记号：,O,f,(,N,),和,g,(,N,),是定义在正整数上的正函数,定义,1.1,如果存在两个正常数,c,和,N,0,对于所有的,N,N,0,，有,f,(,N,),Cg,(,N,),，则记作：,f,(,N,)=,O,(,g,(,N,),。,N,0,f(N,),g(N,),当说一个算法具有,O(g(n,),的计算时间时，指的,就是如果此算法用,n,值不变的同一类数据在某台,机器上运行时，所用的时间总是小于,g(n,),的一个,常数倍。,g(n,),是计算时间,f(n,),的一个上界函数，,f(n,),的数,量级就是,g(n,),10/28/2026,5,符号,的定义,定义,1.2,如果存在两个正常数,C,和自然数,N0,，使得当,N,N,0,时有,f,(N),Cg,(,N,),，则称函数,f,(,N,),当,N,充分大时下有界；且,g,(,N,),是它的一个下界，记为,f,(,N,)=(,g,(,N,),。这时我们说,f,(,N,),的阶不低于,g,(,N,),的阶。,10/28/2026,6,，,o,的定义,定义,f,(,N,)=,(,g,(,N,),当且仅当,f,(,N,)=,O(g(N,),且,f(N,)=(,g(N,),。这时，我们说,f(N,),与,g,(,N,),同阶,o,如果对于任意给定的,0,，都存在正整数,N,0,，使得当,N,N,0,时有,f,(,N,)/,g,(,N,),，则称函数,f,(,N,),当,N,充分大时的阶比,g,(,N,),低，记为,f,(,N,)=,o,(,g,(,N,),例如：,4,N,log,N,+7=o(3,N,2,+4,N,log,N,+7),10/28/2026,7,10/28/2026,8,1.2,算法分析初步,多项式时间算法,(polynomial time algorithm):,可用多项式来对其计算时间限界的算法,O(1),O(logn,),O(n,),O(nlogn,)O(n,2,)O(n,3,),指数时间算法,(exponential time algorithm):,计算时间用指数函数限界的算法,O(2,n,),O(n,!),O(n,n,),10/28/2026,9,作业,1-7,10/28/2026,10,第,2,章,递归,分治法基本思想,二分搜索算法,Strassen,矩阵乘法,合并排序和快速排序,10/28/2026,11,递归复杂度分析,10/28/2026,12,汉诺塔移动次数,M(1)=1,M(n,)=2M(n-1)+1,=22M(n-2)+1+1,=2,2,M(n-2)+2+1,=2,3,M(n-3)+2,2,+2+1,=,=2,i,M(n-i)+2,i-1,+2,i-2,+2+1,=2,i,M(n-i)+2,i,-1,令,i=n-1,则,M(n,)=2,n-1,+2,n-1,-1=2,n,-1,2.1,递归,10/28/2026,13,分治法的基本思想,分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：,把它分成两个或多个更小的问题；,分别解决每个小问题；,把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。,10/28/2026,14,例,2-6,在,9,12,15,27,39,中分别查找,27,，,12,，,14,9 12 15 27 39,0 1 2 3 4,left,right,mid,mid=(left+right)/2,=(0+4)/2=2,mid=(3+4)/2=3,9 12 15 27 39,left,right,mid,查找,27,成功返回,3,，,leftright,mid,9 12 15 27 39,left,right,10/28/2026,15,template,int,BinarySearch,(,T a,const T&x,int,n,),/,在,a0=a1=,amiddle,)left=;,else right=;,return 1;/,未找到,x,n-1,0,left1,时，,T,w,(n,)=T,w,(n/2)+1,T(1)=1,T,w,(n,)=T,w,(n/2)+1,=T,w,(n/4)+1,+1,=T,w,(1)+1+.+1=1+k=1+logn,10/28/2026,17,二分搜索的时间复杂度,最坏情况下的成功检索计算时间,(logn,),最坏情况下的不成功检索计算时间,(logn,),最好情况下的成功检索计算时间,(1),最好情况下的不成功检索计算时间,(logn,),每种不成功的检索时间都为,(logn,),2.2,二分搜索技术,10/28/2026,18,作业：,P34,，,2-2,中第二个和第五个算法的正确性，错误的说明原因或者给出反例,2.P35,2-3,10/28/2026,19,2-3,：,二分搜索中当程序停止时，左右指针或者指向同一个元素，此时该元素等于待查找元素,或者,left=right+1,，此时,right,指向的为比待找元素小的元素，,left,为比待找元素大的元素,10/28/2026,20,归并排序主程序伪代码,template,void,MergeSort(Type,a,int,left,int,right),/,Aleft:right,是一个全程数组，含有,right-left+1,个待排序的元素。,if,(),/,至少有,2,个元素,int,mid=(left+right)/2;,/,求当前数组的分割点,MergeSort(a,，,left,mid);,MergeSort(a,，,mid+1,right);,Merge(a,，,b,，,left,mid,right);,copy,（,a,，,b,，,left,，,right,）；,left right,递归调用，分别对分解出来的两个子问题排序,合并两个排好序的子问题，放入另一个数组,b,中,2.4,合并排序,10/28/2026,21,考虑数组,a,的两段为,1,7,8,9,和,2,3,4,5,1,7,8,9,2,3,4,5,1,7,8,9,2,3,4,5,1,1,2,1,7,8,9,2,3,4,5,1,2,3,1,7,8,9,2,3,4,5,1,2,3,4,1,7,8,9,2,3,4,5,1,2,3,4,5,数组,a,的两部分,数组,b,1,2,3,4,5,7,1,2,3,4,5,7,8,1,2,3,4,5,7,8,9,在移动扫描指针的同时，要判断其是否已经到达数组的尾部，如到达，则停止扫描，把未参加排序的数全部放入备用数组中,2.4,合并排序,10/28/2026,22,合并函数,template,void Merge(Type a,Type b,int,l,int,m,int,r),/,合并,al:m,和,am+1:r,到,bl:r,int,i=,l,;,j=m+1,k=,l,;,while(,)&(,),if(a i m)for(,int,q=j;q=r;q+),b k+=a q;,else for(,int,q=I;q=m;q+),b k+=a q;,把,al:m,和,am+1:r,中的数据进行比较，按顺序放入,b,中,如果前一段数据小于后一段的多，则先排完，把后段剩余数赋给,bn,否则将前段数据赋给,bn,前半段指针,后半段指针,数组,b,的下标指针,i=m,j=r,2.4,合并排序,10/28/2026,23,作业,分析,merge,函数最好与最坏的键值比较次数。,最好比较,1,次,最差比较,m+n-1,，,m,和,n,分别为两段数组的长度,10/28/2026,24,快速排序,Template,void,QuickSort(Type,a,int,p,int,r),if(p,r),int,q=,Partition(a,p,r,);,QuickSort(a,p,q-1);/,对左半段排序,QuickSort(a,q+1,r);/,对右半段排序,a,的起始位置,A,的终止位置,Partition,函数负责将,a,进行一次分割，返回分割元素的位置,快速排序问题,10/28/2026,25,划分程序,template,int,Partition(Type,a,int,p,int,r),int,i=,j=,;,Type x=,;,while(true),while(,a+i x,);,if(,)break;,Swap(a i,a j );,a p =,;,a j =,;,return j;,快速排序问题,p,r+1,a p,i=j,a j,x,左侧扫描指针起始,右侧扫描指针起始,中轴元素,移动左侧扫描指针,移动右侧扫描指针,10/28/2026,26,算法分析,最坏情况：划分的两个区域分别包含,n,1,个元素和,1,个元素，如果每一步都出现这种情况，其复杂性,T,(,n,),O,(1),n,1,T,(,n,)=,T,(,n,-1)+,O,(,n,),n,1,解得：,T,(,n,)=,O,(,n,2,),快速排序问题,10/28/2026,27,最好情况,每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为,n/2,的区域，,O(1)n,1,T(n,)=,2T(n/2)+O(n)n1,T(n,)=,O(nlogn,),快速排序问题,10/28/2026,28,2-19,将算法,Partition,中的不等号反向,10/28/2026,29,第,3,章,动态规划思想，基本要素,矩阵连乘算法及最优解构造,0-1,背包问题最优值及最优解,最优二叉搜索树,（通过具体实例弄清每个算法的流程及算法的具体实现）,10/28/2026,30,动态规划算法,将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而,避免计算重复的子问题,，再由子问题的解得到原问题的解。,算法思想,10/28/2026,31,动态规划算法的基本要素,1,最优子结构性质,2,重叠子问题性质,10/28/2026,32,1.,最优子结构,当问题的最优解包含了其子问题的最优解时，称该问题具有,最优子结构性质,。,分析最优子结构性质时，一般假设由问题的最优解导出的子问题不是最优的，然后再设法说明在这个假设下可以构造出一个比原问题更优解更好的解，从而导出矛盾。,动态规划算法的基本要素,10/28/2026,33,2.,重叠子问题,在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法对每个问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法通常只需要多项式时间。,动态规划算法的基本要素,10/28/2026,34,动态规划与分治的联系区别,都是分解成子问题，由子问题的解得到原问题的解。,分治中子问题相互独立，而动态规划中子问题互相有联系，且存在重复计算，即存在,重叠子问题,。,10/28/2026,35,动态规划算法设计步骤,（,1,）找出最优解的性质，刻画其结构特征,（,2,）递归地定义最优值,（,3,）以自底向上的方式计算出最优值,（,4,）根据计算最优值时得到的信息，构造一个最优解,10/28/2026,36,矩阵连乘问题,给定,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,的结果与相乘的次数。,10/28/2026,37,最优子结构特征,计算,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,10/28/2026,38,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,矩阵连乘问题,10/28/2026,39,采用递归方法计算,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(tu),u=t;,sij,=k;,return u;,参加运算矩阵链起始位置,矩阵链终止位置,i=j,取第一个断开位置时计算量,记录当前断开位置,循环取,k,的可取断开位置,矩阵连乘问题,10/28/2026,40,递归树,1,4,1,1,2,4,1,2,3,4,1,3,4,4,2,2,3,4,2,3,4,4,1,1,2,2,3,3,4,4,1,1,2,3,1,2,3,3,3,3,4,4,2,2,3,3,2,2,3,3,1,1,2,2,矩阵连乘问题,10/28/2026,41,2,4,2,2,3,4,1,2,3,3,4,4,1,1,1,4,1,3,2,3,矩阵连乘问题,3.,计算最优值,10/28/2026,42,3.,计算最优值,置所有只有一个矩阵的矩阵链计算量为,0,，即,mii,=0,，,i=1,2,n,。,通过上一步的结果可以得到所有矩阵链长度为,2,的子问题的最优计算量。,通过上两步的结果可以得到所有矩阵链长度为,3,的子问题的最优计算量,矩阵连乘问题,计算,m i j,时，只用到已计算出的,m i k,和,m k+1 j,10/28/2026,43,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,10/28/2026,44,3.,计算最优值,void,MatrixChain(int,p,int,n,int,*m,int,*s),for(,int,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,10/28/2026,45,算法复杂度,算法,MatrixChain,的主要计算量取决于程序中对,r,i,和,k,的三重循环，,循环体内的计算量为,O(1),，三重循环的总次数是,O(n,3,),，所以，算法的计算时间上界为,O(n,3,),。,10/28/2026,46,4.,构造最优解,上述算法只是明确给出了矩阵最优连乘次序所用的数乘次数,m1n,，并未明确给出最优连乘次序，即完全加括号方法。但是以,sij,为元素的,2,维数组却给出了足够的信息。事实上，,sij,=k,说明，计算连乘积,Ai:j,的最佳方式应该在矩阵,Ak,和,Ak+1,之间断开，即最优加括号方式为,(Ai:k)(Ak+1:j),。,10/28/2026,47,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,A,1,(A,2,)(A,3,),S22=S33=0,S66=0,S45=0,(A,4,)(A,5,),A,6,S44=S55=0,10/28/2026,48,根据最优值算法构造最优解,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,10/28/2026,49,作业,1,当,A,1,A,2,A,3,A,4,A,5,分别为,2025,，,2510,，,105,，,515,，,1520,的矩阵时，填写相应的,mij,和,sij,，并给出最优计算次序。,10/28/2026,50,备忘录方法,用一个表格来保存已解决的子问题的答案，用的时候查表即可。,采用的递归方式是,自顶向下,，动态规划是,自低向上,控制结构与直接递归相同，区别在于备忘录方式为每个解过的子问题建立备忘录。,初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问题的解答即可。,动态规划算法的基本要素,10/28/2026,51,备忘录方法解矩阵乘,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,10/28/2026,56,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),10/28/2026,57,2.,递归关系,设背包问题的子问题的最优值为,m(i,j),即,m(i,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),10/28/2026,58,例,:,四个物品，背包容积为,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,10/28/2026,59,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,时，要进行选择,10/28/2026,60,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,10/28/2026,61,构造最优解,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,10/28/2026,63,3-4,钱币问题,10/28/2026,64,3.5,最优二叉搜索树,Optimal Binary Search Trees,10/28/2026,65,最优二叉搜索树,利用动态规划构造对标识符集合,a1,a2,an,的,最优二叉搜索树,算法,包括,成功检索,和,不成功检索,）。,最优二叉搜索树,10/28/2026,66,3,、最优二叉搜索树问题,对于有序集,S,及其存取概率分布,（,a,0,b,1,a,1,b,n,a,n,），在所有表示有序集,S,的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。,结点在二叉搜索树中的层次越深，需要比较的次数就越多，因此要构造一棵最小二叉树，一般尽量把搜索概率较高的结点放在较高的层次。,最优二叉搜索树问题,10/28/2026,67,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,最优子结构性质,10/28/2026,68,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,的存取分布概率，在子树的顶点处被搜索到的概率是,最优子结构性质,10/28/2026,69,左子树的搜索概率,右子树的搜索概率,设,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,分别是下面的条件概率：,10/28/2026,70,构造最优二叉搜索树时，可以选择先构造其左右子树，使其左右子树最优，然后构造整棵树,最优子结构性质,10/28/2026,71,5,、递归计算最优值,最优二叉搜索树,T,ij,的平均路长为,p,ij,，则所求的最优值为,p,1,n,。由二叉树的花费公式,根据最优二叉搜索树问题的最优子结构性质可建立计算,p,ij,的递归式如下,初始时,递归计算最优值,10/28/2026,72,记,w,i,j,p,i,j,为,m,(,i,j,),递归计算最优值,10/28/2026,73,例,给出,标识符集,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,构造一棵最优二叉搜索树,递归计算最优值,10/28/2026,74,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,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,10/28/2026,75,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,10/28/2026,76,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,10/28/2026,77,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,10/28/2026,78,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,10/28/2026,79,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),10/28/2026,80,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,个结点作根,10/28/2026,81,练习,设,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,及最后的最优二叉搜索树,10/28/2026,82,作业,P84 3-15,10/28/2026,83,第,4,章,贪心算法的基本要素，思想，与动态规划的区别联系,活动安排问题,最优装载,单源最短路径,多机调度问题,10/28/2026,84,什么是贪心方法,如果硬币面值为,1,角,1,分,、,7,分,、,5,分,、和,1,分,。,要找给顾客,2,角,6,分,钱，,按贪心方法找出的硬币个数是：,2,个,1,角,1,分和四个,1,分，共,6,枚，,这比,1,个,1,角,1,分和,3,个,5,分多了,2,枚；因此，从,局部的最优选择,得到的解,并不总是问题的最优解,。,10/28/2026,85,贪心算法,总是作出在当前看来最好的选择。,也就是说贪心算法,并不从整体最优,考虑，它所作出的选择只是在某种意义上的,局部最优选择,。当然，,希望,贪心算法得到的最终结果也是整体最优的。,虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。,在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,10/28/2026,86,贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。,希望通过每次所做的选择导致最终结果是问题的一个最优解。,希望从,局部的最优选择,得到,整体最优解,。,贪心算法的基本要素,贪心算法的基本要素,10/28/2026,87,贪心算法的基本要素,可用贪心算法求解的问题的基本要素,用贪心算法求解的问题，具有两个重要的性质：,最优子结构性质,贪心选择性质,。,贪心算法的基本要素,10/28/2026,88,1.,最优子结构性质,最优子结构性质,整体最优解,包含它的,子问题的最优解,。,具有,最优子结构性质,是一个问题可用动态规划算法或贪心算法求解的一个关键特征。,贪心算法的基本要素,10/28/2026,89,最优子结构性质,例：,活动安排问题中最优子结构性质表现为：若,A,是对于,E,的活动安排问题包含活动,1,的一个最优解，则相容活动集合,A=A 1,是对于,E=,iE,:s,i,f,1,的活动安排问题的一个最优解,10/28/2026,90,2.,贪心选择性质,贪心选择性质,:,所求问题的整体最优解可以通过一系列局部最优的选择来完成即贪心选择来达到。,这是贪心算法可行的要素。也是贪心算法与,动态规划算法,的主要区别。,如找顾客钱币问题和图的染色问题不具有,贪心选择性质,。,贪心算法的基本要素,10/28/2026,91,3.,贪心算法与动态规划算法的差异,相同点：都具有最优子结构性质,区别：动态规划算法每步所作的选择往往依赖于相关子问题的解。只有解出相关子问题才能作出选择。,贪心算法仅在当前状态下作出最好选择，即局部最优选择，但不依赖于子问题的解,贪心：自顶向下,动态规划：自低向上,贪心算法的基本要素,10/28/2026,92,贪心算法与动态规划算法的差异,对于一个具有最优子结构的问题应该选用贪心算法还是动态规划算法？,是不是能用动态规划算法求解的问题也能用贪心算法来求解？,10/28/2026,93,活动安排问题,已知,n,个活动,E,=1,2,n,要求使用同一资源，第,k,个活动要求的开始和结束时间为,s,k,f,k,其中,s,k,f,k,k,=1,2,n,。活动,k,与活动,j,称为相容的如果,s,k,f,j,或者,s,j,f,k,。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。,问题提出：,10/28/2026,94,基本思路,在安排时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。,贪心准则应当是：,在未安排的活动中挑选结束时间最早的活动安排。,活动安排问题,10/28/2026,95,活动安排贪心算法伪代码,template,void,GreedySelector(int,n,Type,starttime,Type,fintime,bool,A,),