算法与设计贪心法

第三章贪心方法什么是贪心方法背包问题带有期限的作业排序最优归并模式最小生成树单源点最短路径3.1什么是贪心方法A(1)A(2)…A(n-1)A(n)某一问题的n个输入B1(1)B1(2)…B1(m)该问题的一种解（可行解）是A的一个子集满足一定的条件约束条件Bk(1)Bk(2)…Bk(m)…目标函数取极值最优解3.1什么是贪心方法根据题意，选取一种量度标准，然后按量度标准对n个输入排序，按顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。量度标准A(1)A(2)…A(n)A’(1)A’(2)…A’(n)S(1)S(2)…量度标准意义下的部分最优解原问题的n个输入排序后的n个输入A’(j)贪心方法的抽象化控制ProcedureGREEDY(A,n)solutionФfori1tondoxSELECT(A)ifFEASIBLE(solution,x)thensolutionUNION(solution,x)endifrepeatreturn(solution)EndGREEDY按某种最优量度标准从A中选择一个输入赋给x，并从A中除去判断x是否可以包含在解向量中将x与解向量合并并修改目标函数3.2背包问题问题描述已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi，假定将物品i的某一部分xi放入背包就会得到pixi的效益(0≤xi≤1,pi>0)

，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？问题的形式描述极大化

∑pixi

约束条件

∑wixi≤M 0≤xi≤1,pi>0,wi>0,1≤i≤n1≤i≤n1≤i≤n目标函数背包问题实例考虑下列情况的背包问题n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的4个可行解是：(x1,x2,x3)∑wixi∑pixi①(1/2,1/3,1/4)16.524.25②(1,2/15,0)2028.2③(0,2/3,1)2031④(0,1,1/2)2031.5贪心方法的数据选择策略(1)用贪心策略求解背包问题时，首先要选出最优的度量标准。可以选取目标函数为量度标准，每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中。如上面的实例所示，可将物品按效益量非增次序排序：(p1,p2,p3)=(25,24,15)。先装入物品1重量为18，即x1=1；然后再装物品2，由于约束条为∑wixi≤M=20，所以物品2只能装入重量为2的一小部分，即x2=2/15。贪心方法的数据选择策略(2)按上述的数据选择策略，装入顺序是按照物品的效益值从大到小的输入，由刚才的方法可得这种情况下的总效益值为∑pixi=25+24*2/15=28.2，显然是一个次优解，原因是背包容量消耗过快。2. 若以容量作为量度，可让背包容量尽可能慢地被消耗。这就要求按物品重量的非降次序来把物品放入背包，即(w3,w2,w1)=(10,15,18)。贪心方法的数据选择策略(2)先装入物品3,x3=1,p3x3=15，再装入重量为10的物品2，∑pixi=15+24*10/15=31。由刚才的方法可得这种情况下的总效益值为31，仍是一个次优解，原因是容量在慢慢消耗的过程中，效益值却没有迅速的增加。贪心方法的数据选择策略(3)3. 采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准。即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需使物品的装入次序按pi/wi比值的非增次序来考虑。这种策略下的量度是已装入物品的累计效益值与所用容量之比。(p2/w2,

p3/w3,

p1/w1)=(24/15,15/10,25/18)。先装入重量为15的物品2，在装入重量为5的物品3，∑pixi=24+15*5/10=31.5。此结果为最优解。背包问题的贪心算法ProcedureGREEDY-KNAPSACK(P,W,M,X,n)realP(1:n),W(1:n),X(1:n),M,cu;integeri,n;X0;cuMfori1tondoifW(i)>cuthenexitendifX(i)1;cucu-W(i)repeatifi≤nthenX(i)cu/W(i)endifEndGREEDY-KNAPSACK将解向量X初始化为0Cu为背包的剩余容量只放物品i的一部分预先将物品按pi/wi比值的非增次序排序最优解的证明基本思想把这个贪心解与任一最优解相比较，如果这两个解不同，就去找开始不同的第一个xi，然后设法用贪心解的这个xi去代换最优解的那个xi

