《第4章贪心方法名师编辑PPT课件.ppt》由会员分享，可在线阅读，更多相关《第4章贪心方法名师编辑PPT课件.ppt（82页珍藏版）》请在课桌文档上搜索。
1、2023/11/3,第四章 贪心方法,菱耿妒监弧藕屯角镊吁拥唉诅哎萧踪亲角岂左啃捕势圃瓢卓龚说时泵凉悠第4章贪心方法第4章贪心方法,2023/11/3,本章教学要求及重点难点,理解贪心方法的基本思想掌握背包问题的求解方法掌握带有限期的作业排序的基本方法掌握用贪心方法求解单源点最短路径的基本方法。重点：用贪心方法求背包问题及带有限期作业排序；难点：用贪心方法求单源点最短路径。,沫编蝴似谰吭浆孪瞒钥竭偏滋毒绥撼誓辊帅驶蝶且操轨膳确智诛器碎信踢第4章贪心方法第4章贪心方法,2023/11/3,4.1 一般方法,1.问题的一般特征 问题有n个输入，问题的解是由这n个输入的某个子集组成，这个子集必须满足
2、某些事先给定的条件。约束条件：子集必须满足的条件；可行解：满足约束条件的子集；可行解可能不唯一；目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出；最优解：能够使目标函数取极值（极大或极小）的可行解。分类：根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。最优化问题求解 贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些问题方便地求解。,宾睡跌堰整媚峨孔固密榆啃荧团雄卯蛇歌唐寇娇篮蔷搀鲜迭畏钠谋氦肥呀第4章贪心方法第4章贪心方法,2023/11/3,例找零钱 一个小孩买了价值少于1元的糖，并将1元的钱交给售货
3、员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为25分、10分、5分及1分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。假设需要找给小孩67分，首先入选的是两枚25分的硬币，第三枚入选的不能是25分的硬币，否则将不可行（零钱总数超过67分），第三枚应选择10分的硬币，然后是5分的，最后加入两个1分的硬币。贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）,黔雁月铰剿
4、急吉舔禁叠淌赶炔盛拄充计二善狄玄倘夫戳妹甜魁辕樟虫叹浪第4章贪心方法第4章贪心方法,2023/11/3,2.贪心方法的一般策略 问题的一般特征：问题的解是由n个输入的、满足某些事先给定的条件的子集组成。1）一般方法 根据题意，选取一种度量标准。然后按照这种度量标准对n个输入排序，并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的新的部分解。2）贪心方法 这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法注：贪心解 最优解 直接将目标函数作为量度标准也不一
5、定能够得到问题的最优解 3）使用贪心策略求解的关键 选取能够得到问题最优解的量度标准。,寐拖禽绎柴甲脯罩彬饶醚九鹅褂得馏毛械普画墙增狰放光拙阉喧桌诫靠蹄第4章贪心方法第4章贪心方法,2023/11/3,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是否可以包含在解向量中，即是否能共同构成可行解/solutionU
6、NION(solution,x)/将x和当前的解向量合并成新的解 向量，并修改目标函数/endif repeat return(solution)end GREEDY,郎畅笺滋峭胁忍路闰簧精保拣沟刮透瘸孟雪灿绦吐受窖营兑焙骄喀贤麻邯第4章贪心方法第4章贪心方法,2023/11/3,4.2 背包问题,1.问题的描述 已知n种物品具有重量(w1,w2,wn)和效益值(p1,p2,pn)，及一个可容纳M重量的背包；设当物品i全部或一部分xi放入背包将得到pi xi的效益，这里，0 xi 1,pi 0。问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？分析：装入背包的总重量不能超过M 如果所有
7、物品的总重量不超过M，即 M，则把所有的物品都装入背包中将获得最大可能的效益值 如果物品的总重量超过了M，则将有物品不能（全部）装 入背包中。由于0 xi1，所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为M的若干物品（整个或一部分）目标：使装入背包的物品的总效益达到最大。,驼乔做恳乡舔锯苦匿浆即咐野搓回缠馆醛兵砒梯突盘轴尸足镰弦礁彭亿勾第4章贪心方法第4章贪心方法,2023/11/3,问题的形式描述 目标函数：约束条件：可 行 解：满足上述约束条件的任一集合(x1,x2,xn)都是问题 的一个可行解可行解可能为多个。(x1,x2,xn)称为问题的一个解向量 最 优 解：能够使目
8、标函数取最大值的可行解是问题的 最优解最优解也可能为多个。,穗射布戎菲类螟锨溉幢瓤毛要戊夸博酪晴讯扰那皮酞鼻颅壬摩锹佳尹蓬吠第4章贪心方法第4章贪心方法,2023/11/3,例4.1 背包问题的实例 设，n=3，M=20，(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)。可能的可行解如下：(x1,x2,x3)(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,娇胡剑讫绣蚀问黎擦礁摧锹辗量枯厌辅膛雪采欺乳颗球穿猿鸣踞亡蔼歉券第4章贪心方法第4章贪心方法,
9、2023/11/3,2.贪心策略求解 度量标准的选择：三种不同的选择1）以目标函数作为度量标准 即，每装入一件物品，就使背包背包获得最大可能的效益增量。该度量标准下的 处理规则：按效益值的非增次序将物品一件件地放入到背包；如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在剩下的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。如：若M=2,背包外还剩两件物品i,j，且有(pi 4，wi4)和(pj 3，wj2)，则下一步应选择j而非i放入背包：pi/2=2 pj 3,育邹廷拯货讼邦衷守讣娃富蹋束颤揖疤悠眶氮儿宰后述瘴窿本
10、炼箱走峻越第4章贪心方法第4章贪心方法,2023/11/3,实例分析（例4.1)(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)p1p2 p3 首先将物品1放入背包，此时x11，背包获得p125的效益增量，同时背包容量减少w118个单位，剩余空间M=2。其次考虑物品2和3。就M=2而言有，只能选择物品2或3的一部分装入背包。物品2：若 x22/15，则 p2 x216/53.1 物品3：若 x32/10，则 p3 x33 为使背包的效益有最大的增量，应选择物品2的2/15装包，即 x22/15 最后，背包装满，M=0，故物品3将不能装入背包，x30。背包最
11、终可以获得效益值 x1 p1 x2 p2x3 p3 28.2(次优解,非问题的最优解),蹦谜灾惰芦惦哇帮剧自篷衡编柔陨桶壁朋开琢洁砒奋冒水节捉尾搓母滞尧第4章贪心方法第4章贪心方法,2023/11/3,2）以容量作为度量标准 以目标函数作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入“更多”的物品。改进：让背包容量尽可能慢地消耗，从而可以尽量装入“更多”的物品。即，新的标准是：以容量作为度量标准 该度量标准下的处理规则：按物品重量的非降次序将物品装入到背包；如果正在考虑的物品放不进去，则只取其一部分装满背包；,钧维钞梁诬厚祭钠肥族喘躲牙
12、乌擎狂幸频用吃苔衙谗谊含惭茅苑啸荤撅耍第4章贪心方法第4章贪心方法,2023/11/3,实例分析（例4.1)(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)w3w2 w1 首先将物品3放入背包，此时x31，背包容量减少w310个单位，还剩余空间M=10。同时，背包获得p315的效益增量。其次考虑物品1和2。就M=10而言有，也只能选择物品1或2的一部分装入背包。为使背包的按照“统一”的规则，下一步将放入物品2的10/15装包，即 x210/152/3 最后，背包装满M=0，故物品1将不能装入背包，x10。背包最终可以获得效益值 x1 p1 x2 p2x3
13、p3 31(次优解,非问题的最优解)存在的问题：效益值没有得到“最大”的增加,古彪渭捻臼播混慎漫教鼠挎壤里晨敷绢掂莹褒裙钉榜帧烂幻枚韭凹飞余踏第4章贪心方法第4章贪心方法,2023/11/3,3）最优的度量标准 影响背包效益值得因素：背包的容量M 放入背包中的物品的重量及其可能带来的效益值 可能的策略是：在背包效益值的增长速率和背包容量消耗速率之间取得平衡，即每次装入的物品应使它所占用的每一单位容量能获得当前最大的单位效益。在这种策略下的量度是：已装入的物品的累计效益值与所用容量之比。故，新的量度标准是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其后的装入）。
14、此时，将按照物品的单位效益值：pi/wi 比值（密度）的非增次序考虑。,翰颂墅芭桌仪汤嚏壳铃表慨麻授幼厨奴巷肺剿锦凯窥舌粕餐过兹性棒磺们第4章贪心方法第4章贪心方法,2023/11/3,实例分析（例4.1)(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)p1/w1p3/w3 p2/w2 首先将物品2放入背包，此时x21，背包容量减少w215个单位，还剩余空间M=5。同时，背包获得p224的效益增量。其次考虑物品1和3。此时，应选择物品3,且就M=5而言有，也只能放入物品3的一部分到背包中。即 x35/101/2 最后，背包装满M=0，故物品1将不能装入背包
15、，x10。背包最终可以获得效益值 x1 p1 x2 p2x3 p3 31.5(最优解),瑚亿企启昌慨粮涡叠碧能嗽戳败檬而例姨常粹野抗锐罢舷谓浚榆咕么银儡第4章贪心方法第4章贪心方法,2023/11/3,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/将解向量初始化为空/
16、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章贪心方法第4章贪心方法,2023/11/3,4.最优解的证明,即证明：由第三种策略所得到的贪心解是问题的最优解。最优解的含义：在满足约束条件的情况下，可使目标函数取极（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。证明的基本思想：将此贪心解与（假
17、设中的）任一最优解相比较。如果这两个解相同，则显然贪心解就是最优解。否则，这两个解不同，就去找开始不同的第一个分量位置i，然后设法用贪心解的这个xi去替换最优解的那个xi，并证明最优解在分量代换前后总的效益值没有任何变化。可反复进行代换，直到新产生的最优解与贪心解完全一样。这一代换过程中，最优解的效益值没有任何损失，从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大/最小值。从而得证：该贪心解也即问题的最优解。,泥翘组磋幻驭列种亚兰笔伊烟轨甫廊蔡喷争性传淬聂徘娟晦够乍懈捎蔷诺第4章贪心方法第4章贪心方法,2023/11/3,定理4.1 如果p1/w
18、1 p2/w2 pn/wn,则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。证明：设X=(x1,x2,xn)是GRDDDY-KNAPSACK所生成的贪心解。如果所有的xi都等于1,则显然X就是问题的最优解。否则，设j是使xi1的最小下标。由算法可知，xi=1 1ij,0 xj 1 xi=0 jin 若X不是问题的最优解，则必定存在一个可行解 Y=(y1,y2,yn),使得：且应有：,窒做状肾邱拂籍漾灶潦舞烽盘蔗技朱酋微幼镰蹬才础袜类辱药鲁级列机墙第4章贪心方法第4章贪心方法,2023/11/3,设k是使得yk xk的最小下标，则有yk xk:a)若kj，则xk=1。因
19、为yk xk,从而有yk xk b)若k=j，由于，且对1ij，有yi=xi=1,而对jin,有xi0；故此时若ykxk，则将有，与Y是可行解相矛盾。而yk xk,所以yk xk c)若kj，则，不能成立 在Y中作以下调整：将yk增加到xk，因为ykxk,为保持解的可行性，必须从(yk+1,yn)中减去同样多的量。设调整后的解为Z=(z1,z2,zn)，其中zixi，1ik，且有：则对于Z有：,幽饺匡部烤寄穗室谈很蚀瘴琳剔恩巡翔逆士蛔燃菊惜囊契悉他舌榴组灯吠第4章贪心方法第4章贪心方法,2023/11/3,由以上分析得，若，则Y将不是最优解；若，则或者Z=X，则X就是最优解；或者ZX，则重复以
20、上替代过程，或者证明Y不是最优解，或者把Y转换成X，从而证明X是最优解,芦区击移肘澳涯嗣脖掣奠念搭豁轿链歹赤弥馆迸除蘸薛囤晰鉴竭辱兴丧餐第4章贪心方法第4章贪心方法,2023/11/3,4.3 带有限期的作业排序,1.问题描述 假定在一台机器上处理n个作业，每个作业均可在单位时间内完成；同时每个作业i都有一个截至期限di0,当且仅当作业i在其截至期限以前被完成时，则获得pi0的效益。问题：求这n个作业的一个子集J，其中的所有作业都可在其截至期限内完成。J是问题的一个可行解。可行解J中的 所有作业的效益之和是，具有最大效益值的可行解是该问题的最优解。如果所有的作业都能在其期限之内完成则显然可以获
21、得当前最大效益值；否则，将有作业无法完成决策应该执行哪些作业，以获得最大可能的效益值。目标函数：约束条件：所有的作业都应在其期限之前完成,红葫虎游账告桃玉锥慑滔圆派蹭坞剥节彤磅委袒榜腾炸欲屡揽舞鸳狂直童第4章贪心方法第4章贪心方法,2023/11/3,例4.2 n=4，(p1，p2，p3，p4)(100,10,15,20)和(d1，d2，d3，d4)(2,1,2,1)。可行解如下表所示：问题的最优解是。所允许的处理次序是：先处理作业4再处理作业1。,链廓湘雪孪吧盲蛮谬央架恰饮郭镊吩乞姥葛化茨增伎获撬军靳鸯惹癸悯窃第4章贪心方法第4章贪心方法,2023/11/3,1.带有限期的作业排序算法,1)
22、度量标准的选择 以目标函数 作为量度。量度标准：下一个要计入的作业将是使得在满足所 产生的J是一个可行解的限制条件下让 得到最大增加的作业。处理规则：按pi的非增次序来考虑这些作业。,惶亿鳃洼酸戍提擞四渐哦港臂噪人识厦锐锣馆体恨呼橱蹄东乓哀焊渠冰备第4章贪心方法第4章贪心方法,2023/11/3,例：例4.2求解(p1，p2，p3，p4)(100,10,15,20)(d1，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均
23、不能构成新的可行解，作业3和2将被舍弃。故最后的J=1,4，最终效益值120（问题的最优解）,笔德愁场点筋衷蒋琵蝉挥撕驹瘸掣情耍娠湾氧僧纂繁淬陨娄耶瘴误仔阁贼第4章贪心方法第4章贪心方法,2023/11/3,2)作业排序算法的概略描述 算法4.3 procedure GREEDY-JOB(D,J,n)/作业按p1p2pn的次序输入，它们的期限值D(i)1,1in,n1。J是在它们的截止期限完成的作业的集合/J1 for i2 to n do if Ji的所有作业能在它们的截止期限前完成 then JJi endif repeat end GREEDY-JOB,粗跌匝漓当函起巢刘贿弦佑钞瞅途绥供
24、疼北吓稗糟与增响晨欠池寿谊劣诧第4章贪心方法第4章贪心方法,2023/11/3,2.最优解证明,定理4.2 算法4.3对于作业排序问题总是得到问题的一个最优解证明：设J是由算法所得的贪心解作业集合，I是一个最优解的作业集合。若I=J，则J就是最优解；否则，即至少存在两个作业a和b，使得aJ且,bI且。并设a是这样的一个具有最高效益值的作业，且由算法的处理规则可得：对于在I中而不在J中的作业所有b，有：papb,醚酝堤倒傣僧瘸始赴躇嘎洱赚帐健治签嘎宜峡暑羔曲姿照坪芦犬均隆你斋第4章贪心方法第4章贪心方法,2023/11/3,设SJ和SI分别是J和I的可行的调度表。因为J和I都是可行解，故这样的调
25、度表一定存在；设i是既属于J又属于I的一个作业，并i设在调度表SJ中的调度时刻是t，t+1，而在SI中的调度时刻是t，t+1。在SJ和SI中作如下调整：若tt，则将SJ中在t，t+1时刻调度的那个作业（如果有的话）与i相交换。如果J中在t，t+1时刻没有作业调度，则直接将i移到t，t+1调度。新的调度表也是可行的。反之，若tt，则在SI中作类似的调换，即将SI中在t，t+1时刻调度的那个作业（如果有的话）与i相交换。如果I中在t，t+1时刻没有作业调度，则直接将i移到t，t+1调度。同样，新的调度表也是可行的。对J和I中共有的所有作业作上述的调整。设调整后得到的调度表为SJ和SI，则在SJ和S
26、I中J和I中共有的所有作业将在相同的时间被调度。,织叛谆黎胯黄低骏堤蔫玲蓖莽左祖轩荧褪劳幂惦逾训棒湃姚副屎揣摈嘉馅第4章贪心方法第4章贪心方法,2023/11/3,设a在SJ中的调度时刻是ta,ta+1，b是SI中该时刻调度的作业。根据以上的讨论有：papb。在SI中，去掉作业b，而去调度作业a，得到的是作业集合I=I-b a的 一个可行的调度表，且I的效益值不小于I的效益值。而I中比I少了一个与J不同的作业。重复上述的转换，可使I在不减效益值的情况下转换成J。从而J至少有和I一样的效益值。所以J也是最优解。证毕。,樟模旺蛇竹容欣珊搏空早弯撂祭磷睫昂臀厅蒂铣沉脾玛黎也炊舜汝羌山古第4章贪心方法
27、第4章贪心方法,2023/11/3,3.如何判断J的可行性,方法一：检验J中作业所有可能的排列，对于任一种次序排列的作 业排列，判断这些作业是否能够在其期限前完成若J 中有k个作业，则将要检查k!个序列方法二：检查J中作业的一个特定序列就可判断J的可行性：对于所给出的一个排列i1i2ik,由于作业ij完成的 最早时间是j，因此只要判断出排列中的每个作业 dijj，就可得知是一个允许的调度序列，从而J是一个 可行解。反之，如果排列中有一个dijj,则将是一个 行不通的调度序列，因为至少作业ij不能在其期限之前完 成。这一检查过程可以只通过检验J中作业的一种特殊的排列：按照作业期限的非降次序排列的
28、作业序列即可完成。,柠捎前屁祖箱逝渡坝脏摊齐窃喻筐滞帚胸亏饭搁缚咙诺券华吭誓里芝卉谁第4章贪心方法第4章贪心方法,2023/11/3,定理4.3 设J是k个作业的集合，i1i2ik是J中作业的一种排列，它使得di1di2dik。J是一个可行解，当且仅当J中的作业可以按照的次序而又不违反任何一个期限的情况来处理。证明：如果J中的作业可以按照的次序而又不违反任何一个期限的情况来处理，则J是一个可行解 若J是一个可行解，则必存在序列r1r2rk，使得drjj,1jk。若，则即是可行解。否则，令a是使得raia的最小下标，并设rb=ia。则有：ba 且 dradrb(为什么?)在中调换ra与rb，所得
29、的新序列 s1s2sk的处理次序不违反任何一个期限。重复上述过程，则可将转换成且不违反任何一个期限。故是一个可行的调度序列 故定理得证。,薪矽浦报睫铭斩劫总挤乞橙彼吩之种敞漠纲丧创五层帘寐槽教迄咐蝇肯党第4章贪心方法第4章贪心方法,2023/11/3,i1 i2 ia ic ikr1 r2 ra rb rk ab dradrb,谩涪减旋潞琼递辙炼蓖它粪鞋诫紊捶勃间忽蛮模魄贰黎剥恕贴芬延凡啤袱第4章贪心方法第4章贪心方法,2023/11/3,5.带有限期的作业排序算法的实现,对当前正在考虑的作业j，按限期大小采用一种“插入排序”的方式，尝试将其“插入”到一个按限期从小到大顺序构造的作业调度序列中
30、，以此判断是否能够合并到当前部分解J中。如果可以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。具体如下：假设n个作业已经按照效益值从大到小的次序，即p1p2pn的顺序排列好，每个作业可以在单位时间内完成，并具有相应的时间期限；且至少有一个单位时间可以执行作业 首先，将作业1存入部分解J中，此时J是可行的；然后，依次考虑作业2到n。假设已经处理了i-1个作业，其中有k个作业计入了部分解J中：J(1),J(2),J(k)，且有 D(J(1)D(J(2)D(J(k),琐荫坛颗肮戳绰嚼啊藏陈观闹阵桃售持卑炎录洲颧蕉羊子磁劣忱烁蒋貉宋第4章贪心方法第4章贪心方法,2023/11/3,对当前正在
31、考虑的作业i,将D(i)依次和D(J(k),D(J(k-1),，D(J(1)相比较，直到找到位置q：使得 D(i)D(J(l)，qlk，且 D(J(q)D(i)此时，若D(J(l)l,qlk,即说明q位置之后的所有作业均可推迟一个单位时间执行，而又不违反各自的执行期限。最后，将q位置之后的所有作业后移一位，将作业i插入到位置q1处，从而得到一个包含k+1个作业的新的可行解。若找不到这样的q，作业i将被舍弃。对i之后的其它作业重复上述过程直到n个作业处理完毕。最后J中所包含的作业集合是此时算法的贪心解，也是问题的最优解。,窍涸疾蒙喷仁桶换挺迎梁酚落秘菇疤脂吗旨祈侧厌赃茄支链稍部煎池缩犯第4章贪心
32、方法第4章贪心方法,2023/11/3,算法4.4 带有限期和效益的单位时间的作业排序贪心算法 procedure JS(D,J,n,k)/D(1),D(n)是期限值。n1。作业已按p1p2pn的顺序排序。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(
33、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,桶论耸际摩茬廖褥蝶杀翼星伯亩更幢秘骤符岩威套镁语春骆海亏溅朴冤敢第4章贪心方法第4章贪心方法,2023/11/3,计算时间分析 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 i
34、k 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)。sn，故最坏情况：TJS=(n2)，特例情况：pi=di=n-i+1,1in最好情况：TJS=(n)，特例情况：di=i,1in,蒸厚膨劝旦馏锤甄衡爹呐蕴弗拉考绒伪少堡挤式缺窍些淀旱只罢阻晌廖物第4章贪心方法第4章贪心方法,2023/11/3,6.一种“更快”的作业排序问题 使用不相交集合的 UNION和FIND算法（见1.4.3节），可以将JS的计算时间降低到数量级接近(n)。（
35、略）,瞄戴瓤潭眶淮箱毅箍自捌讼定确款习砰填眶渺触学组虾狰韩貌楔驰斡掏阎第4章贪心方法第4章贪心方法,2023/11/3,例4.3 设n=5,(p1,p5)=(20,15,10,5,1),(d1,d5)=(2,2,1,3,3)。,最优解是J1,2,4,嘶悔铺份镍亏凿连滓瀑趁挛又抽邻用摔姬平断帚归宏没优序搜揪须烃救铬第4章贪心方法第4章贪心方法,2023/11/3,4.4 最优归并模式,1.问题的描述1）两个文件的归并问题 两个已知文件的一次归并所需的计算时间O(两个文件的元素总数)例：n个记录的文件(n+m)个记录的文件 m个记录的文件(n+m)2）多个文件的归并 已知n个文件，将之归并成一个单
36、一的文件 例：假定文件X1，X2，X3，X4，采用两两归并的方式，可能的归并模式有：X1+X2=Y1+X3=Y2+X4=Y3 X1+X2=Y1+Y3 X3+X4=Y2,超刷哎剂巡命欺美剂凰漆死舟烷殆耻负最佃刽撒航田奶瓷姑纺着亮财荚个第4章贪心方法第4章贪心方法,2023/11/3,二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归并的模式，最终得到一个完整的记录文件。二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，称之为二元归并树。如 归并树的构造 外结点：n个原始文件 内结点：一次归并后得到的文件 在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示
37、的文件归并成其本身所代表的文件,仇渭绍赣城堰滥色春殊啼骂褐岭恬千寺格驳邢糕洪爬拽贴护友纺岿哀盖逊第4章贪心方法第4章贪心方法,2023/11/3,不同的归并顺序带来的计算时间是不同的。例4.5 已知X1,X2,X3是分别为30、20、10个记录长度的已分类文件。将这3个文件归并成长度为60的文件。可能的归并过程和相应的记录移动次数如下：问题：采用怎样的归并顺序才能使归并过程中元素的移动次数最小（或执行的速度最快）,嘘枝堕濒掳隆拎基锹抽圃侗额卢疯豁窑砧绝御优清辈珍狮灭溅驶入粤槛蒜第4章贪心方法第4章贪心方法,2023/11/3,2.贪心求解1)度量标准的选择 任意两个文件的归并所需的元素移动次数
38、与这两个文件的长度之和成正比；度量标准：每次选择需要移动次数最少的两个集合进行归并；处理规则：每次选择长度最小的两个文件进行归并。,(F1,F2,F3,F4,F5)=(20,30,10,5,30),疫登鸵寝颅冶质袋早芦皇庙距抵痹牲唆遗毖赚念坎废急束琳仑郎犊拨俊慎第4章贪心方法第4章贪心方法,2023/11/3,2)目标函数 目标：元素移动的次数最少 实例：为得到归并树根结点表示的归并文件，外部结点中每个文件记录需要移动的次数该外部结点到根的距离，即根到该外部结点路径的长度。如，F4：则F4中所有记录在整个归并过程中移动的总量|F4|*3 带权外部路径长度：记di是由根到代表文件Fi的外部结点的
39、距离，qi是Fi的长度，则这棵树的代表的归并过程的元素移动总量是：最优的二路归并模式：与一棵具有最小外部带权路径长度的二元树相对应。,牡抚仲退唤妻趣惨啊骋坐昨窜景贫岁残艇毛蚌灼愤摇虱连秽灾灰菇挚棺缨第4章贪心方法第4章贪心方法,2023/11/3,算法4.6 生成二元归并树的算法 procedure TREE(L,n)/L是n个单结点的二元树表/for i1 to n-1 do call GETNODE(T)/构造一颗新树T/LCHILD(T)LEAST(L)/从表L中选当前根WEIGHT最小的树，并从中删除/RCHILD(T)LEAST(L)WEIGHT(T)WEIGHT(LCHILD(T)
40、+WEIGHT(RCHILD(T)call INSERT(L,T)/将归并的树T加入到表L中/repeat return(LEAST(L)/此时，L中的树即为归并的结果/end TREE,悯莽擎张卫撬步锐军营川莫蒙镐馒涡诽嘶案蛆唉犀作倔坛糖匆腥磕钱拇诊第4章贪心方法第4章贪心方法,2023/11/3,例4.6 已知六个初始文件，长度分别为：2,3,5,7,9,13。采用算法TREE，各阶段的工作状态如图所示：,仟嘿壤血窥偿黄葱擦肮噶窟屎暂仕离贷鹏涕好沮悲凌叠酣潮愤榷特绽脸流第4章贪心方法第4章贪心方法,2023/11/3,沤跃训辖齿在级刽钓恐糠人揪番续寨东拳杨丹魂从巍晕睛芬序沤送忠边庐第4章贪
41、心方法第4章贪心方法,2023/11/3,时间分析 1)循环体：n-1次 2)L以有序序列表示 LEAST(L):(1)INSERT(L,T):(n)总时间：(n2)3)L以min-堆表示 LEAST(L):(logn)INSERT(L,T):(logn)总时间：(nlogn),嚏链醛本卫毁掸肆棱伍颓浇凭聊亿棕见小柒液绑挝蛆钝羡绰糟谰喇杉舌掳第4章贪心方法第4章贪心方法,2023/11/3,3.最优解的证明 定理3.4 若L最初包含n1个单结点的树，这些树有WEIGHT值为(q1,q2,qn)，则算法TREE对于具有这些长度的n个文件生成一棵最优的二元归并树。证明：归纳法证明 当n=1时，返回
42、一棵没有内部结点的树。定理得证。假定算法对所有的(q1,q2,qn)，1mn,生成一棵最优二元归并树。对于n,假定q1q2qn,则q1和q2将是在for循环的第一次迭代中首先选出的具有最小WEIGHT值的两棵树（的WEIGHT值）；如图所示，T是由这样的两棵树构成的子树：,睫槐贯箱邢务蜀疼淀欠幂藤判侨弊壤镭跌绳咯哑湃照手粒额车殊这慑陈史第4章贪心方法第4章贪心方法,2023/11/3,设T是一棵对于(q1,q2,qn)的最优二元归并树。设P是T中距离根最远的一个内部结点。若P的两棵子树不是q1和q2，则用q1和q2代换P当前的子树而不会增加T的带权外部路径长度。故，T应是最优归并树中的子树。则
43、在T中用一个权值为q1q2的外部结点代换T，得到的是一棵关于(q1q2,qn)最优归并树T”。而由归纳假设，在用权值为q1q2的外部结点代换了T之后，过程TREE将针对(q1q2,qn)得到一棵最优归并树。将T带入该树，根据以上讨论，将得到关于(q1,q2,qn)的最优归并树。故，TREE生成一棵关于(q1,q2,qn)的最优归并树。,疑力剃织列咯唇漱尧注离撼帐柞据姿突判蒂逸猖恐炎禽避莹据楔斗祷希想第4章贪心方法第4章贪心方法,2023/11/3,5.k路归并模式 每次同时归并k个文件。k元归并树：可能需要增加“虚”结点，以补充不足的外部结点。如果一棵树的所有内部结点的度都为k，则外部结点数n
44、满足 n mod(k-1)=1 对于满足 n mod(k1)=1的整数n，存在一棵具有n个外部结点的k元树T，且T中所有结点的度为k。至多需要增加k-2个外部结点。k路最优归并模式得贪心规则：每一步选取k棵具有最小长度的子树归并。,镊绢委腋读秩泪玖蚜藻西川绿紧轮眩纲馋歌郁诬裕似宋译了处辟泻炯悬腺第4章贪心方法第4章贪心方法,2023/11/3,4.5 最小生成树,1.问题的描述 生成树：设G=(V,E)是一个无向连通图。如果G的生 成子图T=(V,E)是一棵树，则称T是G的一棵 生成树(spanning tree)最小生成树:2.贪心策略 度量标准：选择能使迄今为止所计入的边的成本和有最小 增
45、加的那条边。Prim算法 Kruskal算法,鸣胳商穿拢汁皑困像编蹬辕扑代镭搽医佩敷亚柿专歹清一名摘芦宝贡颈蓑第4章贪心方法第4章贪心方法,2023/11/3,3.Prim算法 策略：使得迄今所选择的边的集合A构成一棵树；对将要计入到A中的下一条边(u,v)，应是E中一条当前不在A中且使得A(u,v)也是一棵树的最小成本边。,织烩培喻佰半李编颐超倡宴讶爽蛇蔽诗爹若烦孔湛尺痰霸箭持勿家椰骤毫第4章贪心方法第4章贪心方法,2023/11/3,1,4,6,2,5,3,10,20,25,15,35,边(3,5),成本35,V(TP)=1,2,3,4,5,6,E(TP)=(1,2),(2,6),(3,5
46、),(4,6),(3,6),旨先狮牲霜擞沂托污聪饥寇墙悟聪超祭罐父箍忙样粉井肇钦飞您园新缄页第4章贪心方法第4章贪心方法,2023/11/3,算法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 inte
47、ger 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,埔导霜颤肤萄兑什涛穿晶咯郊瑟宝杠假握徘碰昧洗迅岁疫牢时孜单掌蔓窄第4章贪心方法第4章贪心方法,2023/11/3,NEAR(k)NEAR(l)0 for i2 to n-1 do/找T的其余n-2条边/设j是NEAR(j)0 且COST(j,NEAR(j)最小的下标(T
48、(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,施刚潍式执取翰供锐鼓慑赚确劳颅劣擂盆爆版蔼潘驱国旭馅陶螟穿找吮扬第4章贪心方法第4章贪心方法,2023/11/3,计算复杂性：,第3行花费(e)(e=|E|)时间，第4行花费(1)时
49、间；第69行的循环花费(n)时间；第12行和第1620行的循环要求(n)时间，因此第1121行循环要花费(n)时间。所以PRIM算法具有 的时间复杂度,举吟斟郭雄枫完肩步咆贩剂谩不计形歉沧俺胯佃伴洗喇崩是享涵恍六竖缮第4章贪心方法第4章贪心方法,2023/11/3,另一种PRIM算法,最小生成树中包含了与每个结点v相关的一条最小成本边 证明略 方法：从一棵包含任何一个随意指定的结点而没有边的树开始这一算法，然后再逐条增加边。,秀次弯万躁氯赣苹趋过糖剃昨恍嗡幢蒂蜘躇谰庆摸抉枣织惧梯唐捉撵蓝此第4章贪心方法第4章贪心方法,2023/11/3,4.Kruskal算法（连通）图的边按成本的非降次序排列
50、，下一条计入生成树T中的边是还没有计入的边中具有最小成本、且和T中现有的边不会构成环路的边。,1,2,1,6,2,1,6,2,3,1,6,2,3,4,边(1,2)(3,6)(4,6)(2,6),成本10152025,1,6,2,3,4,5,6,3,4,5,3,4,5,4,5,5,围勤晌蚕严驹敢袍巴授斤叙囤生段憋衡诵扣季屑味幅妥趴亩亩螟虹粒血剂第4章贪心方法第4章贪心方法,2023/11/3,1,4,6,2,5,3,10,20,25,15,35,边(1,4)(3,5),成本30 舍弃35,V(TK)=1,2,3,4,5,6,E(TK)=(1,2),(2,6),(3,5),(4,6),(3,6),
