第4章贪心方法名师编辑PPT课件.ppt
《第4章贪心方法名师编辑PPT课件.ppt》由会员分享,可在线阅读,更多相关《第4章贪心方法名师编辑PPT课件.ppt(82页珍藏版)》请在三一文库上搜索。
1、2018/12/21,第四章 贪心方法,菱耿妒监弧藕屯角镊吁拥唉诅哎萧踪亲角岂左啃捕势圃瓢卓龚说时泵凉悠第4章贪心方法第4章贪心方法,2018/12/21,本章教学要求及重点难点,理解贪心方法的基本思想 掌握背包问题的求解方法 掌握带有限期的作业排序的基本方法 掌握用贪心方法求解单源点最短路径的基本方法。 重点:用贪心方法求背包问题及带有限期作业排序; 难点:用贪心方法求单源点最短路径。,沫编蝴似谰吭浆孪瞒钥竭偏滋毒绥撼誓辊帅驶蝶且操轨膳确智诛器碎信踢第4章贪心方法第4章贪心方法,2018/12/21,4.1 一般方法,1. 问题的一般特征 问题有n个输入,问题的解是由这n个输入的某个子集组成
2、,这个子集必须满足某些事先给定的条件。 约束条件:子集必须满足的条件; 可行解:满足约束条件的子集;可行解可能不唯一; 目标函数:用来衡量可行解优劣的标准,一般以函数的形式给出; 最优解:能够使目标函数取极值(极大或极小)的可行解。 分类:根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同,可分为:线性规划、整数规划、非线性规划、动态规划等。 最优化问题求解 贪心方法:一种改进的分级的处理方法,可对满足上述特征的某些问题方便地求解。,宾睡跌堰整媚峨孔固密榆啃荧团雄卯蛇歌唐寇娇篮蔷搀鲜迭畏钠谋氦肥呀第4章贪心方法第4章贪心方法,2018/12/21,例找零钱 一个小孩买了价值少
3、于1元的糖,并将1元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为25分、10分、5分及1分的硬币。售货员分步骤组成要找的零钱数,每次加入一个硬币。 选择硬币时所采用的贪心算法如下:每一次选择应使零钱数尽量增大。为确保解法的可行性(即:所给的零钱等于要找的零钱数),所选择的硬币不应使零钱总数超过最终所需的数目。 假设需要找给小孩67分,首先入选的是两枚25分的硬币,第三枚入选的不能是25分的硬币,否则将不可行(零钱总数超过67分),第三枚应选择10分的硬币,然后是5分的,最后加入两个1分的硬币。 贪心算法有种直觉的倾向,在找零钱时,直觉告诉我们应使找出的硬币数目最
4、少(至少是接近最少的数目),黔雁月铰剿急吉舔禁叠淌赶炔盛拄充计二善狄玄倘夫戳妹甜魁辕樟虫叹浪第4章贪心方法第4章贪心方法,2018/12/21,2. 贪心方法的一般策略 问题的一般特征:问题的解是由n个输入的、满足某些事先给定的条件的子集组成。 1)一般方法 根据题意,选取一种度量标准。然后按照这种度量标准对n个输入排序,并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解,则不把此输入加到这部分解中。否则,将当前输入合并到部分解中从而得到包含当前输入的新的部分解。 2)贪心方法 这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法 注
5、: 贪心解 最优解 直接将目标函数作为量度标准也不一定能够得到问题的最优解 3)使用贪心策略求解的关键 选取能够得到问题最优解的量度标准。,寐拖禽绎柴甲脯罩彬饶醚九鹅褂得馏毛械普画墙增狰放光拙阉喧桌诫靠蹄第4章贪心方法第4章贪心方法,2018/12/21,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 /
6、判定x是否可以包含在解向量中, 即是否能共同构成可行解/ solutionUNION(solution,x) /将x和当前的解向量合并成新的解 向量,并修改目标函数/ endif repeat return(solution) end GREEDY,郎畅笺滋峭胁忍路闰簧精保拣沟刮透瘸孟雪灿绦吐受窖营兑焙骄喀贤麻邯第4章贪心方法第4章贪心方法,2018/12/21,4.2 背包问题,1.问题的描述 已知n种物品具有重量(w1,w2,wn)和效益值(p1,p2,pn) ,及一个可容纳M重量的背包;设当物品i全部或一部分xi放入背包将得到pi xi的效益,这里,0 xi 1, pi 0。 问题:采用
7、怎样的装包方法才能使装入背包的物品的总效益最大? 分析: 装入背包的总重量不能超过M 如果所有物品的总重量不超过M,即 M,则把所有的物品都装入背包中将获得最大可能的效益值 如果物品的总重量超过了M,则将有物品不能(全部)装 入背包中。由于0xi1,所以可以把物品的一部分装入背包,所以最终背包中可刚好装入重量为M的若干物品(整个或一部分) 目标:使装入背包的物品的总效益达到最大。,驼乔做恳乡舔锯苦匿浆即咐野搓回缠馆醛兵砒梯突盘轴尸足镰弦礁彭亿勾第4章贪心方法第4章贪心方法,2018/12/21,问题的形式描述 目标函数: 约束条件: 可 行 解:满足上述约束条件的任一集合(x1,x2,xn)
8、都是问题 的一个可行解可行解可能为多个。 (x1,x2,xn)称为问题的一个解向量 最 优 解:能够使目标函数取最大值的可行解是问题的 最优解最优解也可能为多个。,穗射布戎菲类螟锨溉幢瓤毛要戊夸博酪晴讯扰那皮酞鼻颅壬摩锹佳尹蓬吠第4章贪心方法第4章贪心方法,2018/12/21,例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,
9、 1) 20 31 (0, 1, 1/2) 20 31.5,娇胡剑讫绣蚀问黎擦礁摧锹辗量枯厌辅膛雪采欺乳颗球穿猿鸣踞亡蔼歉券第4章贪心方法第4章贪心方法,2018/12/21,2. 贪心策略求解 度量标准的选择:三种不同的选择 1)以目标函数作为度量标准 即,每装入一件物品,就使背包背包获得最大可能的效益增量。 该度量标准下的 处理规则: 按效益值的非增次序将物品一件件地放入到背包; 如果正在考虑的物品放不进去,则只取其一部分装满背包:如果该物品的一部分不满足获得最大效益增量的度量标准,则在剩下的物品种选择可以获得最大效益增量的其它物品,将它或其一部分装入背包。 如:若M=2,背包外还剩两件物
10、品i,j,且有(pi 4,wi4) 和(pj 3,wj2),则下一步应选择j而非i放入背包: pi/2 = 2 pj 3,育邹廷拯货讼邦衷守讣娃富蹋束颤揖疤悠眶氮儿宰后述瘴窿本炼箱走峻越第4章贪心方法第4章贪心方法,2018/12/21,实例分析(例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
11、x216/53.1 物品3: 若 x32/10, 则 p3 x33 为使背包的效益有最大的增量,应选择物品2的2/15装包,即 x22/15 最后,背包装满, M=0,故物品3将不能装入背包,x30 。 背包最终可以获得效益值 x1 p1 x2 p2x3 p3 28.2 (次优解,非问题的最优解),蹦谜灾惰芦惦哇帮剧自篷衡编柔陨桶壁朋开琢洁砒奋冒水节捉尾搓母滞尧第4章贪心方法第4章贪心方法,2018/12/21,2)以容量作为度量标准 以目标函数作为度量标准所存在的问题:尽管背包的效益值每次得到了最大的增加,但背包容量也过快地被消耗掉了,从而不能装入“更多”的物品。 改进:让背包容量尽可能慢地
12、消耗,从而可以尽量装入“更多”的物品。 即,新的标准是:以容量作为度量标准 该度量标准下的处理规则: 按物品重量的非降次序将物品装入到背包; 如果正在考虑的物品放不进去,则只取其一部分装满背包;,钧维钞梁诬厚祭钠肥族喘躲牙乌擎狂幸频用吃苔衙谗谊含惭茅苑啸荤撅耍第4章贪心方法第4章贪心方法,2018/12/21,实例分析(例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而言
13、有,也只能选择物品1或2的一部分装入背包。为使背包的按照“统一”的规则,下一步将放入物品2的10/15装包,即 x210/152/3 最后,背包装满M=0,故物品1将不能装入背包,x10 。 背包最终可以获得效益值 x1 p1 x2 p2x3 p3 31 (次优解,非问题的最优解) 存在的问题:效益值没有得到“最大”的增加,古彪渭捻臼播混慎漫教鼠挎壤里晨敷绢掂莹褒裙钉榜帧烂幻枚韭凹飞余踏第4章贪心方法第4章贪心方法,2018/12/21,3)最优的度量标准 影响背包效益值得因素: 背包的容量M 放入背包中的物品的重量及其可能带来的效益值 可能的策略是:在背包效益值的增长速率和背包容量消耗速率之
14、间取得平衡,即每次装入的物品应使它所占用的每一单位容量能获得当前最大的单位效益。 在这种策略下的量度是:已装入的物品的累计效益值与所用容量之比。 故,新的量度标准是:每次装入要使累计效益值与所用容量的比值有最多的增加(首次装入)和最小的减小(其后的装入)。 此时,将按照物品的单位效益值:pi/wi 比值(密度)的非增次序考虑。,翰颂墅芭桌仪汤嚏壳铃表慨麻授幼厨奴巷肺剿锦凯窥舌粕餐过兹性棒磺们第4章贪心方法第4章贪心方法,2018/12/21,实例分析(例4.1) (p1,p2,p3) = (25,24,15), (w1,w2,w3) = (18,15,10) p1/w1p3/w3 p2/w2
15、首先将物品2放入背包,此时x21,背包容量减少w215个单位,还剩余空间M=5。同时,背包获得p224的效益增量。 其次考虑物品1和3。此时,应选择物品3,且就M=5而言有,也只能放入物品3的一部分到背包中 。即 x35/101/2 最后,背包装满M=0,故物品1将不能装入背包,x10 。 背包最终可以获得效益值 x1 p1 x2 p2x3 p3 31.5 (最优解),瑚亿企启昌慨粮涡叠碧能嗽戳败檬而例姨常粹野抗锐罢舷谓浚榆咕么银儡第4章贪心方法第4章贪心方法,2018/12/21,3. 背包问题的贪心求解算法,算法4.2 背包问题的贪心算法 procedure GREEDYKNAPSACK(
16、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,烟淌窘阔伊嚷谷指教引笋排撤归碰养伍
17、廉抵肺曹沥酪宽痉悠橙拯岳江厕躯第4章贪心方法第4章贪心方法,2018/12/21,4. 最优解的证明,即证明:由第三种策略所得到的贪心解是问题的最优解。 最优解的含义:在满足约束条件的情况下,可使目标函数取极(大或小)值的可行解。贪心解是可行解,故只需证明:贪心解可使目标函数取得极值。 证明的基本思想:将此贪心解与(假设中的)任一最优解相比较。 如果这两个解相同,则显然贪心解就是最优解。否则, 这两个解不同,就去找开始不同的第一个分量位置i,然后设法用贪心解的这个xi去替换最优解的那个xi ,并证明最优解在分量代换前后总的效益值没有任何变化。 可反复进行代换,直到新产生的最优解与贪心解完全一样
18、。这一代换过程中,最优解的效益值没有任何损失,从而证明贪心解的效益值与代换前后最优解的效益值相同。即,贪心解如同最优解一样可取得目标函数的最大/最小值。 从而得证:该贪心解也即问题的最优解。,泥翘组磋幻驭列种亚兰笔伊烟轨甫廊蔡喷争性传淬聂徘娟晦够乍懈捎蔷诺第4章贪心方法第4章贪心方法,2018/12/21,定理4.1 如果p1/w1 p2/w2 pn/wn,则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。 证明: 设X=(x1, x2, , xn)是GRDDDY-KNAPSACK所生成的贪心解。 如果所有的xi都等于1,则显然X就是问题的最优解。否则, 设j是使xi1
19、的最小下标。由算法可知, xi=1 1ij, 0xj 1 xi=0 jin 若X不是问题的最优解,则必定存在一个可行解 Y=(y1, y2, , yn),使得: 且应有:,窒做状肾邱拂籍漾灶潦舞烽盘蔗技朱酋微幼镰蹬才础袜类辱药鲁级列机墙第4章贪心方法第4章贪心方法,2018/12/21,设k是使得yk xk的最小下标,则有yk xk: a) 若kj,则xk=1。因为yk xk,从而有yk xk b) 若k=j,由于 ,且对1ij,有yi=xi=1,而对jin,有xi0;故此时若ykxk,则将有 ,与Y是可行解相矛盾。而yk xk,所以yk xk c) 若kj,则 ,不能成立 在Y中作以下调整:
20、将yk增加到xk,因为ykxk,为保持解的可行性,必须从( yk+1,yn)中减去同样多的量。设调整后的解为Z=(z1, z2, , zn),其中zixi,1ik,且有: 则对于Z有:,幽饺匡部烤寄穗室谈很蚀瘴琳剔恩巡翔逆士蛔燃菊惜囊契悉他舌榴组灯吠第4章贪心方法第4章贪心方法,2018/12/21,由以上分析得, 若 ,则Y将不是最优解; 若 ,则或者Z=X,则X就是最优解; 或者ZX,则重复以上替代过程,或者证明Y不是最优解,或者把Y转换成X,从而证明X是最优解,芦区击移肘澳涯嗣脖掣奠念搭豁轿链歹赤弥馆迸除蘸薛囤晰鉴竭辱兴丧餐第4章贪心方法第4章贪心方法,2018/12/21,4.3 带有
21、限期的作业排序,1. 问题描述 假定在一台机器上处理n个作业,每个作业均可在单位时间内完成;同时每个作业i都有一个截至期限di0,当且仅当作业i在其截至期限以前被完成时,则获得pi0的效益。 问题:求这n个作业的一个子集J,其中的所有作业都可在其截至期限内完成。J是问题的一个可行解。 可行解J中的 所有作业的效益之和是 ,具有最大效益值的可行解是该问题的最优解。 如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益值;否则,将有作业无法完成决策应该执行哪些作业,以获得最大可能的效益值。 目标函数: 约束条件:所有的作业都应在其期限之前完成,红葫虎游账告桃玉锥慑滔圆派蹭坞剥节彤磅委袒榜腾
22、炸欲屡揽舞鸳狂直童第4章贪心方法第4章贪心方法,2018/12/21,例4.2 n=4,(p1,p2,p3,p4)(100,10,15,20)和(d1,d2,d3,d4)(2,1,2,1)。可行解如下表所示: 问题的最优解是。所允许的处理次序是:先处理作业4再处理作业1。,链廓湘雪孪吧盲蛮谬央架恰饮郭镊吩乞姥葛化茨增伎获撬军靳鸯惹癸悯窃第4章贪心方法第4章贪心方法,2018/12/21,1. 带有限期的作业排序算法,1) 度量标准的选择 以目标函数 作为量度。 量度标准:下一个要计入的作业将是使得在满足所 产生的J是一个可行解的限制条件下让 得到最大增加的作业。 处理规则:按pi的非增次序来考
23、虑这些作业。,惶亿鳃洼酸戍提擞四渐哦港臂噪人识厦锐锣馆体恨呼橱蹄东乓哀焊渠冰备第4章贪心方法第4章贪心方法,2018/12/21,例:例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均不能构成新的可行解,作业3和2将被舍弃。 故最后的J=1,4,最终效益值120(问题的最优解),笔德愁场点筋衷蒋琵蝉挥撕驹瘸掣情耍娠湾氧僧纂繁淬陨娄耶瘴误仔
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贪心 方法 名师 编辑 PPT 课件
链接地址:https://www.31doc.com/p-1530317.html