高等教育算法设计与分析.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,#,6.1,一般方法,6.2,背包问题,6.3,带时限的作业排序,6.4,最佳合并模式,6.5,最小代价生成树,6.6,单源最短路径,6.7,磁带最优存储,6.8,贪心法的基本要素,第,6,章 贪心法,最优化问题,（,optimization problems,）是指这样一类问题，问题给定某些,约束条件,（,constraint,），满足这些约束条件的问题解称为,可行解,（,feasible solution,）。通常满足约束条件的解不是惟一的。为了衡量可行解的好坏，问题还给出了某个数值函数，称为,目标函数,（,objective function,），使目标函数取最大（或最小）值的可行解称为,最优解,（,optimal solution,）。,6.1,一般方法,贪心法是通过,分步决策,（,stepwise decision,）的方法来求解问题的。,贪心法每一步上用作决策依据的选择准则被称为,最优量度标准,（,optimization criterion,）。,在根据最优量度标准选择分量的过程中，还需要使用一个,可行解判定函数,。,贪心策略并不是从整体上加以考虑的，它所做出的选择只是当前看似最佳选择,，,必须进一步证明该算法最终导致问题的一个整体最优解。,贪心技术,(Greedy Technique),A1),A(2),A(n-1),A(n),某一问题的,n,个输入,B,1,(1),B,1,(2),B,1,(m),该问题的一种解（可行解）,是,A,的一,个子集,满足一定,的条件,约束条件,B,k,(1),B,k,(2),B,k,(m),目标函数,取极值,最优解,【,程序,6,1】,贪心法,SolutionType Greedy(SType a,int n),SolutionType solution=,;,for(int i=0;id,2,d,m,的最少数量的硬币找出金额为,n,的零钱。,如,d,1,=25,d,2,=10,d,3,=5,d,4,=1,，,n=48,该问题的一个解是,：,1,个,25,，,2,个,10,，,3,个,1,，且该解是最优的。,这种方法称为,贪心法,，建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完全解。,必须满足：,可行,、,局部最优,、,不可取消,7,又如：,d,1,=11,d,2,=5,d,3,=1,n=15,该问题的一个解是,：,1,个,11,，,4,个,1,，该解不是最优的。,最优解：,3,个,5,本质上由硬币面值种类决定（问题其本身固有的特点）。,贪心策略最优解的证明,基本思想,设,X=x,1,x,2,.,x,n,为贪心策略得到的解,设,Y=y,1,y,2,.,y,n,为该问题的最优解,很明显，,X,Y,如果成立，则不用证明了。,证明过程：,依次比较,X,和,Y,中的每个元素，如果发现不一样，则用,X,中的替换,Y,中相应元素，比较完后得到一个新的解,Y=X,此时，如能证明,Y,的最优值就是,Y,的最优值或者比,Y,还好，则说明,X,就是最优解。,问题,对容量为,M,的背包进行最佳装载的问题。,6.2,背包问题,6.2.1,问题描述,已知一个载重为,M,的背包和,n,件物品，第,i,件物品的重量为,w,i,，如果将第,i,件物品全部装入背包，将有收益,p,i,，这里，,w,i,0,，,p,i,0,，,0,in,。所谓背包问题是指求一种最佳装载方案，使得收益最大。所以，背包问题是现实世界一个常见的最优化问题。,两类背包问题,:,如果每一件物品不能分割，只能作为整体或者装入背包，或者不装入，称为,0/1,背包问题,；如果物品是可以分割的，也就是允许将其中的一部分装入背包,为,一般背包问题,或简称背包问题。,6.2.2,贪心法求解,背包问题,背包问题的解可以表示成一个,n-,元组：,X=(x,0,x,1,x,n,1,),，,0,x,i,1,，,0,in,，每个,x,i,是第,i,件物品装入背包中的部分。,判定可行解的约束条件是：,背包问题的最优解必须使下列目标函数取最大值：,例,6,1,设有载重能力,M=20,的背包，,3,件物品的重量为,:,（,w,0,w,1,w,2,）,=(18,15,10),，物品装入背包的收益为：（,p,0,p,1,p,2,）,=(25,24,15),。,背包问题,(Knapsack Problem),方案,1,：按物品价值降序装包,方案,2,：按物品重量升序装包,方案,3,：按物品价值与重量比值的降序装包,【,程序,6,2】,背包问题的贪心算法,template,class Knapsack,public:,Knapsack(int mSize,float cap,float*wei,T*prof);,void GreedyKnapsack(float*x);,private:,float m,*w;,T*p;,int n;,;,templatevoid Knapsack:GreedyKnapsack(float*x),/,前置条件：,wi,已按,pi/wi,的非增次序排列,float u=m;,for(int i=0;in;i+)xi=0;,for(i=0;iu)break;,xi=1.0;,u=u-wi;,if(i=n)xi=u/wi;,6.2.3,算法正确性,定理,6,1,如果,p,0,/w,0,p,1,/w,1,p,n,1,/w,n,1,，,则程序,6,2,求得的背包问题的解是最优解。,证明,：,设,X,=(x,0,x,1,x,n-1,),，,0 x,j,1,0i,n,是贪心背包算法所生成的,贪心解,。,如果所有的,x,i,都等于,1,则显然,X,就是问题的,最优解,。否则，,设,j,是使,x,i,1,的最小下标。由算法的执行过程可知，,解的形式为：,X,=(1,1,x,j,0,0),即,x,i,=1 0i,j,0 x,j,1,x,i,=0 j,in-1,假设,Y,是问题的最优解：,Y=(y,0,y,1,y,n-1,),且有：,若,X,Y,，则,X,就是最优解。否则，,X,和,Y,至少在,1,个分量上存在不同。,设,k,是使得,y,k,x,k,的最小下标，则有,y,k,x,k,。可分以下情况说明：,a),若,kj,，则,x,k,=1,。因为,y,k,x,k,从而有,y,k,x,k,b),若,k=j,，由于 ，且对1i,j,，有,y,i,=x,i,=1,而对,j,in,有,x,i,0,；故此时若,y,k,x,k,，则将有 ，与,Y,是可行解相矛盾。而,y,k,x,k,所以,y,k,x,k,c),若,k,j,，则 ，不能成立,在,Y,中作以下调整：将,y,k,增加到,x,k,，因为,y,k,x,k,为保持解的可行性，必须从,(y,k+1,y,n-1,),中减去同样多的量。设调整后的解为,Z,=(z,0,z,1,z,k,z,k+1,z,n-1,),，其中,z,i,x,i,，,0ik,，且有：,Z,的效益值有：,差值,0,由以上分析得，,若 ，则,Y,将不是最优解；,若 ，则或者,Z=X,，则,X,就是最优解；,或者,ZX,，则重复以上替代过程，或者证明,Y,不是最优解，或者把,Y,转换成,X,，从而证明,X,是最优解,最优装载,有一批集装箱要装上一艘载重量为,c,的轮船。其中集装箱,i,的重量为,Wi,。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,1.,算法描述,最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。,template,void Loading(int x,Type w,Type c,int n),int*t=new int n+1;,Sort(w,t,n);,for(int i=1;in;i+)xi=0;,for(int i=1;i=n i+),xti=1;c-=wti;,2.,贪心选择性质,可以证明最优装载问题具有贪心选择性质。,3.,最优子结构性质,最优装载问题具有最优子结构性质。,由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法,loading,的正确性。,算法,loading,的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为,O(nlogn),。,活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,设有,n,个活动的集合,E=1,2,n,，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动,i,都有一个要求使用该资源的起始时间,si,和一个结束时间,fi,且,si fi,。如果选择了活动,i,，则它在半开时间区间,si,fi),内占用资源。若区间,si,fi),与区间,sj,fj),不相交，则称活动,i,与活动,j,是相容的。也就是说，当,sifj,或,sjfi,时，活动,i,与活动,j,相容。,template,void GreedySelector(int n,Type s,Type f,bool A),A1=true;,int j=1;,for(int i=2;i=fj)Ai=true;j=i;,else Ai=false;,下面给出解活动安排问题的贪心算法,GreedySelector,:,各活动的起始时间和结束时间存储于数组,s,和,f,中且按结束时间的非减序排列,由于输入的活动以其完成时间的,非减序,排列，所以算法,greedySelector,每次总是选择,具有最早完成时间,的相容活动加入集合,A,中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是,使剩余的可安排时间段极大化,，以便安排尽可能多的相容活动。,算法,greedySelector,的效率极高。当输入的活动已按结束时间的非减序排列，算法只需,O(n),的时间安排,n,个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用,O(nlogn),的时间重排。,例：设待安排的,11,个活动的开始时间和结束时间按结束时间的非减序排列如下：,i,1,2,3,4,5,6,7,8,9,10,11,Si,1,3,0,5,3,5,6,8,8,2,12,fi,4,5,6,7,8,9,10,11,12,13,14,算法,greedySelector,的计算过程,如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合,A,的活动，而空白长条表示的活动是当前正在检查相容性的活动。,若被检查的活动,i,的开始时间,Si,小于最近选择的活动,j,的结束时间,fi,，则不选择活动,i,，否则选择活动,i,加入集合,A,中。,贪心算法并不总能求得问题的,整体最优解,。但对于活动安排问题，贪心算法,greedySelector,却总能求得的整体最优解，即它最终所确定的相容活动集合,A,的规模最大。这个结论可以用数学归纳法证明。,6.3.1,问题描述,设有一个单机系统、无其它资源限制且每个作业运行相等时间，不妨假定每个作业运行,1,个单位时间。现有,n,个作业，每个作业都有一个截止期限,d,i,0,，,d,i,为整数。如果作业能够在截止期限之内完成，可获得,p,i,0,的收益。问题要求得到一种作业调度方案，该方案给出作业的一个子集和该作业子集的一种排列，使得若按照这种排列次序调度作业运行，该子集中的每个作业都能如期完成，并且能够获得最大收益。也就是说这种作业调度是最优的。,6.3,带时限的作业排序,6.3.2,贪心法求解,例,6,2,设有,4,个作业，每个作业的时限为,(d,0,d,1,d,2,d,3,),=(2,1,2,1),收益为,(p,0,p,1,p,2,p,3,),=(100,10,15,27),。,【,程序,6,3】,带时限作业排序的贪心算法,void GreedyJob(int d,Set X,int n),/,前置条件：,p,0,p,1,p,n-1,X=0;,for(int i=1;in;i+),if(,集合,X,i,中作业都能在给定时限内完成,),X=X,i;,6.3.3,算法正确性,定理,6,2,程序,6,2,的贪心算法对于带时限作业排序问题将得到最优解。,证明,：,设,X,=(x,0,x,1,x,K,),是由贪心算法,6-2,所得的作业集合,贪心解,，,Y=(y,0,y,1,y,r,),是一个,最优解,的作业集合。,若,Y=X,，则,X,就是最优解；否则,，则至少存在两个作业,a,和,b,，使得,aX,且,bY,且 。（为什么）,并设,a,是,这样,的一个具有,最高效益值,的作业,(,由算法的处理规则可得：对于在,Y,中而不在,X,中的作业所有,b,，有：,p,a,p,b,),设,和,分别是,X,和,Y,的可行的,调度表,。因为,X,和,Y,都是可行解，故这样的调度表一定存在；,设,x,是既属于,X,又属于,Y,的一个作业，并设,x,在调度表,中的调度时刻是,t,，,t+1,，,而在,中的调度时刻是,t,，,t+1,。,在,X,和,Y,中作如下调整：,若,t,t,，,则将,中在,t,，,t+1,时刻调度的那个作业（如果有的话）与,x,相交换。如果,X,中在,t,，,t+1,时刻没有作业调度，则直接将,x,移到,t,，,t+1,调度。,新的调度表也是可行的。,x.z,y.x,：,t,t,若,t,t,，则在,中作类似的调换，即将,中在,t,，,t+1,时刻调度的那个作业（如果有的话）与,x,相交换。如果,Y,中在,t,，,t+1,时刻没有作业调度，则直接将,x,移到,t,，,t+1,调度。,同样，新的调度表也是可行的。,对,X,和,Y,中共有的所有作业作上述的调整。设调整后得到的调度表为,和,，则在,和,中,X,和,Y,中所有的,共有作业,将在,相同时间,被调度。,y.x,x.z,：,：,t,t,设,a,在,中的调度时刻是,t,a,t,a,+1,，,b,是,中该时刻调度的作业，则有,p,a,p,b,（为什么？）。,在,中，去掉作业,b,，而去调度作业,a,，得到的是作业集合,Y=,（,Y-b,）,a,的 一个可行的调度表，且,Y,的效益值不小于,X,的效益值。而,Y,中比,Y,少了一个与,X,不同的作业。,重复上述的转换，可使,Y,在,不减,效益值的情况下转换成,X,。从而,X,至少有和,Y,一样的效益值。所以,X,也是最优解。,证毕。,.a,.b,：,：,t,a,=,（,x,z,）,=,（,z,x,）,=,（,y,x,）,=,（,y,x,）,(a)x,与,z,交换前,(b)x,与,z,交换后,=,（,y,x,）,=,（,y,x,）,=,（,x,z,）,=,（,z,x,）,(c)x,与,z,交换前,(d)x,与,z,交换后,图,6-1,使相同作业在相同时刻被调度,6.3.4,可行性判定,定理,6,3,X=,（,x,0,x,1,x,k,）是,k,个作业的集合，,=,（,0,1,k,）是,X,的一种特定排列，它使得,d,0,d,1,d,k,，其中，,d,j,是作业,j,的时限。,X,是一个可行解当且仅当,X,中的作业能够按,次序调度而不会有作业超期。,方法一,：枚举法，检验,X,中作业所有可能的排列，对于任一种次序排列的作业序列，判断这些作业是否能够在其期限前完成,若,X,中有,k,个作业，则将要检查,k!,个序列,判断策略：,对于一个给定,作业处理序列,i,1,i,2,i,k,由于作业,i,j,完成的,最早时间,是,j,，因此只要判断出,排列中的每个作业的期限有,d,ij,j,，就可得知,是一个允许的调度序列，从而,X,是一可行解。,反之，如果,排列中有一个作业有,d,ij,j,则,将是一个行不通的调度序列，因为至少作业,i,j,不能在其期限之前完成。,方法二,：检查,X,中作业的一个,特定序列,就可判断,X,的可行性：,这一特定序列是按照,作业期限,的,非降次序,排列的作业序列,证明：,如果,X,中的作业可以按照,的次序而又不违反任何一个作业期限的情况来处理，则,X,是一个,可行解,现证,若,X,是一个可行解，,是否代表一个可行的调度序列？,X,是可行解,必存在一可行的调度序列,r,1,r,2,r,k,，使得,d,rj,j,1jk若,，则,即是可行的调度序列。否则，,，令,a,是使得,r,a,i,a,的最小下标（如下图）,i,1,i,2,i,a,i,c,i,k,r,1,r,2,r,a,r,b,r,k,设,rb=ia,。则有,：,b,a,且,d,ra,d,rb,故，在,中调换,ra,与,rb,，所得的新序列,s1s2sk,的处理次序不违反任何一个期限，而,中位置,a,及,a,之前的作业均与,相同。,重复上述过程，则可将,转换成,且不违反任何一个期限，故,是一个可行的调度序列,故定理得证。,6.3.5,作业排序贪心算法,定理,6,3,提供了一种高效的可行解判定方法。使得在按最优量度标准，即按作业收益的非增次序选择下一个作业后，可以有效地判定是否可将该作业加入已生成的部分解向量,X,。,【,程序,6,4】,带时限的作业排序程序,int JS(int*d,int*x,int n),/,设,p,0,p,1,p,n-1,int k=0;x0=0;,for(int j=1;j=0,if(rr+1),for(int i=k;i=r+1;i-)xi+1=xi;,xr+1=j;k+;,return k;,6.3.6,一种改进算法,本小节将介绍一种带时限作业排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的时间从,(n2),减少到接近,O(n),。,例,6,3,设,n=5,个作业，,作业的时限为,:(d0,d1,d2,d3,d4)=(2,2,1,3,3),收益为,:(p0,p1,p2,p3,p4)=(20,15,10,5,1),。,【,程序,6,5】,使用并查集的带时限作业排序,int FJS(int*d,int*x,int n),UFSet s(n);,int b,k=-1,*f=new intn+1;,for(int i=0;i=n;i+)fi=i;,for(i=0;in;i+),if(nm,时，首先将,n,个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为,O(nlogn),。,例如,，,设,7,个独立作业,1,2,3,4,5,6,7,由,3,台机器M1,，,M2,和,M3,加工处理。各作业所需的处理时间分别为,2,14,4,16,6,5,3,。按算法,greedy,产生的作业调度如下图所示，所需的加工时间为,17,。,6.4.1,问题描述,两路合并外排序算法通过反复执行将两个有序子文件合并成一个有序文件的操作，最终将,n,个长度不等的有序子文件合并成一个有序文件。,合并,n,个有序子文件成为一个有序文件的合并过程可以有多种方式，称为,合并模式,。,在整个合并过程中，需从外存读写的记录数最少的合并方案称为,最佳合并模式,（,optimal merge pattern,）。,6.4,最佳合并模式,例,6,4,设有,5,个有序子文件（,F,1,F,2,F,3,F,4,F,5,），其长度分别为（,20,，,30,，,30,，,10,，,5,）。现通过两两合并将其合并成一个有序文件。,带权外路径长度,是针对扩充二叉树而言的。,扩充二叉树,（,extended binary tree,）中除叶子结点外，其余结点都必须有两个孩子。扩充二叉树的带权外路径长度（,weighted external path length,）定义为：,6.4.2,贪心法求解,两路合并最佳模式问题的,最优量度标准,为带权外路径长度最小。,两路合并最佳模式的贪心算法简述如下：,设,W,w,0,w,1,w,n,1,是,n,个有序文件的长度；以每个权值作为根结点值，构造,n,棵只有根的二叉树；,选择两棵根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根的权值之和；,重复,第,2,步,，直到合并成一棵二叉树为止。,【,程序,6,6】,两路合并最佳模式的贪心算法,template,struct HNode,/,优先权队列中的元素的类型,operator T()const return weight;,BTNode*ptr;,T weight;,;,template,BTNode*CreateHfmTree(T*w,int n),/w,为一维数组保存,n,个权值,PrioQueue pq(2*n-1);,BTNode*p;HNode ab;,for(int i=0;in;i+),p=new BTNode(wi);,a.ptr=p;a.weight=wi;,pq.Append(a);,for(i=1;in;i+),pq.Serve(a);pq.Serve(b);,a.weight+=b.weight;,p=new BTNode(a.weight,a.ptr,b.ptr);,a.ptr=p;,pq.Append(a);,pq.Serve(a);,return a.ptr;,6.4.3,算法正确性,定理,6,4,设有,n,个权值,W=,w,0,w,1,w,n,1,作为外结点的权值，构造两路合并树的贪心算法将生成一棵具有最小带权外路径长度的二叉树。,6.5.1,问题描述,问题,一个无向连通图的,生成树,是一个极小连通子图，它包括图中全部结点，并且有尽可能少的边。,一棵,生成树的代价,是树中各条边上的代价之和。一个网络的各生成树中，具有最小代价的生成树称为该网络的,最小代价生成树,（,minimum-cost spanning tree,）。,6.5,最小代价生成树,网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边,(v,w),的权,cvw,表示建立城市,v,和城市,w,之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。,6.5.2,贪心法求解,最优量度标准,选择使得迄今为止已入选,S,中边的代价之和增量最小的边,克鲁斯卡尔算法,的贪心准则是：按边代价的非减次序考察,E,中的边，从中选择一条代价最小的边,e=(u,v),。,普里姆算法,的贪心准则是：在保证,S,所代表的子图是一棵树的前提下选择一条最小代价的边,e=(u,v),。,最小生成树性质,用贪心算法设计策略可以设计出构造最小生成树的有效算法。将介绍的构造最小生成树的,Prim,算法和,Kruskal,算法都可以看作是应用贪心算法设计策略的例子。尽管这两个算法做贪心选择的方式不同，它们都利用了下面的,最小生成树性质,：,设,G=(V,E),是连通带权图，,U,是,V,的真子集。如果,(u,v),E,，且,u,U,，,v,V-U,，且在所有这样的边中，,(u,v),的权,cuv,最小，那么一定存在,G,的一棵最小生成树，它以,(u,v),为其中一条边。这个性质有时也称为,MST,性质,。,【,程序,6,7】,最小代价生成树的贪心算法,ESetType SpanningTree(ESetType E,int n),/G=(V,E),为无向图,ESetType S=,;,int u,v,k=0;EType e;,while(kn-1&E,中尚有未检查的边,),e,select(E);,if(S,e,不包含回路,),S=S,e;k+;,return S;,6.5.3,Prim(,普里姆,),算法,【,程序,6,8】,普里姆算法,template,struct ENode,/,带权图的边结点,int adjVex;,T w;,ENode*nextArc;,;,template,class Graph,public:,Graph(int mSize);,void Prim();,protected:,void Prim(int k,int*nearest,T*lowcost);,ENode*a;,int n;,;,template,void Graph:Prim(int s),/,公有成员函数,int*nearest=new intn,*lowcost=new intn;,Prim(s,nearest,lowcost);,for(int j=0;jn;j+),cout(nearestj,“,j,lowcostj);,coutendl;,delete nearest;delete lowcost;,template,void Graph:Prim(int k,int*nearest,T*lowcost),/,私有成员函数,bool*mark=new booln;,ENode*p;,if(kn-1)throw OutofBounds;,for(int i=0;in;i+),nearesti=-1;marki=false;,lowcosti=INFTY;,lowcostk=0;nearestk=k;markk=true;,for(i=1;inextArc),int j=p-adjVex;,if(!markj)&(lowcostjp-w),lowcostj=p-w;nearestj=k;,T min=INFTY;,for(int j=0;jn;j+),if(!markj)&(lowcostj&pq),eNode x;,UFSet s(n);,int u,v,k=0;,while(kn-1&!pq.IsEmpty(),pq.Serve(x);,u=s.Find(x.u);v=s.Find(x.v);,if(u!=v),s.Union(u,v);,k+;,cout(x.ux.v,x.w);,coutendl;,if(kn-2)throw NonConnected;,克鲁斯卡尔算法的时间复杂度为,O,（,elog,e,）。,6.5.5,算法正确性,定理,6,5,设图,G=,（,V,，,E,）是一个带权连通图，,U,是,V,的一个真子集。若边,(u,v),E,是所有,u,U,v,V-U,的边中权值最小者，那么一定存在,G,的一棵最小代价生成树,T=(V,S),，,(u,v),S,。这一性质称为,MST,（,minimum spanning tree,）性质。,定理,6,6,普里姆算法和克鲁斯卡尔算法都将产生一个带权无向连通图的最小代价生成树。,6.6.1,问题描述,单源最短路径问题是：给定带权的有向图,G=(V,E),和图中结点,s,V,，求从,s,到其余各结点的最短路径，其中，,s,称为源点。,6.6,单源最短路径,6.6.2,贪心法求解,迪杰斯特拉,（,Dijkstra,）算法,首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有结点之间的最短路径都已求得为止。,6.6.3,迪杰斯特拉算法,【,程序,6,10】,迪杰斯特拉算法,template,class MGraph,public:,MGraph(int mSize);,void Dijkstra(int s,T*,private:,int Chooseint*d,bool*s);,T*a;,int n;,;,template,int MGraph:Choose(int*d,bool*s),int i,minpos;T min;,min=INFTY;minpos=-1;,for(i=1;in;i+),if(dimin&!si),min=di;minpos=i;,return minpos;,template,void MGraph:Dijkstra(int s,T*&d,int*&path),int k,i,j;,if(sn-1)throw OutOfBounds;,bool*inS=new booln;,d=new Tn;path=new intn;,for(i=0;in;i+),inSi=false;di=asi;,if(i!=s,else pathi=-1;,inSs=true;ds=0;,for(i=1;in-1;i+),k=Choose(d,inS);,inSk=true;,for(j=0;jn;j+),if(!inSj&dk+akj dj),dj=dk+akj;pathj=k;,6.6.4,算法正确性,定理,6,7,已知带权有向图,G=(V,E),，其源点为,s,，迪杰斯特拉算法使得对所有,i,，,i,V-s,，,di,(s,i),，且一旦,di=,(s,i),，它将不再改变。,定理,6,8,已知带权有向图,G=(VE),，其源点为,s,，迪杰斯特拉算法使得对所有结点,i,和,j,i,S,，,j,V-S,，必有,di,dj,。,定理,6,9,已知带非负权值的有向图,G=(V,E),，路径（,s=v,0,v,i,v,k,=t,）是从,s,到,v,k,的一条最短路径，,v,i,V,，,0,i,kn,，则子路径（,s=v,0,v,i,）和（,v,i,v,k,=t,）必定分别是从,s,到,v,i,和,v,i,到,t,的最短路径。,定理,6,10,已知带非负权值的有向图,G=(V,E),，其源点为,s,，迪杰斯特拉算法结束时，对所有结点,i,，有,di=,(s,i),。,6.7.1,单带最优存储,问题,设有,n,个程序编号为,0,n-1,，,存放在长度为,L,的磁带上，程序,i,在磁带上的存储长度为,a,i,，,0,in,。,假定每个程序被检索地概率相等，则,平均检索时间,（,mean retrieval time MRT,）定义为,单带最优存储问题是求这,n,个程序的一种排列，使得,MRT,有最小值。,6.7,磁带最优存储,例,6,5,设,n=3,，,(a,0,a,1,a,2,)=(5,10,3),。,贪心法求解,量度标准：计算迄今为止已选的那部分程序的,D,值，选择下一个程序应使得该值增加最小。,定理,6,11,设有,n,个程序,0,1,n-1,程序,i,的长度为,a,i,，,0,in,，且有,a0,a,1,a,n,1,，,=(,0,1,n,1,),是这,n,个作业的一种排列。那么只有当,j,=j,，,0,i1,条磁带,T,0,T,1,T,m,1,和,n,个程序。要求将此,n,个程序分配到这,m,条磁带上，令,I,j,0,jm,是存放在第,j,条磁带上的程序子集的某种排列，,D(I,j,),的定义如前面相同，那么，求,m,条磁带上检索一个程序的平均检索时间的最小值等价于求,的最小值。,【,程序,6,11】,多带最优存储,#include,void Store(int n,int m),int j=0;,for(int i=0;in;i+),cout ,将程序,i,加到磁带,jendlj=(j+1)%m;,coutendl;,定理,6,12,设有,n,个程序,0,1,n-1,程序,i,的长度为,a,i,，,0,in,，且有,a,0,a,1,a,n,1,，程序,6,11,实现将,n,个程序分配到,m,条磁带上，且有最小,TD,值。,6.8.1,最优量度标准,选择最优量度标准是使用贪心法求解问题的核心问题。,贪心算法每一步作出的选择可以依赖以前作出的选择，但不依赖将来的选择，也不依赖于子问题的解。,对于一个贪心算法，必须证明所采用的量度标准能够导致一个整体最优解。,6.8,贪心法的基本要素,6.8.2,最优子结构,最优子结构特性是关于问题最优解的特性。当一个问题的最优解中包含了子问题的最优解，则称该问题具有,最优子结构特性,（,optimal substructure,）。,一般而言，如果一个最优化问题的解结构具有元组形式，并具有最优子结构特性，我们可以尝试选择量度标准。,