，并证明最优解在分量代换前后的总效益值无任何变化。反复进行这种代换，直到新产生的最优解与贪心解完全一样，从而证明了贪心解就是最优解。最优解的证明定理3.1

如果p1/w1≥p2/w2≥…≥pn/wn，则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。证明：设X=(x1,…,xn)是GREEDY-KNAPSACK算法所生成的解。如果所有的xi等于1，显然这个解就是最优解。否则，设j是使xj!=1的最小下标。 由算法可知，对于1≤i<j,xj=1;

对于j<i≤n,xj=0;

对于i=j，0≤xj<1。最优解的证明假设X不是最优解，则必定存在一个最优解Y=(y1,…,yn)，使得∑piyi>∑pixi

。假定∑wiyi=M，设k是使得yk!=xk的最小下标，则可以推出结论yk<xk成立。这个结论可从下面三种可能发生的情况分别证明：若k<j，则xk=1。因yk!=xk，则yk<xk成立若k=j，由于∑wixi=M，且对于1≤i<j，有xj=yi=

1，而对于j<i≤n，有xj=0。若yk>xk，则有∑wiyi>M，这与Y是可行解矛盾。若yk=xk，与假设yk!=xk矛盾，故只有yk<xk成立。若k>j，若yk>xk=0

，则∑wiyi>M,这与Y是可行解矛盾。因此，结论yk<xk成立。 现在，假定把yk增加到xk，那么必须从(yk+1,…,yn)中减去同样多的量，使得所用的总容量仍为M。这导致一个新的解Z=(z1,…,zn)，其中，zi=xi,1≤i≤k，并且∑wi(

yi-zi)=wk(

zk-yk)

。因此，对于Z有∑pizi=∑piyi+(zk-yk)pk-∑(yi-zi)pi

=∑piyi+(zk-yk)wkpk/wk-∑(yi-zi)wipi/wi

≥∑piyi+[(zk-yk)wk-∑(yi-zi)wi]pk/wk

=∑piyi

1≤i≤n1≤i≤nk<i≤n1≤i≤nk<i≤n1≤i≤nk<i≤n1≤i≤nk<i≤n所以∑pizi≥∑piyi成立最优碎解的锋证明若∑pizi>∑piyi，则Y不可计能是优最优讨解。若∑pizi=∑piyi，同托时Z=恰X，则X就是混最优时解；若∑pizi=∑piyi，圾但Z!艳=X，则穗重复瓜上面击的讨禁论，显或者惊证明Y不是束最优无解，货或者牛把Y转换座成X，从厅而证龟明了X也是擦最优畏解。麻证毕妙。课后火思考校题找零你钱问齐题：韵一个消小孩打买了睁价值舰为33美分宁的糖暗，并演将1美元拖的钱袋交给没售货砖员。简售货刘员希花望用永数目所最少匙的硬尾币找源给小观孩。欧假设均提供赢了数牲目不陵限的退面值字为25美分腥、10美分祝、5美分恨、及1美分占的硬痛币。长使用除贪心它算法销求解企最优现结果派。并舅证明弟找零扰钱问屈题的恒贪心集算法偶是否讲总能之产生碌具有航最少隐硬币棋数的洞零钱药。考虑桥假设乏售货役员只受有数副目有袖限的25美分逗，10美分朱，5美分扣和1美分多的硬爆币，谈给出槐一种迈找零备钱的规贪心东算法轰。3.雀3带有资限期炎的作培业排烤序问题践描述假定急只能俩在一规台机查器上遭处理n个作谣业，召每个贯作业悔均可妄在单者位时透间内乱完成糟；又奇假定渣每个榨作业i都有越一个闸截止书期限di>0银(是整框数)，当牛且仅幼当作庙业i在它仍的期胖限截阻止之浊前被衡完成衬时，爬则获蝇得pj>0的效术益。这个燃问题蔑的一师个可断行解乒是这n个作假业的榆一个租子集绪合J，J中的河每个肢作业奏都能垄在各物自的磨截止壤期限幼之前阻完成所，可驴行解盖的效郑益值或是J中这浩些作期业的阻效益园之和∑pj。具梨有最误大效千益值你的可昌行解临就是往最优古解。带有唤限期摧的作你业排纺序实巨例例3.岩2逮n锋=4，(p1,p2,p3,p4)范=疗(1冻00短,1姓0,画15扫,2笑0)和(d1,d2,d3,d4)=喘(2启,1创,2次,1唤)，这雁个问首题可咸能的码可行绑解和爱他们誓的效籍益值牙为：可行解J处理顺序效益值∑pj

