贪心方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第四章 贪心方法,10/22/2026,本章教学要求及重点难点,理解贪心方法的基本思想,掌握背包问题的求解方法,掌握带有限期的作业排序的基本方法,掌握用贪心方法求解单源点最短路径的基本方法。,重点：用贪心方法求背包问题及带有限期作业排序；,难点：用贪心方法求单源点最短路径。,10/22/2026,4.1 一般方法,1.问题的一般特征,问题有,n,个输入，问题的解是由这n个输入的某个,子集,组成，这个子集必须满足某些事先给定的条件。,约束条件,：子集必须满足的条件；,可行解,：满足约束条件的子集；可行解可能不唯一；,目标函数,：用来衡量可行解优劣的标准，一般以函数的形式给出；,最优解,：能够使目标函数取极值（极大或极小）的可行解。,分类,：根据描述问题约束条件和目标函数的,数学模型,的特性和问题的,求解方法,的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。,最优化问题求解,贪心方法,：一种改进的,分级,的处理方法，可对满足上述特征的某些问题方便地求解。,10/22/2026,例找零钱 一个小孩买了价值少于1元的糖，并将1元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为25分、10分、5分及1分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。,选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。,假设需要找给小孩67分，首先入选的是两枚25分的硬币，第三枚入选的不能是25分的硬币，否则将不可行（零钱总数超过67分），第三枚应选择10分的硬币，然后是5分的，最后加入两个1分的硬币。,贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）,10/22/2026,2.贪心方法的一般策略,问题的一般特征：问题的解是由,n,个输入的、满足某些事先给定的条件的子集组成。,1）一般方法,根据题意，选取一种,度量标准,。然后按照这种度量标准对n个输入,排序,，并按序一次输入一个量。,如果这个输入和当前已构成在这种量度意义下的,部分最优解,加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的,新的部分解,。,2）贪心方法,这种能够得到某种量度意义下的最优解的,分级处理,方法称为,贪心方法,注：,贪心解 最优解,直接将目标函数作为,量度标准,也不一定能够得到问题的最优解,3）使用贪心策略求解的关键,选取能够得到问题最优解的量度标准。,10/22/2026,问题的形式描述,目标函数,：,约束条件,：,可 行 解,：满足上述约束条件的,任一集合,(x,1,x,2,x,n,),都是问题,的一个可行解可行解可能为多个。,(x,1,x,2,x,n,)称为问题的一个,解向量,最 优 解,：能够使目标函数取,最大值,的可行解是问题的,最优解最优解也可能为多个。,10/22/2026,例4.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,10/22/2026,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,10/22/2026,实例分析（例4.1),(p,1,p,2,p,3,)=(25,24,15)，(w,1,w,2,w,3,)=(18,15,10),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/53.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 (,次优解,非问题的最优解),10/22/2026,2）以,容量,作为度量标准,以,目标函数,作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入,“更多”,的物品。,改进：让背包,容量,尽可能慢地消耗，从而可以尽量装入“更多”的物品。,即，新的标准是：以,容量,作为度量标准,该度量标准下的处理规则：,按物品,重量的非降次序,将物品装入到背包；,如果正在考虑的物品放不进去，则只取其一部分装满背包；,10/22/2026,实例分析（例4.1),(p,1,p,2,p,3,)=(25,24,15)，(w,1,w,2,w,3,)=(18,15,10),w,3,w,2,w,1,首先将,物品3,放入背包，此时,x,3,1,，背包容量减少w,3,10个单位，还剩余空间,M=10。同时，,背包获得,p,3,15,的效益增量,。,其次考虑,物品1和2,。就,M=10而言有，也只能选择物品1或2的,一部分,装入背包。,为使背包的按照“统一”的规则，下一步将放入,物品2,的10/15装包，即,x,2,10/152/3,最后，背包装满,M=0，故,物品1,将不能装入背包，,x,1,0,。,背包最终可以获得,效益值,x,1,p,1,x,2,p,2,x,3,p,3,31 (,次优解,非问题的最优解),存在的问题：效益值没有得到“最大”的增加,10/22/2026,3）最优的度量标准,影响背包效益值得因素：,背包的,容量,M,放入背包中的物品的重量及其可能带来的效益值,可能的策略,是：在背包效益值的增长速率和背包容量消耗速率之间取得,平衡,，即每次装入的物品应使它所占用的每一,单位容量,能获得当前最大的单位效益。,在这种策略下的,量度,是：已装入的物品的累计效益值与所用容量之比。,故，新的,量度标准,是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其后的装入）。,此时，将按照物品的单位效益值：p,i,/w,i,比值（密度）的非增次序考虑。,10/22/2026,实例分析（例4.1),(p,1,p,2,p,3,)=(25,24,15)，(w,1,w,2,w,3,)=(18,15,10),p,1,/,w,1,p,3,/,w,3,p,2,/,w,2,首先将,物品2,放入背包，此时,x21,，背包容量减少w,2,15个单位，还剩余空间,M=5。同时，,背包获得,p,2,24,的效益增量,。,其次考虑,物品1和3,。此时，应选择物品3,且就,M=5而言有，也只能放入物品3的,一部分,到背包中。,即,x,3,5/101/2,最后，背包装满,M=0，故,物品1,将不能装入背包，,x,1,0,。,背包最终可以获得,效益值,x,1,p,1,x,2,p,2,x,3,p,3,31.5 (,最优解,),10/22/2026,3.背包问题的贪心求解算法,算法4.2 背包问题的贪心算法,procedure GREEDYKNAPSACK(P,W,M,X,n),/p(1:n)和w(1:n)分别含有按P(i)/W(i)P(i1)/W(i1)排序的n,件物品的效益值和重量。M是背包的容量大小，而x(1:n)是解,向量/,real P(1:n),W(1:n),X(1:n),M,cu;,integer I,n,X0/将解向量初始化为空/,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,10/22/2026,4.最优解的证明,即证明：由第三种策略所得到的贪心解是问题的,最优解,。,最优解,的含义：在满足约束条件的情况下，可使目标函数取极（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。,证明的,基本思想,：将此贪心解与（假设中的）任一最优解,相比较,。,如果这两个解相同，则显然贪心解就是最优解。否则，,这两个解不同，就去找开始,不同,的第一个分量位置,i,，然后设法用贪心解的这个x,i,去,替换,最优解的那个x,i,，并证明最优解在分量代换前后总的效益值没有任何变化。,可反复进行代换，直到新产生的最优解与贪心解完全一样。这一代换过程中，最优解的,效益值没有任何损失,，从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大/最小值。,从而得证：该,贪心解,也即问题的,最优解,。,10/22/2026,定理4.1 如果p,1,/w,1,p,2,/w,2,p,n,/w,n,则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。,证明,：,设,X,=(x,1,x,2,x,n,)是GRDDDY-KNAPSACK所生成的,贪心解,。,如果所有的x,i,都等于,1,则显然X就是问题的,最优解,。否则，,设j是使x,i,1的最小下标。由算法可知，,x,i,=1 1ij,0 x,j,1,x,i,=0 jin,若X不是问题的最优解，则必定存在一个可行解,Y=(y,1,y,2,y,n,),使得：,且应有：,10/22/2026,设k是使得y,k,x,k,的最小下标，则有y,k,x,k,:,a)若k0,当且仅当作业i在其截至期限以前被完成时，则获得,p,i,0的效益。,问题,：求这n个作业的一个子集J，其中的所有作业都可在其截至期限内完成。J是问题的一个可行解。,可行解J中的 所有作业的效益之和是 ，具有,最大效益值的,可行解是该问题的最优解。,如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益值；否则，将有作业无法完成决策应该执行哪些作业，以获得最大可能的效益值。,目标函数：,约束条件：,所有的作业都应在其期限之前完成,10/22/2026,例4.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,10/22/2026,1.带有限期的作业排序算法,1)度量标准的选择,以目标函数 作为量度。,量度标准：下一个要计入的作业将是使得在满足所,产生的J是一个可行解的限制条件下让,得到最大增加的作业。,处理规则：按p,i,的非增次序来考虑这些作业。,10/22/2026,例：例4.2求解,(p,1,，p,2,，p,3,，p,4,)(100,10,15,20),(d,1,，d,2,，d,3,，d,4,)(2,1,2,1),首先令,J=,作业1具有当前的最大效益值，且1是可行解，所以作业1计入J；,在剩下的作业中，作业4具有最大效益值，且1,4也是可行解，故作业4计入J，即J=1,4；,考虑1,3,4和1,2,4均不能构成新的可行解，作业3和2将被舍弃。,故最后的J=1,4，最终效益值120（问题的,最优解,）,10/22/2026,2)作业排序算法的概略描述,算法4.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,10/22/2026,2.最优解证明,定理4.2 算法4.3对于作业排序问题总是得到问题的一个,最优解,证明,：,设,J,是由算法所得的,贪心解,作业集合，,I,是一个,最优解,的作业集合。,若I=J，则J就是最优解；否则,，即至少存在两个作业,a,和,b,，使得aJ且 ,bI且 。,并设a是这样的一个具有,最高效益值,的作业，且由算法的处理规则可得：对于在I中而不在J中的作业所有b，有：,p,a,p,b,10/22/2026,设,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,中作如下调整：,若,tt，,则将S,J,中在t，t+1时刻调度的那个作业（如果有的话）与i相交换。如果J中在t，t+1时刻没有作业调度，则直接将i移到t，t+1调度。新的调度表也是可行的。反之，,若,tt,，则在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中,共有,的所有作业将在相同的时间被调度。,10/22/2026,设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也是最优解。,证毕。,10/22/2026,3.如何判断J的可行性,方法一,：检验J中作业所有可能的排列，对于任一种次序排列的作,业排列，判断这些作业是否能够在其期限前完成若J,中有k个作业，则将要检查,k!,个序列,方法二,：检查J中作业的一个,特定序列,就可判断J的可行性：,对于所给出的一个排列,i,1,i,2,i,k,由于作业i,j,完成的,最早时间是j，因此只要判断出,排列中的每个作业,d,ij,j，就可得知,是一个允许的调度序列，从而J是一个,可行解。反之，如果排列中有一个d,ij,j,则,将是一个,行不通的调度序列，因为至少作业i,j,不能在其期限之前完,成。,这一检查过程可以只通过检验J中作业的一种特殊的排列：按照作业,期限的非降次序,排列的作业序列即可完成。,10/22/2026,定理4.3 设J是k个作业的集合，,i,1,i,2,i,k,是J中作业的一种排列，它使得d,i1,d,i2,d,ik,。J是一个可行解，,当且仅当,J中的作业可以按照,的次序而又不违反任何一个期限的情况来处理。,证明：,如果J中的作业可以按照,的次序而又不违反任何一个期限的情况来处理，则J是一个可行解,若J是一个可行解，则必存在序列,r,1,r,2,r,k,，使得d,rj,j,1jk。,若,，则即是可行解。否则，,，令a是使得r,a,i,a,的最小下标，并设r,b,=i,a,。则有：,ba,且,d,ra,d,rb,(为什么?),在,中调换r,a,与r,b,，所得的新序列,s,1,s,2,s,k,的处理次序不违反任何一个期限。,重复上述过程，则可将,转换成,且不违反任何一个期限。故,是一个,可行,的调度序列,故定理得证,。,10/22/2026,i,1,i,2,i,a,i,c,i,k,r,1,r,2,r,a,r,b,r,k,ab,d,ra,d,rb,10/22/2026,5.带有限期的作业排序算法的实现,对当前正在考虑的作业j，按限期大小采用一种,“插入排序”,的方式，尝试将其“插入”到一个按限期从小到大顺序构造的作业调度序列中，以此判断是否能够合并到当前部分解J中。如果可以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。,具体如下：,假设n个作业已经按照效益值从大到小的次序，即p,1,p,2,p,n,的顺序排列好，每个作业可以在,单位时间,内完成，并具有相应的时间期限；且至少有一个单位时间可以执行作业,首先，将作业1存入部分解J中，此时J是可行的；,然后，依次考虑作业2到n。假设已经处理了i-1个作业，其中有k个作业计入了部分解J中：J(1),J(2),J(k)，且有,D(J(1)D(J(2)D(J(k),10/22/2026,对当前正在考虑的作业i,将D(i)依次和D(J(k),D(J(k-1),，D(J(1)相比较，直到找到位置q：使得,D(i)D(J(,l,)，q,l,k，且,D(J(q)D(i),此时，若,D(J(,l,),l,q,l,k,即说明q位置之后的所有作业均可,推迟,一个单位时间执行，而又不违反各自的执行期限。,最后，将q位置之后的所有作业后移一位，将作业i,插入,到位置q1处，从而得到一个包含k+1个作业的新的可行解。,若找不到这样的q，作业i将被舍弃。,对i之后的其它作业重复上述过程直到n个作业处理完毕。最后J中所包含的作业集合是此时算法的贪心解，也是问题的最优解。,10/22/2026,算法4.4 带有限期和效益的单位时间的作业排序贪心算法,procedure JS(D,J,n,k),/D(1),D(n)是期限值。n1。作业已按p,1,p,2,p,n,的顺序排序。J(i)是最优解中的第i个作,业，1ik。终止时，D(J(i)D(J(i1)，1ik/,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的位置并检查插入的可行性/,rk,while D(J(r)D(i)and D(J(r)r do,rr-1,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,endif,repeat,end JS,10/22/2026,计算时间分析,for i2 to n do,将循环,n-1,次,rk,while D(J(r)D(i)and D(J(r)r do,至多循环,k,次，,k是当前计入J中的作业数 ,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是插入点的位置 ,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)，特例情况：d,i,=i,1in,10/22/2026,6.一种“更快”的作业排序问题,使用不相交集合的,UNION,和,FIND,算法（见1.4.3节），可以将JS的计算时间降低到数量级接近,(n),。,（略）,10/22/2026,例4.3 设n=5,(p1,p5)=(20,15,10,5,1),(d1,d5)=(2,2,1,3,3)。,J,已分配时间片,正被考虑作业,动作,0,无,1,分配1,2,1,1,2,2,分配0,1,1,2,0,1,1,2,3,不适合，舍弃,1,2,0,1,1,2,4,分配2,3,1,2,4,0,1,1,2,2,3,5,舍弃,最优解是J1,2,4,10/22/2026,4.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,10/22/2026,二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归并的模式，最终得到一个完整的记录文件。,二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，称之为二元归并树。,如,归并树的构造,外结点：n个原始文件,内结点：一次归并后得到的文件,在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示的文件归并成其本身所代表的文件,60,50,30,20,10,X,1,Z,1,X,X,3,X,2,10/22/2026,不同的归并顺序带来的计算时间是不同的。,例4.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次,10/22/2026,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),10/22/2026,2)目标函数,目标,：元素移动的次数最少,实例：为得到归并树根结点表示的归并文件，外部结点中每个文件记录需要移动的次数该外部结点到根的距离，即根到该外部结点路径的长度。如，,F,4,：,则F,4,中所有记录在整个归并过程中移动的总量,|F,4,|*3,带权外部路径长度,：记d,i,是由根到代表文件Fi的外部结点的距离，q,i,是F,i,的长度，则这棵树的代表的归并过程的元素移动总量是：,最优的二路归并模式,：与一棵具有,最小外部带权路径长度,的二元树相对应。,F,4,Z,1,Z,2,Z,4,10/22/2026,算法4.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,10/22/2026,例4.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,10/22/2026,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,10/22/2026,时间分析,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),10/22/2026,3.最优解的证明,定理3.4 若L最初包含n1个单结点的树，这些树有WEIGHT值为(q,1,q,2,q,n,)，则算法TREE对于具有这些长度的n个文件生成一棵最优的二元归并树。,证明：,归纳法,证明,当n=1时，返回一棵没有内部结点的树。定理得证。,假定算法对所有的(q,1,q,2,q,n,)，1mn,生成一棵最优二元归并树。,对于n,假定q,1,q,2,q,n,则q,1,和q,2,将是在for循环的第一次迭代中首先选出的具有最小WEIGHT值的两棵树（的WEIGHT值）；如图所示，T是由这样的两棵树构成的子树：,q,1,q,2,q,1,+q,2,T,10/22/2026,设,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,)的,最优归并树,。,10/22/2026,5.k路归并模式,每次,同时,归并,k,个文件。,k元归并树：可能需要增加,“虚”,结点，以补充不足的外部结点。,如果一棵树的所有内部结点的度都为k，则外部结点数n满足 n mod(k-1)=1,对于满足 n mod(k1)=1的整数n，存在一棵具有n个外部结点的k元树T，且T中所有结点的度为k。,至多需要增加,k-2,个外部结点。,k路最优归并模式得贪心规则：每一步选取,k,棵具有最小长度的子树归并。,10/22/2026,4.5 最小生成树,1.问题的描述,生成树,：设G=(V,E)是一个无向连通图。如果G的生,成子图T=(V,E)是一棵树，则称T是G的一棵,生成树(spanning tree),最小生成树:,2.贪心策略,度量标准：选择能使迄今为止所计入的边的,成本和,有,最小,增加,的那条边。,Prim算法,Kruskal算法,10/22/2026,3.Prim算法,策略：使得迄今所选择的边的集合A构成一棵树；对将要计入到A中的下一条边(u,v)，应是E中一条当前不在A中且使得A,(u,v)也是一棵树的最小成本边。,1,4,6,2,5,3,10,30,20,45,25,55,40,50,15,35,1,2,1,6,2,1,6,2,3,1,6,2,3,4,边,(1,2),(2,6),(3,6),(6,4),成本,10,25,15,20,10/22/2026,1,4,6,2,5,3,10,20,25,15,35,边,(3,5),成本,35,V(T,P,)=1,2,3,4,5,6,E(T,P,)=(1,2),(2,6),(3,5),(4,6),(3,6),10/22/2026,算法4.7 Prim最小生成树算法,procedure PRIM(E,COST,n,T,mincost),/E是G的边集。COST(n,n)是n结点图G的成本邻接矩阵，矩阵元素COST(i,j)是一个正实数，如果不存在边(i,j)，则为。计算一棵最小生成树并把它作为一个集合存放到数组T(1:n-1,2)中(T(i,1),T(i,2)是最小成本生成树的一条边。最小成本生成树的总成本最后赋给mincost/,real COST(n,n),mincost,integer NEAR(n),n,i,k,l,T(1:n-1,2),(k,l),具有最小成本的边,mincostCOST(k,l),(T(l,1),T(l,2)(k,l),for i1 to n do/将NEAR置初值/,if COST(i,l)COST(i,k)then NEAR(i)l,else NEAR(i)k,endif,repeat,10/22/2026,NEAR(k)NEAR(l)0,for i2 to n-1 do/找T的其余n-2条边/,设j是NEAR(j)0 且COST(j,NEAR(j)最小的下标,(T(i,1),T(i,2)(j,NEAR(j),mincostmincost+COST(j,NEAR(j),NEAR(j)0,for k1 to n do/修改NEAR/,if NEAR(k)0 and COST(k,NEAR(k)COST(k,j),then NEAR(k)j,endif,repeat,repeat,if mincost then print(no spanning tree)endif,end PRIM,10/22/2026,计算复杂性：,第3行花费,(e)(e=|E|)时间，第4行花费,(1)时间；第69行的循环花费,(n)时间；第12行和第1620行的循环要求,(n)时间，因此第1121行循环要花费,(n)时间。,所以PRIM算法具有 的时间复杂度,10/22/2026,另一种PRIM算法,最小生成树中包含了与每个结点v相关的一条最小成本边,证明略,方法：从一棵包含任何一个随意指定的结点而没有边的树开始这一算法，然后再逐条增加边。,10/22/2026,4.Kruskal算法,（连通）图的边按成本的非降次序排列，下一条计入生成树T中的边是还没有计入的边中具有最小成本、且和T中现有的边不会构成环路的边。,1,4,6,2,5,3,10,30,20,45,25,55,40,50,15,35,1,2,1,6,2,1,6,2,3,1,6,2,3,4,边,(1,2),(3,6),(4,6),(2,6),成本,10,15,20,25,1,6,2,3,4,5,6,3,4,5,3,4,5,4,5,5,10/22/2026,1,4,6,2,5,3,10,20,25,15,35,边,(1,4),(3,5),成本,30 舍弃,35,V(T,K,)=1,2,3,4,5,6,E(T,K,)=(1,2),(2,6),(3,5),(4,6),(3,6),10/22/2026,算法4.9 Kruskal算法,procedure KRUSKAL(E,COST,N,T,mincost),/G有n个结点，E是G的边集。COST(u,v)是边(u,v)的成本。T是最小成本生成树的边集，mincost是它的成本/,real mincost,COST(1:n,1:n);integer PARENT(1:n),T(1:n-1,2),n,以边成本为元素构造一个min堆,PARENT,1/每个结点都在不同的集合中/,imincost0,while in-1 and 堆非空 do,从堆中删去最小成本边(u,v)并重新构造堆,jFIND(u);kFIND(v),if(jk)then ii+1,T(i,1)u;T(i,2)v,mincostmincost+COST(u,v),call UNION(j,k),endif,repeat,if in-1 then print(no spanning tree)endif,return,end KRUSKAL,10/22/2026,注：,边集以min-堆的形式保存，一条当前最小成本边可以在,(loge)的时间内找到；,当且仅当图G是不连通的，i,n-1；此时算法具有最坏的执行时间；,算法的计算时间是,(eloge),10/22/2026,4.6 单源点最短路径,1.问题描述,最短路径问题：,每对结点之间的路径问题,特定线路下的最短路径问题,单源最短路径问题等,单源最短路径问题,已知一个n结点有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v,0,到其它各结点的最短路径。,假定边的权值为正。,10/22/2026,例4.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,45,10,15,20,10,15,3,35,20,30,10/22/2026,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,10/22/2026,2)贪心算法,设,S,是已经对其生成了最短路径的,结点集合,（包括v0)。,对于当前不在S中的结点w，记,DIST(w),是从v0开始，,只经过,S中的结点而在w结束的那条最短路径的长度。,则有，,S,W,10/22/2026,如果下一条最短路径是到结点u，则这条路径是从结点v0出发在u处终止，且,只经过,那些在S中的结点,即由v0至u的这条最短路径上的所有,中间结点,都是S中的结点:,设,w,是这条路径上的任意中间结点，则从v0到u的路径也包含了一条从v0到w的路径，且其长度小于从v0到u的路径长度。,v0,s1,s2,w,sm-1,u,均在S中,根据,生成规则：,最短路径是按照路径长度的非降次序生成的，因此从v0到w的最短路径应该已经生成。从而w也应该在S中。,故,不存在,不在S中的中间结点。,所生成的下一条路径的终点u必定是所有不在S内的结点中且具有最小距离DIST(u)的结点。,10/22/2026,如果选出了这样结点u并生成了从v0到u的最短路径之后，结点u将成为S中的一个成员。此时，那些从v0出发，,只经过,S中的结点并且在S外的结点w处结束的最短路径可能会,减少,DIST(w)的值变小：,如果这样的路径的长度发生了改变，则这些路径必定是一条从v0开始，经过u然后到w的,更短,的路所致。,根据DIST(w)的定义，它所表示的v0至w的最短路径上的所有中间结点都在S中；,只考虑E和 的情况,u是从v0至w的最短路径上所经过的结点。,则有：,DIST(w)=DIST(u)+c(u,w),S,W,u,v0,10/22/2026,算法4.10 生成最短路径的贪心算法,proce