计算机算法基础3.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 贪心方法,3.1,一般方法,1.,问题的一般特征,问题有,n,个输入，问题的解是由这,n,个输入的某个,子集,组成，这个子集必须满足某些事先给定的条件。,约束条件,：子集必须满足的条件；,可 行 解,：满足约束条件的子集；可行解可能不唯一；,目标函数,：用来衡量可行解优劣的标准，一般以函数的形式给出；,最 优 解,：能够使目标函数取极值（极大或极小）的可行解。,分类,：根据描述问题约束条件和目标函数的,数学模型,的特性和问题的,求解方法,的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。,最优化问题求解,贪心方法,：一种改进的,分级,的处理方法，可对满足上述特征的某些问题方便地求解。,2.,贪心方法的一般策略,问题的一般特征：问题的解是由,n,个输入的、满足某些事先给定的条件的子集组成。,1,）一般方法,根据题意，选取一种,度量标准,。然后按照这种度量标准对,n,个输入,排序,，并按序一次输入一个量。,如果这个输入和当前已构成在这种量度意义下的,部分最优解,加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的,新,的,部分解,。,这一处理过程一直持续到,n,个输入都被考虑完毕，则记入最优解集合中的输入子集构成这种量度意义下的问题的,最优解,贪心方法,:,这种能够得到某种量度意义下的最优解的,分级处理,方法,称为,贪心方法,注：,贪心解 最优解,直接将目标函数作为,量度标准,也不一定能够得到问题的最优解,使用贪心策略求解的关键是选取能够得到问题最优解的,量度标准,。,3.,贪心方法的抽象化控制描述,procedure GREEDY(A,n),/A(1:n),包含,n,个输入,/,solution,/,将解向量,solution,初始化为空,/,for i1 to n do,xSELECT(A,)/,按照度量标准，从,A,中选择一个输入，,其值赋予,x,并将之从,A,中删除,/,if FEASIBLE(solution,x)then /,判定,x,是否可以包含在当前解向量,中，即是否能共同构成可行解,/,solutionUNION(solution,x)/,将,x,和当前的解向量合并成,新的解向量，并修改目标函数,/,endif,repeat,return,end GREEDY,3.2,背包问题,1.,问题的描述,已知,n,种物品具有重量,(w,1,w,2,w,n,),和效益值,(p,1,p,2,p,n,),，,及一个可容纳,M,重量的背包；设当物品,i,全部或一部分,x,i,放入背包将得到,p,i,x,i,的效益，这里，,0,x,i,1,p,i,0,。,问题,：采用怎样的装包方法才能使装入背包的物品的,总效益最大,？,分析,：,装入背包的总重量,不能超过,M,如果所有物品的,总重量,不超过,M,，,即,M,，,则把,所有,的物品都装入背包中将获得最大可能的效益值,如果物品的总重量,超过了,M,，,则将有物品不能（部分,/,全部）装 入背包中。由于,0,xi1,，,所以可以把物品的一部分装入背包，故最终背包中可刚好装入重量为,M,的若干物品（整体或一部分）。这种情况下，如果背包没有被装满，则显然不能获得最大的效益值。,目标,：使装入背包的物品的,总效益,达到,最大,。,问题的形式描述,目标函数,：,约束条件,：,可 行 解,：满足上述约束条件的,任一,(x,1,x,2,x,n,),都是问题,的一个可行解,可行解可能为多个。,(x,1,x,2,x,n,),称为问题的一个,解向量,最 优 解,：能够使目标函数取,最大值,的可行解是问题的最优解,最优解也可能为多个。,例,3.1,背包问题的实例,设，,n=3,，,M=20,，,(p,1,p,2,p,3,)=(25,24,15),，,(w,1,w,2,w,3,)=(18,15,10),。,可能的可行解如下：,(x,1,x,2,x,3,),(1/2,1/3,1/4),16.5,24.25,/,没有装满背包,/,(1,2/15,0)20 28.2,(0,2/3,1)20 31,(0,1,1/2)20,31.5,2.,贪心策略求解,度量标准的选择：三种不同的选择,1,）以,目标函数,作为度量,即，每装入一件物品，就使背包获得,最大,可能的,效益增量,。,该度量标准下的处理规则是：,按效益值的,非增,次序将物品一件件地放入到背包；,如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在,剩下,的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。,如：若,M=2,背包外还剩两件物品,i,j,，,且有,(p,i,4,，,w,i,4),和,(,p,j,3,，,w,j,2),，,则下一步应选择,j,而非,i,放入背包：,p,i,/2=2,p,j,3,实例分析（例,3.1),p,1,p,2,p,3,首先将,物品,1,放入背包，此时,x,1,1,，,背包获得,p,1,25,的效益增量，同时背包容量减少,w,1,18,个单位，剩余空间,M=2,。,其次考虑,物品,2,和,3,。就,M=2,而言有，只能选择物品,2,或,3,的,一部分,装入背包。,物品,2,：若,x,2,2/15,，,则,p,2,x,2,16/5,3.1,物品,3,：若,x,3,2/10,，,则,p,3,x,3,3,为使背包的效益有最大的增量，应选择,物品,2,的,2/15,装包，即,x,2,2/15,最后，背包装满，,M=0,，,物品,3,不装包，即,x,3,0,。,背包最终可以获得,效益值,x,1,p,1,x,2,p,2,x,3,p,3,28.2 (,次优解,非问题的最优解,),2,）以,容量,作为度量标准,以,目标函数,作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入,“更多”,的物品。,改进：让背包,容量,尽可能慢地消耗，从而可以尽量装入“较多”的物品。,即，新的标准是：以,容量,作为度量,该度量标准下的处理规则：,按物品,重量的非降次序,将物品装入到背包；,如果正在考虑的物品放不进去，则只取其一部分装满背包；,实例分析（例,3.1),w,3,w,2,w,1,首先将,物品,3,放入背包，此时,x,3,1,，,背包容量减少,w,3,10,个单位，还剩余空间,M=10,。,同时,，,背包获得,p,3,15,的效益增量,。,其次考虑,物品,2,。就,M=10,而言有，也只能选择物品,2,的,一部分,装入背包。,下一步将放入,物品,2,的,10/15,装包，即,x,2,10/15,2/3,最后，背包装满,M=0,，,物品,1,将不能装入背包，故,x,1,0,。,背包最终可以获得,效益值,x,1,p,1,x,2,p,2,x,3,p,3,31 (,次优解,非问题的最优解,),存在的问题：效益值没有得到“最大程度”的增加,3,）最优的度量标准,影响背包效益值得因素：,背包的,容量,M,放入背包中的物品的重量及其可能带来的效益值,可能的策略,是：在背包效益值的增长速率和背包容量消耗速率之间取得,平衡,，即每次装入的物品应使它所占用的每一,单位容量,能获得当前最大的单位效益。,在这种策略下的,量度,是：已装入的物品的累计效益值与所用容量之比。,故，新的,量度标准,是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其后的装入）。,此时，将按照物品的单位效益值：,p,i,/,w,i,比值的非增次序考虑。,实例分析（例,3.1),p,1,/,w,1,p,3,/,w,3,p,2,/,w,2,首先，将,物品,2,放入背包，此时,x2,1,，,背包容量减少,w,2,15,个单位，还剩余空间,M=5,。,同时，,背包获得,p,2,24,的,效益增量,。,其次，在剩下的,物品,1,和,3,中，应选择物品,3,且就,M=5,而言有，,只能放入物品,3,的,一部分,到背包中。,即,x,3,5/10,1/2,最后，背包装满,M=0,，,物品,1,将不能装入背包，故,x,1,0,。,最终可以获得的背包,效益值,x,1,p,1,x,2,p,2,x,3,p,3,31.5 (,最优解,),3.,背包问题的贪心求解算法,算法,3.2,背包问题的贪心算法,procedure GREEDY,KNAPSACK(P,W,M,X,n),/P(1:n),和,W(1:n),分别含有按,P(i)/W(i)P(i,1)/W(i,1),排序的,n,件物品的效益值和重量。,M,是背包的容量大小，而,X(1:n),是解,向量,/,real P(1:n),W(1:n),X(1:n),M,cu;,integer I,n,X0/,将解向量初始化为,0/,cuM/cu,是背包的剩余容量,/,for i1 to n do,if W(i)cu then exit,endif,X(i)1,cu cu-W(i),repeat,if in then X(i)cu/W(i),endif,end GREEDY-KNAPSACK,4.,最优解的证明,即证明：由第三种策略所得到的贪心解是问题的,最优解,。,最优解,的含义：在满足约束条件的情况下，使目标函数取极（大或,小）值的可行解。,贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。,证明的,基本思想,：将此贪心解与（假设中的）任一最优解,相比较,。,如果这两个解相同，则显然贪心解就是最优解。,如果这两个解不同，就设法去找开始,不同,的第一个分量位置,i,，,然后设法用贪心解的这个,x,i,去,替换,最优解对应的分量,，,并证明最优解在分量代换前后总的效益值没有任何变化,(,且不违反约束条件,),。,可反复进行代换，直到代换后产生的最优解与贪心解完全一样。这一代换过程中，最优解的,效益值没有任何损失,，从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大,/,最小值。,从而得证：该,贪心解,即是问题的,最优解,。,定理,3.1,如果,p,1,/w,1,p,2,/w,2,p,n,/w,n,则算法,GREEDY-KNAPSACK,对于给定的背包问题实例生成一个最优解。,证明,：,设,X,=(x,1,x,2,x,n,),是,GREEDY-KNAPSACK,所生成的,贪心解,。,如果所有的,x,i,都等于,1,则显然,X,就是问题的,最优解,。否则，,设,j,是使,x,i,1,的最小下标。由算法的执行过程可知，,x,i,=1 1i,j,0 x,j,1,x,i,=0 j,in,反证：假设,X,不是问题的最优解，则必定存在一个可行解，设为,Y=(y,1,y,2,y,n,),使得：,且应有：,设,k,是使得,y,k,x,k,的最小下标，则有,y,k,x,k,，可分一下情况说明：,a),若,k0,当且仅当作业,i,在其截至期限以前被完成时，则获得,p,i,0,的效益。,问题,：求这,n,个作业的一个子集,J,，,其中的所有作业都可在其截至期限内完成。,J,是问题的一个可行解。,可行解,J,中的 所有作业的效益之和是 ，具有,最大效益值,的可行解是该问题的最优解。,分析：,目标函数：,约束条件：,所有的作业都应在其期限之前完成,如果,所有,的作业都能在其期限之内完成则显然可以获得,当前最大效益值；,否则，将有作业无法完成,决策应该执行哪些作业，以,获得最大可能的效益值。,例,3.2 n=4,，,(p,1,，,p,2,，,p,3,，,p,4,),(100,10,15,20),(d,1,，,d,2,，,d,3,，,d,4,),(2,1,2,1),。,可行解如下表所示：,问题的最优解是,。所允许的,处理次序,是：先处理作业,4,再处理作业,1,。,可行解,处理顺序,效益值,（,1,）,1,100,（,2,）,2,10,（,3,）,3,15,（,4,）,4,20,（,1,2,）,2,1,110,（,1,3,）,1,3或3,1,115,（,1,4,）,4,1,120,（,2,3,）,2,3,25,（,3,4,）,4,3,35,1.,带有限期的作业排序算法,1),度量标准的选择,以,目标函数,作为量度。,量度标准：下一个要计入的作业将是使得在满足所产生的,J,是,一个可行解的限制条件下让 得到最大增加的,作业。,处理规则：,按,p,i,的,非增次序,来考虑这些作业；,同时因受作业期限的限制，必须为作业安排合理,的,处理顺序,。,例：例,3.2,求解,首先令,J=,作业,1,具有当前的最大效益值，且,1,是可行解，所以作,业,1,计入,J,（一般情况下，假定至少有一个时间单元）。,在剩下的作业中，作业,4,具有最大效益值，且,1,4,也是,可行解，故作业,4,计入,J,，即,J=1,4,；,考虑,1,3,4,和,1,2,4,均不能构成新的可行解，作业,3,和,2,将被舍弃。,故，最后的,J=1,4,，加工顺序是：,4,，,1,。,最终效益值,120,（问题的,最优解,）,2),作业排序算法的概略描述,算法,3.3,procedure GREEDY-JOB(D,J,n),/,作业按,p,1,p,2,p,n,的次序输入，它们的期限值,D(i)1,1in,n1,。,J,是在它们的截止期限前完成的作业的集合,/,J1,/,用作业序号代表作业,/,for i2 to n do,if Ji,的,所有作业,能在它们的,截止期限前,完成,then JJi,endif,repeat,end GREEDY-JOB,2.,最优解证明,定理,3.2,算法,3.3,对于作业排序问题的解是问题的一个,最优解,证明,：,设,J,是由算法,3.3,所得的作业集合,贪心解,，,I,是一个,最优解,的作业集合。,若,I=J,，则,J,就是最优解；否则,，则至少存在两个作业,a,和,b,，,使得,aJ,且,bI,且 。（为什么）,并设,a,是,这样,的一个具有,最高效益值,的作业,(,由算法的处理规则可得：对于在,I,中而不在,J,中的作业所有,b,，,有：,p,a,p,b,),设,S,J,和,S,I,分别是,J,和,I,的可行的,调度表,。因为,J,和,I,都是可行解，故这样的调度表一定存在；,设,i,是既属于,J,又属于,I,地一个作业，并设,i,在调度表,S,J,中的调度时刻是,t,，,t+1,，,而在,S,I,中的调度时刻是,t,，,t+1,。,在,S,J,和,S,I,中作如下调整：,若,t,t,，,则将,S,J,中在,t,，,t+1,时刻调度的那个作业（如果有的话）与,i,相交换。如果,J,中在,t,，,t+1,时刻没有作业调度，则直接将,i,移到,t,，,t+1,调度。,新的调度表也是可行的。反之，,若,t,t,，,则在,S,I,中作类似的调换，即将,S,I,中在,t,，,t+1,时刻调度的那个作业（如果有的话）与,i,相交换。如果,I,中在,t,，,t+1,时刻没有作业调度，则直接将,i,移到,t,，,t+1,调度。,同样，新的调度表也是可行的。,对,J,和,I,中共有的所有作业作上述的调整。设调整后得到的调度表为,S,J,和,S,I,，,则在,S,J,和,S,I,中,J,和,I,中所有的,共有作业,将在,相同时间,被调度。,设,a,在,S,J,中的调度时刻是,t,a,t,a,+1,，,b,是,S,I,中该时刻调度的作业，则有,p,a,p,b,（为什么？）。,在,S,I,中，去掉作业,b,，,而去调度作业,a,，,得到的是作业集合,I=,（,I-b,）,a,的 一个可行的调度表，且,I,的效益值不小于,I,的效益值。而,I,中比,I,少了一个与,J,不同的作业。,重复上述的转换，可使,I,在,不减,效益值的情况下转换成,J,。,从而,J,至少有和,I,一样的效益值。所以,J,也是最优解。,证毕。,3.,如何判断,J,的可行性,方法一,：枚举法，检验,J,中作业所有可能的排列，对于任一种次序排,列的作业序列，判断这些作业是否能够在其期限前完成,若,J,中有,k,个作业，则将要检查,k!,个序列,分析：,对于一个给定,作业处理序列,i,1,i,2,i,k,由于作业,i,j,完成的,最早时间,是,j,，因此只要判断出,排列中的每个作业的期限有,d,ij,j,，就可得知,是一个允许的调度序列，从而,J,是一可行解。,反之，如果,排列中有一个作业有,d,ij,j,则,将是一个行不通的调度序列，因为至少作业,i,j,不能在其期限之前完成。,方法二,：检查,J,中作业的一个,特定序列,就可判断,J,的可行性：,即，按照,作业期限,的,非降次序,排列的作业序列即可完,成。,定理,3.3,设,J,是,k,个作业的集合，,i,1,i,2,i,k,是,J,中作业的一种排,列，它使得,d,i1,d,i2,d,ik,。,J,是一个可行解，,当且仅当,J,中的作业可以按照,的次序而又不违反任何一个期限的情况来处理,。,证明：,如果,J,中的作业可以按照,的次序而又不违反任何一个作业期限的情况来处理，则,J,是一个,可行解,现证,若,J,是一个可行解，,是否代表一个可行的调度序列？,J,是可行解,必存在一可行的调度序列,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,设,r,b,=,i,a,。则有：,b,a,且,d,ra,d,rb,故，在,中调换,r,a,与,r,b,，所得的新序列,s,1,s,2,s,k,的处理次序不违反任何一个期限，而,中位置,a,及,a,之前的作业均与,相同。,重复,上述过程，则可将,转换成,且不违反任何一个期限，故,是一个可行的调度序列,故定理得证,。,4.,带有限期的作业排序算法的实现,对当前正在考虑的作业,j,，,按限期大小采用一种,“插入排序”,的方式，尝试将其“插入”到一个按限期从小到大顺序构造的作业调度序列中，以此判断是否能够将作业,j,合并到当前部分解,J,中：,如果有合适的插入位置，则插入到序列中，形成新的可行解序列。,否则，舍弃该作业。,具体如下：,假设,n,个作业已经按照效益值从大到小的次序，即,p,1,p,2,p,n,的顺序排列好，每个作业可以在,单位时间,内完成，并具有相应的时间期限,d,i,；且至少有一个单位时间可以执行作业,首先，将作业,1,计入部分解,J,中，此时,J,是可行的；,然后，依次考虑作业,2,到,n,。,假设已经处理了,i-1,个作业，其中有,k,个作业计入了部分解,J,中：,J(1),J(2),J(k),，,且有,D(J(1)D(J(2)D(J(k),对当前正在考虑的作业,i,将,D(i),依次和,D(J(k),D(J(k-1),，,D(J(1),相比较。若,1,）找到位置,q,：,使得,D(i),D(J(l,),，,q,lk,，,且,D(J(q,),D(i,),q,D(i,),此时，若,D(J(l),l,q,lk,即,q,位置之后的所有作业均可,推迟,一个单位时间执行，而又不违反各自的执行期限。,执行,“,移位,”,处理：将,q,位置之后的所有作业后移一位，将作,业,i,插入,到位置,q,1,处，从而得到一个包含,k+1,个作业的新的可行解。,2,）若找不到这样的位置,q,，,作业,i,将被舍弃。,对,i,之后的其它作业重复上述过程，直到,n,个作业处理完毕。最后,J,中所包含的作业集合是此时算法的贪心解，根据定理,3.2,也是问题的最优解。,算法,3.4,带有限期和效益的单位时间的作业排序贪心算法,procedure JS(D,J,n,k),/n1,。,作业已按,p,1,p,2,p,n,的顺序排序。,D(1),D(n,),是期限值,J(i,),是最优解中的第,i,个作,业，,1ik,。,终止时，,D(J(i)D(J(i,1),，,1i,k/,integer D(0:n),J(0:n),i,k,n,r,D(0)J(0)0/,初始化,/,k1;J(1)1 /,计入作业,1/,for i2 to n do,/,按,p,的非增次序考虑作业,i,。找,i,的插入位置并检查可行性,/,rk,while D(J(r),D(i)and D(J(r)r do,/,D(J(r,)r/,rr-1,/,这样的,r,有,D(J(r,),r/,repeat,If D(J(r)D(i)and D(i),r then/,把,i,插入到,J,中,/,for ik to r+1 by-1 do,J(i+1)J(i)/,将插入点的作业后移一位,/,repeat,J(r+1)i;kk+1 /,将,i,计入,J,中,/,endif,repeat,end JS,另一退出条件是,D(J(r,),D(i,),而,D(J(r,)=r,计算时间分析,for i2 to n do,将循环,n-1,次,rk,while D(J(r),D(i)and D(J(r)r do,至多循环,k,次，,k,是当前计入,J,中的作业数,1,k,n-1,rr-1,repeat,If D(J(r)D(i)and D(i),r then,for ik to r+1 by-1 do,循环,k-r,次，,r,是插入点之前的位置,最坏情况下循环,k,次，插入到最头部,J(i+1)J(i),repeat,J(r+1)I;kk+1,endif,repeat,设,s,是最终计入,J,中的作业数，则算法,JS,所需要的总时间是,O(sn,),。,s,n,，,故,最坏情况,：,T,JS,=,(n,2,),，,特例情况：,p,i,=,d,i,=n-i+1,1in,最好情况,：,T,JS,=,(n),，,特例情况：,p,i,=,d,i,=i,1in,6.,一种“更快”的作业排序问题,判定作业,i,可行的另一种方法：,对于作业,i,，若还没有给,i,分配处理时间，则分配给它时间片,-1,，其中,是尽量取大且,-1,为空的时间片。,即：尽量推迟作业,i,的处理时间。这样在安排作业处理次序时不必每有一个作业加入就需移动,J,中已有的作业。,如果不存在这样的时间片，作业,i,被舍弃。,（如何按照该方法改进算法？）,使用不相交集合的,UNION,和,FIND,算法（见,1.4.3,节），可以将,JS,的计算时间降低到数量级接近,(n),。,（,略）,3.6,单源最短路径,1.,问题描述,最短路径问题：,每对结点之间的路径问题,特定线路下的最短路径问题,单源最短路径问题等,单源最短路径问题,已知一个,n,结点有向图,G=(V,E),和边的权函数,c(e),，,求由,G,中某指定结点,v,0,到其它各结点的最短路径。,假定边的权值为正。,例,3.10,如图所示。设,v,0,是起始点，求,v,0,到其它各结点的最短路径。,路径 长度,(1)v,0,v,2,10,(2)v,0,v,2,v,3,25,(3)v,0,v,2,v,3,v,1,45,(4)v,0,v,4,45,注：路径按照长度的,非降次序,给出,v,0,v,1,v,4,v,5,v,3,v,2,45,50,10,15,20,10,15,3,35,20,30,2.,贪心策略求解,1),度量标准,量度的选择：迄今已生成的,所有路径长度之和,为使之达到最小，其中任意一条路径都应具有最小长度：,假定已经构造了,i,条这样的最短路径，则下一条要构造的路径应是,下一条最短,的路径。,处理规则：按照,路径长度,的,非降次序,依次生成从结点,v,0,到其它各结点的最短路径。,例：,v,0,v,2,v,0,v,2,v,3,v,0,v,2,v,3,v,1,v,0,v,4,问题：如何对尚未生成的路径长度进行排序，以确定其中最短者？,2),贪心算法,设,S,是已经对其生成了最短路径的,结点集合,（包括,v,0,),。,对于当前不在,S,中的结点,w,，记,DIST(w),是从,v,0,开始，,只经过,S,中的结点而在,w,结束的那条最短路径的长度。,则有，,S,W,如果下一条最短路径是到结点,u,，则这条路径是从结点,v,0,出发,，,在,u,处终止，且,只经过,那些在,S,中的结点,即由,v,0,至,u,的这条最短路径上的所有,中间结点,都是,S,中的结点,，证明如下：,设,w,是这条路径上的任意中间结点，则从,v,0,到,u,的路径也包含了一条从,v,0,到,w,的路径，且其长度小于从,v,0,到,u,的路径长度。,v,0,s,1,s,2,w,s,m-1,u,均在,S,中,根据,生成规则：,最短路径是按照路径长度的非降次序生成的，因此从,v,0,到,w,的最短路径应该已经生成。从而,w,也应该在,S,中。,故,不存在,不在,S,中的中间结点。,所生成的下一条路径的终点,u,必定是所有不在,S,内的结点中具有最小,DIST(u,),值,的结点。,如果选出了这样结点,u,并生成了从,v,0,到,u,的最短路径之后，结点,u,将成为,S,中的一个成员。此时，那些从,v,0,出发，只经过,S,中的结点并且在,S,外的结点,w,处结束的最短路径,长度,可能会,减,小,DIST(w),的值变小：,这些,长度发生改变,的路径,，必定是一条从,v,0,出发,，经过,u,然后到,w,的,更短,的路,径,。,根据,DIST(w),的定义，,DIST(w,),所表示的最短路径上，所有中间,结点都在,S,中；故只考虑,E,和 的情况,对于,从,v,0,至,w,，且经过最后一个中间结点为,u,的,最短路径,，,有：,DIST(w,)=DIST(u)+,c(u,w,),随着,u,的加入，,DIST(w,),调整为,DIST(w,)=,min(DIST(w),DIST(u,)+,c(u,w,),S,W,u,v0,算法,3.10,生成最短路径的贪心算法,procedure SHORTEST-PATHS(v,COST,DIST,n),/G,是一个,n,结点有向图，它由其成本邻接矩阵,COST(n,n),表示。,DIST(j,),被置,从结点,v,到结点,j,的最短路径长度，这里,1jn,。,DIST(v),被置成零,/,boolean,S(1:n);real COST(1:n,1:n),DIST(1:n),integer,u,v,n,num,i,w,for i,1 to n do/,将集合,S,初始化为空,/,S(i)0;DIST(i),COST(v,i,),/,若 ，则,DIST(i,)=,/,repeat,S(v)1;DIST(v)0 /,结点,v,计入,S/,for num2 to n-1 do/,确定由结点,v,出发的,n-1,条路,/,选取结点,u,它使得,DIST(u)=,S(u)1/,结点,u,计入,S/,for,所有,S(w),0,的结点,w do /,修改,DIST(w)/,DIST(w)=min(DIST(w),DIST(u)+COST(u,w),repeat,repeat,end SHORTEST-PATHS,3),计算时间,算法,3.10,的计算时间是：,(n,2,),for i,1 to n do,S(i)0;DIST(i)COST(v,i),repeat,for num2 to n-1 do,选取结点,u,它使得,DIST(u)=,S(u)1,for,所有,S(w),0,的结点,w do,DIST(w)=min(DIST(w),DIST(u)+COST(u,w),repeat,repeat,最短路径算法的时间复杂度,由于任何一条边,都有可能,是最短路径中的边，所以求任何最短路径的算法都必须至少检查图中的每条边一次，所以这样的算法的最小时间是,(e),。,邻接矩阵表示的图：,(n,2,),例,3.11,求下图中从,v,1,出发到其余各结点的最短路径,v,1,v,2,v,4,v,3,v,5,v,6,v,7,20,50,25,70,50,70,10,50,55,40,30,25,图的成本邻接矩阵：,0 20 50 30 +,+,+,+,0 25,+,+,70,+,+,+,0 40 25 50,+,+,+,+,0 55,+,+,+,+,+,+,0 10 70,+,+,+,+,+,0 50,+,+,+,+,+,+,0,算法的执行轨迹描述,迭代,选取的结点,S,DIST,(1)(2)(3)(4)(5)(6)(7),置初值,1,2,3,4,5,2,4,3,5,6,1,1,2,1,2,4,1,2,4,3,1,2,4,3,5,1,2,4,3,5,6,0 20 50 30 +,+,+,0,20,45,30 +,90,+,0 20 45,30,85,90 +,0 20,45,30,70,90 +,0 20 45 30 70 90,140,0 20 45 30 70 90,130,算法的执行在有,n-1,个结点加入到,S,中后终止，此时求出了,v,0,至其它各结点的最短路径。,问题：如何求出所有这些最短路径？,3.,最短路径生成树,对于无向连通图,G,，,由结点,v,到其余各结点的最短路径的边构成,G,的一棵,生成树,，称为,最短路径生成树,。,注：不同起点,v,的生成树可能不同。,2,1,3,5,6,7,4,8,55,5,25,40,35,15,10,50,20,45,30,2,1,3,5,6,7,4,8,5,25,40,15,10,20,30,2,1,3,5,6,7,4,8,55,5,25,15,10,45,30,原始图 由结点,1,出发的最短路径生成树 最小成本生成树,3.4,最优归并模式,1.,问题的描述,1,）两个文件的归并问题,两个已知文件的一次归并所需的计算时间,O(,两个文件的元素总数,),例：,n,个记录的文件,(n+m),个记录的文件,m,个记录的文件,(n+m),2,）,多个文件的归并,已知,n,个文件，将它们归并成一个单一的文件,例：假定文件,X,1,，,X,2,，,X,3,，,X,4,，,采用两两归并的方式，可能的归并模式有：,X,1,+X,2,=Y,1,+X,3,=Y,2,+X,4,=Y,3,X,1,+X,2,=Y,1,+,Y,3,X,3,+X,4,=Y,2,二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归并的模式，最终得到一个完整的记录文件。,二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，称之为二元归并树。,如,60,50,30,20,10,X,1,Z,1,X,X,3,X,2,数字代表文件长度,归并树的构造,外结点：,n,个原始文件,内结点：一次归并后得到的文件,在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示的文件归并成其本身所代表的文件,不同的归并顺序所需的计算时间是不同的。,例,3.5,已知,X,1,X,2,X,3,是分别为,30,、,20,、,10,个记录长度的已分类文件。将这,3,个文件归并成长度为,60,的文件。可能的归并过程和相应的记录移动次数如下：,问题：采用怎样的归并顺序才能使归并过程中元素的移动次数最小（或执行的速度最快）,X,X,3,X,2,X,1,移动,50,次,移动,60,次,X,X1,X,2,X,3,移动,30,次,移动,60,次,总移动次数：,110,次,总移动次数：,90,次,2.,贪心求解,1),度量标准的选择,任意两个文件的归并所需的,元素移动次数,与这两个文件的,长度之和,成,正比；,度量标准,：每次归并尺寸最小的两个文件进行归并；,处理规则,：每次选择长度最小的两个文件进行归并。,95,35,5,20,30,60,30,15,10,F,4,F,3,Z,1,Z,2,Z,4,Z,3,F,1,F,5,F,2,(F,1,F,2,F,3,F,4,F,5,)=(20,30,10,5,30),2),目标函数的定义,目标,：元素移动的次数最少,分析：为得到归并树根结点表示的归并文件，外部结点中每个文件的记录需要移动的次数该外部结点到根的距离，即根到该外部结点路径的长度。如，,F,4,：,则,F,4,中所有记录在整个归并过程中移动的总量,|F,4,|*3,带权外部路径长度,：记,d,i,是由根到代表文件,F,i,的外部结点的距离，,q,i,是,F,i,的长度，则这棵树所代表的归并过程中元素移动总量是：,，称为这棵树的,带权外部路径长度,最优的二路归并模式,：与一棵具有,最小带权外部路径长度,的二元归并树相对应。,F,4,Z,1,Z,2,Z,4,算法,3.6,生成二元归并树的算法,procedure TREE(L,n),/L,是,n,个单结点的二元树表,/,for i,1 to n-1 do,call GETNODE(T),/,构造一颗新,树,T/,LCHILD(T)LEAST(L),/,从表,L,中选当前根,WEIGHT,最小的树，,并从中删除,/,RCHILD(T)LEAST(L),WEIGHT(T)WEIGHT(LCHILD(T)+WEIGHT(RCHILD(T),call INSERT(L,T),/,将归并的树,T,加入到表,L,中,/,repeat,return(LEAST(L),/,此时，,L,中的树即为归并的结果,/,end TREE,例,3.6,已知六个初始文件，长度分别为：,2,3,5,7,9,13,。,采用算法,TREE,，,各阶段的工作状态如图所示：,L,迭代,2,3,5,7,9,13,0,2,3,5,7,9,13,1,5,2,3,5,7,9,13,2,5,10,2,3,5,7,9,13,3,5,10,16,2,3,5,7,9,13,4,5,10,16,23,2,3,5,7,9,13,5,5,10,16,23,39,时间分析,1),循环体：,n-1,次,2)L,以有序序列表示,LEAST(L):,(1),INSERT(L,T):,(n),总时间,：,(n,2,),3)L,以,min-,堆表示,LEAST(L):,(,logn,),INSERT(L,T):,(,logn,),总时间,：,(,nlogn,),3.,最优解的证明,定理,3.4,若,L,最初包含,n1,个单结点的树，这些树有,WEIGHT,值为,(q,1,q,2,q,n,),，,则算法,TREE,对于具有这些长度的,n,个文件生成一棵最优的二元归并树。,证明：,归纳法,证明,当,n=1,时，返回一棵没有内部结点的树。定理得证。,假定算法对所有的,(q,1,q,2,q,m,),，,1m,n,生成一棵最优二元归并树。,对于,n,假定,q,1,q,2,q,n,则,q,1,和,q,2,将是在,for,循环的第一次迭代中首先选出的具有最小,WEIGHT,值的两棵树（的,WEIGHT,值）；如图所示，设,T,是由这样的两棵树构成的子树：,q,1,q,2,q,1,+q,2,T,设,T,是一棵对于,(q,1,q,2,q,n,),的,最优二元归并树,。,设,P,是,T,中距离根,最远,的一个,内部结点,。,若,P,的两棵子树不是,q,1,和,q,2,，,则用,q,1,和,q,2,代换,P,当前的子树而不会增加,T,的带权外部路径长度。,故，,T,应是最优归并树中的子树。,则在,T,中用一个权值为,q,1,q,2,的外部结点代换,T,，,得到的是一棵关于,(q,1,q,2,q,n,),最优归并树,T”,。,而由归纳假设，在用权值为,q,1,q,2,的外部结点代换了,T,之后，过程,TREE,将针对,(q,1,q,2,q,n,),得到一棵最优归并树。将,T,带入该树，根据以上讨论，将得到关于,(q,1,q,2,q,n,),的最优归并树。,故，,TREE,生成一棵关于,(q,1,q,2,q,n,),的,最优归并树,。,5.k,路归并模式,每次,同时,归并,k,个文件。,k,元归并树：可能需要增加,“虚”,结点，以补充不足的外部结点。,如果一棵树的所有内部结点的度都为,k,，,则外部结点数,n,满