①（1）1100②（2）210③（3）315④（4）420⑤（1，2）2，1110⑥（1，3）1，3或3，1115⑦（1，4）4，1120⑧（2，3）2，325⑨（3，4）4，335带限影期的辩作业扫排序胀算法为了丛得到墨最优奶解，匙应制交定如惩何选肤择下决一个处作业娱的量嗽度标语准，疏利用恶贪心踪蝶策略阁，使欧得所影选择刃的下辟一个窄作业驻在这幕种量样度下厦达到艇最优泉。可把目最标函测数∑pj作为案量度，则工下一罗个要击计入滑的作底业将乏是使册得在密满足视所产击生的J是一灵个可嚼行解周的限骆制条玻件下舱使∑pj得到属最大向增加安的作谦业，警这一嚼方法盲只要将各耗作业逮按效益pi降序句来排捞列就可权以了辈。例3.白2求解(p炊1，p2，p3，p4社)＝(1彩00绕,1砖0,薄15尖,2镜0)光(d两1，d2，d3，d4群)＝(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卡}，最有终效腥益值彩＝12碧0（问辅题的最优畜解）带限幸期的尚作业笨排序陈算法作业把按p1≥p2≥…≥pn的次哑序输乡丰入：Pr续oc灯ed宋ur赚e腾GR往EE凳DY桌_J布OB尚(D飞,J叉,n荷)J{乐1}fo艺r技i方2粘to振n法d狼oif侮J∪南{i韵}的所平有作元业都呼能在锄他们绑的截疼止期砍限前吵完成th基en傍J泥J∪{i佩}en怎di黑fre困pe抱atEn寇dGR喜EE辅DY糠_J读OB定理3.咳2对于揪作业企排序祖问题茅，用GR筐EE圾DY敬_J狠OB算法慨所描贪述的芒贪心够方法承总是乎得到覆一个伟最优持解证明园如下:定理3.备2证明证明他：设J是由傅贪心捉方法锹所选才择的眠作业稳的集知合；庆设I是一坦个最韵优解杆的作魄业集惕合。幸则I≠陈J，否之则J也是趟最优说解。易知品：I不是J的真烧子集夜，否艰则I就不涌是最钉优解抱；J也不刚是I的真荷子集裁，这铜是由叶贪心华法的湖工作我方式灶所决叨定的哭。因碍此，也存在享作业a和b，使秧得a属于J但不冒属于I；b属于I但不途属于J。设a是使司得a属于J但不茫属于I的一揭个具淡有最高单效益的作馆业，胶对于争在I中又直不在J中的零所有桃作业b，都柿有Pa帆≥P残b。这炮是因麦为若Pa菠<P雹b，则痰贪心绿法会边先于烈作业a考虑荐作业b并且活把b计入恢到J中。定理3.咬2证明牧（续皂）设SJ是J的可晒行调洗度表缩慧；SI是I的可统行调救度表迟。对于得每一橡个I和J的共同咽作业i，做杂以下治调整朱：（t<适t’）如果t>册t’，则促可在SI中作丈类似怎的调掘整。用这滥种方绪法，鞋就使谦得J和I中共棍有的使所有坡作业描在相齿同的沙时间臭被调朴度。SJSIiitt’t+1t’+1xSJSIxitt’t+1t’+1i定理3.茎2证明涛（续都）设作跟业a是使筒得a属于J但不丹属于I的一打个具悼有最音高效副益的统作业。SJSIatata+1btata+1由于Pa冬≥P嚼bSJSIatata+1atata+1显然腥，转读换后I的效充益值谁没有埋减少岂。重复换应用队上述货转换截，使I在不塔减少雅效益裹值的贷情况候下转幅换成J，因盘此，J也必铲定是宰最优竿解。证毕荡。如何带判断J的可因行性方法蜻一：检验J中作泄业所举有可哈能的龄排列周，对禾于任妻一种泳次序软排列泄的作咳业排趴列，讽判断消这些咐作业斗是否急能够雕在其张期限吩前完晕成，渡也即史若J中有k个作联业，渴则将笔要检卡查k!个序册列方法汤二：检查J中作展业的一个陆特定届序列就可趋判断J的可照行性读：对飞于所仙给出秆的一赖个排营列σ＝i1i2…ik,由于贤作业ij完成辩的最谈早时责间是j，因敢此只贼要判佣断出σ排列松中的屯每个抹作业dij≥j，就踩可得哑知σ是一垃个允亭许的臣调度魔序列枯，从窄而J是一砖个可近行解北。反澡之，着如果σ排列朗中有镜一个dij＜j,则σ将是破一个逼行不造通的杀调度司序列侮，因懒为至超少作粒业ij不能症在其苹期限佩之前荡完成猾。这一匀检查廊过程安可以寨只通耍过检患验J中作凳业的蔽一种酱特殊毫的排陆列：按照昏作业静期限断的非菠降次盖序排秤列的上作业处序列即可仓完成猛。可行书解的明确定定理3.搭3:设J是k个作妄业的传集合疮，α=刘i1,i2,…翻,ik是J中作抛业的抛一种虎排列膜，它割使得di1≤di2≤…腔≤dik。J是一免个可吧行解栗，当且始仅当J中的界作业闸可以询按照α的次醋序而仙又不屈违反发任何疑一个温期限零的情况况来息处理涉。定理3.匹2证明证明：（充少分性树）若J中的租作业雷可以啊按照α的次阀序而醒又不庭违反袄任何慌一个副期限稻的情具况来够处理瓶，则J就是寄一个贵可行病解。（必票要性痕）由梢于J可行苹，则密必存于在一腾种调阅度序详列α’紧=r1r2…rk，drj≥j，1≤撇j妹≤料k。假设α’≠α，则a是使使得ra≠ia的最磨小下霞标。α’rarb=雀iaαiaα=眨i1,i2,…牺,ik,di1≤di2≤…隙≤dikα’井=r1r2…rk,熊drj≥j，1≤柳j揉≤巡寿kα’rb=录iaraαia连续晒使用张这一抓方法可，就配可将α’转换河成α且不堂违反拔任何患一个是期限怨。定理咽得证组。带限揭期序传作业薄排序险的处紧理首先症将作孟业1存入警数组J中，跑然后伐处理察作业2到作刚业n假设给已处深理了i-垦1个作渴业，次其中懂有k个作险业存窄入了J(屿1)借,J丈(2架)…廉J(范k)中，呈并且D(见j(爽1)豪)≤驰D(瘦j(哨2)滔)≤御…≤妖D(勿J(黑k)比)，现悄在开和始处暑理作找业i判断J∪{i傍}是否微可行址，只猎需找皱出按诉期限减的非观降次文序插固入作捕业i的位欢置，匆插入客后有D(悬J(党r)离)≥r。找作国业i可能啄的插隙入位观置：恋将D(绝J(怎k)有),悉D(葱j(萝k-储1)迎),铺…,饲D(蜡J(唐1)往)逐个弄与D(麦i)比较翻，直及到找赠到位笼置r，它统使得D(鄙i)突≥D矛(J闷(r俘)),且D(奴i)详>r，则亲说明r+政1…k共k-品r个作省业可脱以向垃后延催迟一斗个单恳位时罚间来吉处理圾，可少将这送些作膏业向唉后移泼动一令个位琴置，摇然后仔把作瞒业i插入胀到r+某1位置鼠，就畏可得膝解。带限城期序鼓作业哪排序门的贪冻心算古法pr茅oc特ed何ur菜e机JS疲(D欲,J惊,n禁,k多)in醒te什ge猜r渴D(料0:礼n)围,J劫(0顶:n吗),艰i,判k,杰n,滋rD(番0)J洒(0轿)勿0;k史1;升J(诱1)吊1除;fo夏r蹄i弯2离to坏n橡d怠or旋k;wh卫il牢eD(共J(性r)宫)>助D(劳i)an价dD(汉J(菌r)馋)≠rdorr婚-停1;re姑pe撇atifD(提J(斤r)狐)≤怪D(据i)an删dD(私i)算>rth循enfo匠r前i产k者to漫r墓+1扯b但y微–1腐d拴oJ(够i+掠1)J译(i疫)re创pe导atJ(收r+饼1)i偿;绍k适k扭+1；en椅di姨fre勒pe尸atEn碗d急JS找到朵插入魔位置检查自插入滥的可焦能性插入问值对于带限剧期序茫作业惯排序滴的贪涨心算抬法JS有两隔个赖及以测尼量其列复杂腐度的房诚参数秩，即跟作业草数n和包朵含在偿解中像的作错业数s。内纤层的wh秒il典e循环啄至多猫循环k次，呀插入侨作业i要执万行时盆间为O(斥k-键r)，外割层fo膀r循环诞共执搜行(n限-1嘉)次。如果s是k的终督值，隆即s是最弹后所幅得解意的作适业数肆，则JS算法秩所需痰要的旱总时芦间为O(拍sn化)。由居于s≤n，所姻以JS算法眨的时致间复姑杂度涝为O(至n2)。带限狐期序纹作业删排序西的贪香心算括法一种真更快伟的作凳业排挖序算切法通过哗使用游不相俘交集饲合的UN伯IO乖N与FI筑ND算法流以及排使用由一个骑不同夕的方帆法来世确定蛙部分插解的敌可行羊性，牧可以撞将该女问题矮的计磨算时乘间由O(济n2)降到功接近友于O(察n)。规则遭是：坑若还届没有救给作皇业i分配茄处理含时间猫，则参分配球给它相时间贿片[a魔-1叉,a妥],其中a应尽杰量取士大且称时间碑片[a抵-1荷,a打]是空堆的。喝若正堤被考砖虑的市新作雕业不运存在辛这样咸的a，这吉个作庸业就羡不能春计入亿解中捏。一种葬更快牲的作别业排怒序算祖法(续)例：卖设n=痛5,扒(p搬1,问…,赚p5梯)=诸(2垦0,恐15奏,1姥0,茂5,蛋1)和（d1赏,…晕,d介5)关=(像2,似2,求1,凤3,以3)0123j1j2j4最优解是J={1,2,4}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舍弃作业祥排序失的一乞个更伍快算竹法pr絮oc卡ed景ur斗e淡FJ版S(闪D,悉n,泼b,特J,欲k)//假定p1≥p2≥…衫≥pn,诞b=患mi豆n{坦n,需ma汇x{讨D(糖i)沫}}In牛te弊ge再r俱b,倒D(许n)博,J势(n朋),尖F(原0:喷b)荒,P阴(0带:b肥)fo赖r帽i=找0重to蚂n禁d洞oF(啄i)幸=i角;萍P(臣i)狗=-皮1re乓pe天atk=形0fo义r堂i=括1笨to拍n芦d旧oj=劣FI齿ND余(m破in抬(n普,D龙(i齐))莲)if幼F训(j孝)<坑>0锣t谈he泄n局k=钓k+忆1;座J(渗k)格=iL=左FI岩ND销(F统(j蚀)-躁1)销;莲ca行ll珠U劣NI牲ON汤(L舒,娇j)F(铅j)烟=F君(L饰)en张di览fre舍pe子aten窑d饺FJ咸S查看望实例课后腰思考裁题0/返1背包旅问题改：在崖杂货话店比晓赛中用你获靠得了镇第一据名，病奖品洒是一芹车免兰费杂男货。旦店中刘有n种不隙同的向货物夫。规摩定从量每种欠货物忙中最备多只访能拿鸦一件则，车质子的效容量姥为c，物多品i需占轧用wi的空灾间，柄价值脱为pi。你品的目裳标是妨使车企中装唇载的求物品咱价值惯最大债。当冲然，灯所装梯货物浮不能棒超过屿车的伙容量窃，且用同一桌种物听品不策得拿攻走多舱件。先如何雅选择军量度辟标准要才能唉找到竭最优裁解？若n=撑2,争w脊=[获10隐0,桐10油,1漫0]氏,p煤=[般20岁,1前5,垦15医],龟c=香10谣5。证运明利逢用价律值贪傻心准润则时桃，所录得结彼果是竖否是妄最优丈解？3.纪4最优惭归并廊模式X1X2X3X4Y1Y2Y3X1X2X3X4Y1Y2Y3第二倦章中她学习饶了如羞何用尽分治喊法将胶两个骂分别河包含n个和m个记距录的乒已分誓类文狼件在O(哑n+屋m)时间躁内归葛并成慎一个顿包含(n吧+m谁)个记胶录的组分类幻玉文件挽。下领面是辅两种姿将4个文疾件进层行归淘并的牵方法纠。不小同的窄配对笑法要焦求不淹同的吗计算映时间洗。什么姓是归题并模计式给出n个文住件，漫则由此许多谨种把胸这些嫩文件勒成对酒地归影并成蛋一个种单一位分类揭文件棋的方壳法。不同斤的配耕对方耕法要新求不筹同的虚计算抱时间问题握的关新键是恢：确悼定一勉个把n个已煮分类状文件梦归并著在一旧起的呢最优驱方法龄（即胞需要握最少提的比案较的血方法宣）X1，X2和X3是各俭自有30个记架录、20个记肢录和10个记俘录的阴三个之已分叔类文将件。归并X1和X2需要50次记优录移袖动，骑再与X3归并筛则还绸要60次移似动，灶其所逼需要引的记突录移摄动次本数总蛙量为11惹0。如果匀首先穴归并X2和X3，需消要30次移俗动，陡然后蔽再归骡并X1，需窗要60次移谢动，扣则所塌要移蹲动记绒录的声总量黑为90。因此储，第远二个甘归并版模式芳比第胞一个挤要好拾。例3.藏5最优幼归并秤模式丈的实养现由于恐归并思一个库具有n个记言录的膨文件耗和一当个具围有m个记爽录的禁文件冷可能砌需要m+组n次记陪录移谎动，彼因此装对于军量度从标准璃的一帜种很李明显链的选竞择是焦：每一僻步都口归并宝尺寸基比较筋小的后两个熊文件。例如寻有五嫂个文哭件长纤度分稠别是(F1,览F2,月…岸,F5)=场(2筑0,榴30肯,1峰0,叫5,雾30疫)5F410F315Z120F130F130F160Z335Z295Z4二元抛归并堵树二路教归并迹模式上面睡所描压述的覆归并箩模式旅称为二路解归并义模式。二叉路归济并模大式可利以用匀二元馅归并才树来态表示顾。二元零归并冻树中诵叶结宁点被歌画成大方块恋，表嫁示五记个已爽知的戒文件剩。这浮些结单点称撑为外部世结点。剩下户的结歌点被洲画成券圆圈子，称获为内部岔结点。每升个内乞部结页点恰表好有膀两个么儿子忌，表宋示它摆是将召两个滨儿子社所表额示的摊文件母归并钩在一种起而谦得到愈的文仍件。每个狗结点帜中的范数字缩慧都是月那个忧结点箩所表讯示文件化的长利度（即瞧记录杨数）跃。最优贴归并童模式矮的实钥现带权仅外部其路径旁长度如果di表示遵从根四到代争表文孩件Fi的外花部节坡点的赶距离促，qi表示Fi的长占度，游则这手棵二寨元归灯并树镇的记锦录移阿动总骡量是暮：∑diqi这个继和数你叫做述这棵农树的带权胳外部怪路径请长度一个纺最优呢二路沃归并片模式林与一叛棵具汉有最寸小外饰部路己径的饺二元晕树相享对应砖。i=拍1n二元劫归并是树算窗法二元或归并壳树算率法把n个树盗的表L作为并输入共。树也中的妙每一机个结跳点有缸三个院信息腹段(L洋CH经IL欠D,做RC盛HI弓LD输,W耻EI候GH拖T)。起初哗，L中的闪每一后棵树杠正好愚有一列个结炸点。弱这个悲结点敌是一购个外辈部结晒点，溪而且薪其LC什HI爱LD和RC筝HI版LD信息南段为0，而WE择IG虾HT是要泥归并锦的n个文棵件之攻一的亮长度月。算法犯运行或期间皆，对咽于L中的厕任何归一棵耗具有腐根结暖点T的树鞠，WE唐IG准HT带(T蔽)表示稿要归导并的宇文件燥的长剖度。WE在IG旷HT贼(T购)=树T中外规部结责点的欢长度苦和。二元宴归并失树算厦法pr硬oc母ed顿ur方e宅TR枣EE闯(L隆,n报)fo芝r期i1狸t超o艺n-宾1蚂doca串ll料G眨ET富NO泻DE械(T计)LC再HI妻LD闪(T消)味LE佳AS能T(贩L)RC芹HI映LD哑(T行)招LE块AS默T(狂L)WE推IG悼HT赵(T忆)静WE蜡IG额HT风(L殿CH权IL粮D(买T)如)+W显EI洽GH抓T(很RC询HI叛LD何(T夺))ca弓ll毫I蜂NS围ER权T(导L,豆T)re户pe省atre彼tu愈rn挑(音LE炼AS抬T(铁L)典)En事d济TR效EE每个伞节点碍有三色个信醉息：LC杀HI闷LD怒,R台CH瓣IL右D,宇WE悲IG糊HT构造秤一个域新结盒点找出L中一赛棵具赞有最千小WE呆IG盆HT的树要，并堤删除把根呀为T的树蝴插入拒到表L中二元暖归并财树算冬法的广实例例：L最初开有6个文变件，博长度置分别卫为：2绕,方3醋,做5汇,所7音,娇9变,裁13。2355101323791639二元努归并劳树算裁法的跃计算墙时间时间婚分析替：1)循环须体：n-星1次2)泰L以有妹序序芝列表龙示LE务AS绕T(四L)页:描О(星1)许IN嗓SE既RT夸(L沿,T神):淡О燥(n丝式)总时厕间：О(么n2)3)炮L以mi匹n-堆表地示LE咬AS宵T(舱L)灾:释О(龙lo妻gn呜)哄IN呈SE更RT罩(L针,T俗):画О稀(l箱og据n)总时处间：О(干nl辱og抱n)最优仿解证敏明定理3.愈4若L是最夫初包汗含n（≥1）个乌单个礼结点黄的树兽，这书些树旧有WE榴IG熔HT值为(q1,q2,…轧,qn)，则壤算法TR青EE对于搭具有袖这些医长度篇的n个文组件生娃成一风棵最逐优的趣二元袜归并喂树。最优矩解的肿证明证明份：用归纳灯法证明①利当n=辟1时，觉返回钟一棵时没有纱内部额结点承的树茫。定色理得肤证。②驶假定均算法说对所丢有的(q1,q2,…有,qm)，1≤效m＜n,生成踪蝶一棵哗最优辽二元颂归并渗树。③铲对于n,假定q1≤q2≤…冰≤qn,则q1和q2将是乱在fo裙r循环尸的第量一次按迭代劣中首芳先选土出的矛具有用最小WE西IG舞HT值的饱两棵附树。躺如图有所示分，T是由筛这样颤的两蜜棵树丛构成颗的子矮树：q1q2q1+q2T最优稿解的数证明■设T’是一阵棵对覆于(q1,q2,…恩,qn)的最闭优二晴元归漏并树讲。■设P是T’中距避离根最远的一虑个内部薪结点。若P的两竭棵子课树不倒是q1和q2，则在用q1和q2代换P当前联的子止树而饿不会枣增加T’的带侧权外奴部路喷径长舅度。故，T应是纺最优两归并吐树中砖的子卸树。在T’中用缺一个耗权值低为q1＋q2的外翁部结著点代挂换T，得沸到的捡是一架棵关掠于(q1＋q2,…绸,qn)最优柏归并逆树T”。而由屿归纳论假设图，在许用权利值为q1＋q2的外侨部结衔点代温换了T之后誉，过死程TR锻EE将针溜对(q1＋q2,…右,qn)得到切一棵抚最优控归并茂树。将T带入饥该树隔，根轰据以耍上讨焦论，唉将得搬到关舞于(q1,q2,…拔,qn)的最航优归摘并树剧。故妖，TR穿EE生成建一棵贿关于(q1,q2,…赌,qn)的最优恶归并蓄树。3.商5最小献生成追树1.问题古的描心述生成仓树：设G=滨(V含,E坦)是一语个无北向连滥通图扮。如吐果G的生成子邮图T=豪(V捞,E毫')是一啄棵树齿，则忽称T是G的一投棵生成控树(s孝pa西nn尺in本g触tr常ee溉)．2.最小岁生成爬树:贪心寄策略度量筛标准浮：选青择能钞使迄扔今为玻止所教计入菌的边由的成本般和有最小增加的那壮条边名。●Pr预im算法●Kr箩us园ka伟l算法Pr贷im算法策略况：永使得绘迄今蚁所选江择的穴边的描集合A构成悠一棵概树；墓对将穿要计还入到A中的才下一择条边(u驱,v仓)，应浴是E中一吵条当火前不泥在A中且邻使得A∪亮{(颂u,就v)光}也是你一棵欺树的分最小乖成本为边。Pr弹im算法1462531030204525554050153512162162316234边(1,2)(2,6)(3,6)(6,4)成本102515201462531020251535(3,5)35Kr适us仙ka旺l算法策略刮：拾（连动通）扛图的位边按欢成本丝式的非浴降次森序排括列，艺下一苦条计扬入生饱成树T中的纯边是度还没笔有计同入的咸边中稳具有玩最小根成本领、且缠和T中现楚有的铅边不初会构修成环热路的够边。Kr智us栽ka括l算法1462531030204525554050153512162162316234边(1,2)(3,6)(4,6)(2,6)成本1015202516234563453454551462531020251535(1,4)(3,5)30舍弃353.好6单源颜点最雕短路捏径什么摆是单糟源点揪最短触路径已知跪一个n结点姻的有妈向图G=汗(V尾,E字)和边宽的权剖函数c(相e)，求优由G中某申指定伯结点v0到其章他各把个结目点的复最短度路径光。v0v2v1v3v4v5204550101515201035303路径长度(1)v0v210(2)v0v2v325(3)v0v2v3v145(4)v0v445贪心葡策略异求解1)度量广标准量度搅的选秘择：便迄今页已生悟成的所有换路径思长度兄之和——为使副之达英到最拼小，吊其中扇任意慢一条随路径病都应道具有戴最小复长度喷：假定遗已经盛构造晚了i条最梨短路卧径，杂则下律一条验要构固造的迅路径虚应是听下一填条最筒短的势路径缩慧。处理剑规则懒：按凤照路径握长度的非降猜次序依次丛生成额从结拥点v0到其艰它各士结点蒜的最裹短路扛径。例：v0→v2v0→v2→v3v0→v2→v3→v1v0→v4贪心饼策略怨求解2)贪心裳算法♠设S是已泼经对距其生级成了够最短鼓路径觉的结点元集合（包跃括v0)。♠对于般当前流不在S中的报结点w，记DI毯ST宫(w津)是从v0开始奸，只经荒过S中的姜结点剂而在w结束络的那蛋条最疾短路奴径的挠长度张。则有岩，SW贪心外策略净求解①如果席下一洋条最轻短路已径是鸽到结好点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内的朱结点心中且恰具有歌最小务距离DI厚ST则(u狸)的结悲点。产生突最短第路径周的贪传心方心法选出项了结虎点u并生棋成了铅从v0到u的最历短路容径之可后，运结点u就成浅为S中的陵一个杯成员誓。此时饱，那龄些从v0开始哑，只覆通过S中的丑结点善并且蜡在S外的谱结点w处结毙束的漫最短笋路径俯可能垫会减缩慧小。如果竖长度古改变朴了，评则它符必定庸是由喘一条断从v0开始火，经煌过u然后互到w的更免短路伶径所携造成瓶的。其中朴从v0到u的路抹径是龄一条础最短域路径粗，从u到w的路奔径是掠边<u定,w苏>，于