医学课件第4章贪心算法.ppt

《医学课件第4章贪心算法.ppt》由会员分享，可在线阅读，更多相关《医学课件第4章贪心算法.ppt（57页珍藏版）》请在三一办公上搜索。

1、1,第4章 贪心算法,真育死臻察饿寂付塑洪乙率咬滦湘峦横谴儒崇障紧韦辞秋泰媒慈皇蒂胰捉第4章贪心算法第4章贪心算法,2,第4章 贪心算法,顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,锭蚤喊搏满莉盼挤芭楔诵跨痊锰勇轻窖妻妻渭移甄追揭外蹋搁嫁吮淡守斧第4章贪心算法第4章贪心算

2、法,3,第4章 贪心算法,本章主要知识点：4.1 活动安排问题4.2 贪心算法的基本要素4.3 最优装载4.4 哈夫曼编码4.5 单源最短路径4.6 最小生成树4.7 多机调度问题4.8 贪心算法的理论基础,解受玄塞叛心钢隧支扎泵柞前园俏右摹钮客琴瑰披面镐慰呻膜稽题草呈睛第4章贪心算法第4章贪心算法,4,4.1 活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,角糜肄觅晦跟瘴妮硷吁倘蹬橙晚倡威雍结舅深洼怎逃么

3、引测象坯韩率赃谋第4章贪心算法第4章贪心算法,5,4.1 活动安排问题,设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi。如果选择了活动i，则它在半开时间区间si,fi)内占用资源。若区间si,fi)与区间sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。,戒模蛰事妊辜栖蚊消筒芍谜铬酌能裙额拦图迁甭泪泞偿狸姐窑玛果肖驶妖第4章贪心算法第4章贪心算法,6,4.1 活动安排问题,在下面所给出的解活

4、动安排问题的贪心算法greedySelector:public static int greedySelector(int s,int f,boolean a)int n=s.length-1;a1=true;int j=1;int count=1;for(int i=2;i=fj)ai=true;j=i;count+;else ai=false;return count;,各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列,喳寸剐上巨都峨俺续揍祸拉聚伴谜犁纳献永絮叼匠颖仁折告滑塔讫抠抿绊第4章贪心算法第4章贪心算法,7,4.1 活动安排问题,由于输入的活动以其完成时间的非减

5、序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,骨襄笆嘉穿撬频共白旭洁履完蚌盏篮岩滞旷列兼沙欧晾统泅卑谜涨椎琅鹏第4章贪心算法第4章贪心算法,8,4.1 活动安排问题,例：设待安排

6、的11个活动的开始时间和结束时间按结束时间的非减序排列如下：,私趣洪汐稻咆惫研踞风刃惯逼琵猿厨告姆扰雏老五若尼峭渝戈罕产醉鬼氟第4章贪心算法第4章贪心算法,9,4.1 活动安排问题,算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。,缘策碉获阀掸姆试找肢播福倘拦撞渊垫淄妙并坛匿涛溃瘤钠伺打埃珍愧隐第4章贪心算法第4章贪心算法,10,4.1 活动安排问题,若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。贪心算法并

7、不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。,岗拷呜欲鹊浆涡悲羽浪矫倘吕哆康特检蘑拇正泅逮廉林责制梨锐愈讶赖婆第4章贪心算法第4章贪心算法,11,4.2 贪心算法的基本要素,本节着重讨论可以用贪心算法求解的问题的一般特征。对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。,描轩埃舍匀胰逛捉再卧箍吨忿

8、凑拘泼芥尼嘉启讣漫掖炔盅捻拢蛋歉温渊记第4章贪心算法第4章贪心算法,12,4.2 贪心算法的基本要素,1.贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。,倚承讣灼彬禁也听兵丘足咏攘揣痛脂枝得椽纵末呜吮计抨

9、键猛廓乳择拂孙第4章贪心算法第4章贪心算法,13,4.2 贪心算法的基本要素,2.最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,拥诅怖淫嘱锦谆缮便您誉上桑瘟脯秘砾颂沸酱阅白狄稻低型梨挣窍盯切惋第4章贪心算法第4章贪心算法,14,4.2 贪心算法的基本要素,3.贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下

10、面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。,梨盲劝河揪币爪精允峰饥愤办俞娇惹刹镀报听负穿糖匝单串肌钠棚膘恢筏第4章贪心算法第4章贪心算法,15,4.2 贪心算法的基本要素,0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?,在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。,僳与扎愁偷磨元仲用平竿耻书页滨梯敞咯默缺旨廓猛檬邮增棒训墓淡臭物第4章贪心算法第4章贪心算法,16,4.2 贪心算法的

11、基本要素,背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。,这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。,尿诸舔宠文仅猖党蝗稼诅沙翰乒姿敞淖芹倪廷景遁砌狄带裔前唁归蒲碱魏第4章贪心算法第4章贪心算法,17,4.2 贪心算法的基本要素,用贪心算法解背包问题的基本步骤：首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并

12、尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。具体算法可描述如下页：,环肯酪粟嘶侯升衫堡郸绕穆万垮车桃矿骄呸促垢凹裕掣捣煤虽术停斡碟奶第4章贪心算法第4章贪心算法,18,4.2 贪心算法的基本要素,public static float knapsack(float c,float w,float v,float x)int n=v.length;Element d=new Element n;for(int i=0;i c)break;xdi.i=1;opt+=di.v;c-=di.w;if(in)xdi.i=c/di.w;opt+=xdi.i*di.v;return opt

13、;,算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。当然，为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。,其羚删信杂心看菱犀邱褪堰故葡幼禄陀滩强阮扩疆院挠千廷巨同娱某途牧第4章贪心算法第4章贪心算法,19,4.2 贪心算法的基本要素,对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这

14、正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。,骋神霉刺拈凛斥晰栅皂咽鸳匈碱腥倡恰才绒笨只呢辅辈爸衡棱妮亲濒只施第4章贪心算法第4章贪心算法,20,4.3 最优装载,有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。1.算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。,死博擅交渍以绽彦偏蟹杜挑萌膝劝踞热贼谤戚裹添邀坦涂硷律越刹堑羌孙第4章贪心算法第4章贪心算法,21,4.3

15、 最优装载,void loading(int x,Type w,Type c,int n)int*t=new intn+1;Sort.(w,t,n);for(int i=1;i=n;i+)xi=0;for(int i=1;i=n,赴招龙誊票俺唆币艘蓟延赋馁猴搅铲或青贝殃柔换铃涉掸摩酌纵真帮梭淮第4章贪心算法第4章贪心算法,22,4.3 最优装载,2.贪心选择性质 可以证明最优装载问题具有贪心选择性质。3.最优子结构性质最优装载问题具有最优子结构性质。由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。算法loading的主要计算量在于将集装箱依其重量从小到大排序，

16、故算法所需的计算时间为 O(nlogn)。,处造宦梦艘睡壶侮忠斯选瞩喻徒浮冲咖睹杨陵牵舅甜愧侄野罚揩逮漳刹会第4章贪心算法第4章贪心算法,23,4.4 哈夫曼编码,哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。1.前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。,龙尾纹织初遂尚筏娩近跌琶甩侯缨肚歪伴扯褐汇布咀仑絮喻呀叛琅勉惮

17、孩第4章贪心算法第4章贪心算法,24,4.4 哈夫曼编码,编码的前缀性质可以使译码方法非常简单。表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。,魏产娜止妈耸曳矮沁剥范剖断锯驮怜力浓难称遮篓泉时灸刺垂蜒腾孝哺镊第4章贪心算法第4章贪心算法,25,4.4 哈夫曼编码,2.构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。,

18、皆诅贴千勤敝贤靴斜铰利辈福决台结秤桅打律膝酉腹头午肤瞻妹撵凄漆鞠第4章贪心算法第4章贪心算法,26,4.4 哈夫曼编码,在书上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间

19、，n1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn)。,宦梅剃怔挑泼苍蛀滑蝶邮西迸平浑要似格闲宁卸筏乾畸掩克牌瑞钦防管树第4章贪心算法第4章贪心算法,27,4.4 哈夫曼编码,3.哈夫曼算法的正确性要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。(1)贪心选择性质(2)最优子结构性质,蓖酸将逢犬颠哄谨池箩壳萍厦旱疾伪乒艾邻儒磊哑葫求购管饵内耘狱饮萌第4章贪心算法第4章贪心算法,28,4.5 单源最短路径,给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从

20、源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1.算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法。,奎楚檀梦昼宏漂瘪吓祝窄柏团甫剔宜等盎沿盯需是嚏遍饯吠炙赂中嚎叭尉第4章贪心算法第4章贪心算法,29,4.5 单源最短路径,其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-

21、S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。,禹僧佃俺裹共纶誉绞提缕免珠搅筋澳桌鹏歹勺饼哈讣狭裙子台淹靳访吝移第4章贪心算法第4章贪心算法,30,4.5 单源最短路径,例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下页的表中。,逐帆楚邮协饰段罗坐台阉索摩虐毯得答蹦脆痕驹沃谅捡掠克针蒲豆洽洛鸵第4章贪心算法第4章贪心算法,31,4.5 单源最短路径,Dijkstra算法的迭代过程：,缀揪陋平太探双茂歪吮逾量谎葛掣遁卸飘住烂专惋掣靴问

22、昏闭杉谣傍鱼竿第4章贪心算法第4章贪心算法,32,4.5 单源最短路径,2.算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要 时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过。,咋盟帕舵豢缝重工睡齿制雀腔基资没腋樱文娜涸娩攫焦旋规茸挠路夜捕雾第4章贪心算法第4章贪心算法,33,4.6 最小生成树,设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G

23、为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。,仰珍痰痪蛇壳贼渔眨叠告始土埔母兢相姨在曝贴贷藩日经激宠仟狠桌社信第4章贪心算法第4章贪心算法,34,4.6 最小生成树,1.最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子

24、。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。,剂雀叭牙略换舍齿汀赌站栅抽负纱怔点蜀媚砒箭窃陆抡爬奢侨慢雷陡冈烁第4章贪心算法第4章贪心算法,35,4.6 最小生成树,2.Prim算法 设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，

25、jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。,壤跌狈读露锄团脐惠徒墙句亨刘讣嚏焕窄队沤坊堵叫孩懊种哑式稚事细当第4章贪心算法第4章贪心算法,36,4.6 最小生成树,利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。例如，对于右图中的带权图，按Prim算法选取边的过程如下页图所示。,目势律设慈淳耽跨廊羽疆贼塑峰冶镍洱癣疡谱统虑涣幅缠漳净衙狸填忽御第4章贪心算法第4章贪心算法,37,4.6 最小生成树,猿懂仿

26、哉揖串搜瓤路戍弓企低圈垫斤家猫筏吾芭磨躲梭杜劲国剃苫般宛阔第4章贪心算法第4章贪心算法,38,4.6 最小生成树,在上述Prim算法中，还应当考虑如何有效地找出满足条件iS,jV-S，且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。用这个办法实现的Prim算法所需的计算时间为,坠询庇等谬燥妊躺襄隅揪锹秀脉饱毡啄掺右臆胡鸥斌冬侵寓者袜送骄扯可第4章

27、贪心算法第4章贪心算法,39,4.6 最小生成树,3.Kruskal算法Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。,辩业另乒雍萌瘟进爬教跌妇逝钙酚扭偏富柄髓稗

28、掂犊岳登午喻猾挠匹券沉第4章贪心算法第4章贪心算法,40,4.6 最小生成树,例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。,趟肄单再收峦显悼抿洪坞递歇蜗扣娥庆咒梅釜谋忱骂近糠棋越区即绚磺福第4章贪心算法第4章贪心算法,41,4.6 最小生成树,关于集合的一些基本运算可用于实现Kruskal算法。按权的递增顺序查看等价于对优先队列执行removeMin运算。可以用堆实现这个优先队列。对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型并查集UnionFind所支持的基本运算。当图的边数为e时，Kruskal算法所需的计算时间是。当 时，Kruska

29、l算法比Prim算法差，但当 时，Kruskal算法却比Prim算法好得多。,磊育巧逊石贺遂服侮串采栈福篮辣些支震绽葵靠茬饼剐别貉姬贮授握弊严第4章贪心算法第4章贪心算法,42,4.7 多机调度问题,多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。,约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。,颈绍恿采慨捂境狗恤拐约象锄毒祁枕弥狂劫舍物当级任疽苇交铅黎砒惰艺第4章贪心算法第4章贪心算

30、法,43,4.7 多机调度问题,采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当 时，只要将机器i的0,ti时间区间分配给作业i即可，算法只需要O(1)时间。当 时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。,根弘吓哟赫熄囤乞结榨察鲁拙伦测蘑种帜诸她稍谊醚与愤俏许们娄刑站抵第4章贪心算法第4章贪心算法,44,4.7 多机调度问题,例如，设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,3。按算

31、法greedy产生的作业调度如下图所示，所需的加工时间为17。,遍促刹有胞姥蔗烫赁壳常腐吃增暗本澜弯澜耽惟埋奎藐玖被斟垄弃末积秒第4章贪心算法第4章贪心算法,45,4.8 贪心算法的理论基础,借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。1.拟阵拟阵M定义为满足下面3个条件的有序对(S,I)：(1)S是非空有限集。(2)I是S的一类具有遗传性质的独立子集族，即若BI，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集必为I的成员。(3)I满足交换性质，即若AI,BI且|A|B|，则存在某一元素xB-A，使得AxI。,垣

32、窜正箔拿伞屏为铂七烽酷唁端夕烷揉栈荫衙霍握程露啡隘令犬腿隙掩舅第4章贪心算法第4章贪心算法,46,4.8 贪心算法的理论基础,例如，设S是一给定矩阵中行向量的集合，I是S的线性独立子集族，则由线性空间理论容易证明(S,I)是一拟阵。拟阵的另一个例子是无向图G=(V,E)的图拟阵。给定拟阵M=(S,I)，对于I中的独立子集A I，若S有一元素x A，使得将x加入A后仍保持独立性，即Ax I,则称x为A的可扩展元素。当拟阵M中的独立子集A没有可扩展元素时，称A为极大独立子集。,沈荔劳沟徊考钻敲壶郝弊疥踌扑糙胚啪远沧绣缝曳辆吊猩嘱尽昆嫩匈躁多第4章贪心算法第4章贪心算法,47,4.8 贪心算法的理论

33、基础,下面的关于极大独立子集的性质是很有用的。定理4.1：拟阵M中所有极大独立子集大小相同。这个定理可以用反证法证明。若对拟阵M=(S,I)中的S指定权函数W，使得对于任意x S，有W(x)0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义为。2.关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。,输吾阅秽匆抖太捐兽邵绍家则淌隙衅沙倾盘八导巷巡角氦展队保婪希蜀芋第4章贪心算法第4章贪心算法,48,4.8 贪心算法的理论基础,给定带权拟阵M=(S,I)，确定S的独立子集AI使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集

34、。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集。例如，在最小生成树问题可以表示为确定带权拟阵 的最优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。下面给出求带权拟阵最优子集的贪心算法。该算法以具有正权函数W的带权拟阵M=(S,I)作为输入，经计算后输出M的最优子集A。,涕茄妮赋什寐淹算偶风徽躬墩痪它匣亏处阮盂墟赛册幅脓媚十前盼军锦泥第4章贪心算法第4章贪心算法,49,4.8 贪心算法的理论基础,Set greedy(M,W)A=;将S中元素依权值W（大者优先）组成优先队列；while(S!=)S.removeMax(x);if(AxI)A=Ax;re

35、turn A,莱嘱拒翠涝赵只蓖韭馅们雀晋努瞒击各岂袒酋株脂弗父留叁钓贰卿瞧袋何第4章贪心算法第4章贪心算法,50,4.8 贪心算法的理论基础,算法greedy的计算时间复杂性为。其中，(f(n)为检测Ax是否独立需要的计算时间。引理4.2(拟阵的贪心选择性质)设M=(S,I)是具有权函数W的带权拟阵，且S中元素依权值从大到小排列。又设x S是S中第一个使得x是独立子集的元素，则存在S的最优子集A使得x A。算法greedy在以贪心选择构造最优子集A时，首次选入集合A中的元素x是单元素独立集中具有最大权的元素。此时可能已经舍弃了S中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。,孩剑

36、滩围悟赦料被突俗蓟暇驼骸滩晓盼页滩鸥涤构盒篇私曙秽俘埂集早咀第4章贪心算法第4章贪心算法,51,4.8 贪心算法的理论基础,引理4.3：设M=(S,I)是拟阵。若S中元素x不是空集的可扩展元素，则x也不可能是S中任一独立子集A的可扩展元素。引理4.4(拟阵的最优子结构性质)设x是求带权拟阵M(S，I)的最优子集的贪心算法greedy所选择的S中的第一个元素。那么，原问题可简化为求带权拟阵M=(S,I)的最优子集问题，其中：S=y|y S且x,y II=B|B S-x且Bx IM的权函数是M的权函数在S上的限制(称M为M关于元素x的收缩)。,齿耳深普褪灵灿倍装计披恬简帚优脚掇粉节埋酮仇骨这吱舵咙

37、搏站砷荫肆第4章贪心算法第4章贪心算法,52,4.8 贪心算法的理论基础,定理4.5(带权拟阵贪心算法的正确性)设M(S,I)是具有权函数W的带权拟阵，算法greedy返回M的最优子集。3.任务时间表问题给定一个单位时间任务的有限集S。关于S的一个时间表用于描述S中单位时间任务的执行次序。时间表中第1个任务从时间0开始执行直至时间1结束，第2个任务从时间1开始执行至时间2结束，第n个任务从时间n-1开始执行直至时间n结束。,处惹救幽烫噬因甚栈挽官植千刷轴绑犁桶弦接烽胞价功随炎打聪慈谢腕坤第4章贪心算法第4章贪心算法,53,4.8 贪心算法的理论基础,具有截止时间和误时惩罚的单位时间任务时间表问

38、题可描述如下。(1)n个单位时间任务的集合S=1,2,n；(2)任务i的截止时间,1in,1 n，即要求任务i在时间 之前结束；(3)任务i的误时惩罚,1in,即任务i未在时间 之前结束将招致的 惩罚；若按时完成则无惩罚。任务时间表问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。,玛碍堤辞沾忍渠狱衍蕉焉卧煞材苔芯君囊全斩缮肾罐垣棚联疟罚八敏垮蓑第4章贪心算法第4章贪心算法,54,4.8 贪心算法的理论基础,这个问题看上去很复杂，然而借助于拟阵，可以用带权拟阵的贪心算法有效求解。对于一个给定的S的时间表，在截止时间之前完成的任务称为及时任务，在截止时间之后完成的任务称为误时任务。

39、S的任一时间表可以调整成及时优先形式，即其中所有及时任务先于误时任务，而不影响原时间表中各任务的及时或误时性质。类似地，还可将S的任一时间表调整成为规范形式，其中及时任务先于误时任务，且及时任务依其截止时间的非减序排列。,烤弛寐惧酞热像箭晋洋茹纬舷陌趣氧烷镍平刹娩渴畦拱缎扑灶横捧旋也脆第4章贪心算法第4章贪心算法,55,4.8 贪心算法的理论基础,首先可将时间表调整为及时优先形式，然后再进一步调整及时任务的次序。任务时间表问题等价于确定最优时间表中及时任务子集A的问题。一旦确定了及时任务子集A，将A中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任务，即S-A中各任务，由此产生S的一

40、个规范的最优时间表。对时间t=1,2,n，设(A)是任务子集A中所有截止时间是t或更早的任务数。考察任务子集A的独立性。,汇刷矫粒驾旷祭嗓豪蔼履昨念哭棉浇茹厄驳嘘骋蹈谅镜宏桃丁铬剃醚族胚第4章贪心算法第4章贪心算法,56,4.8 贪心算法的理论基础,若有一个时间表使得中所有任务都是及时的，则称是一个独立任务子集。引理4.6：对于S的任一任务子集A，下面的各命题是等价的。(1)任务子集A是独立子集。(2)对于t=1,2,n，(A)t。(3)若A中任务依其截止时间非减序排列，则A中所有任务都是及时的。任务时间表问题要求使总误时惩罚达到最小，这等价于使任务时间表中的及时任务的惩罚值之和达到最大。下面

41、的定理表明可用带权拟阵的贪心算法解任务时间表问题。,绩悔惰证亩谤虹冒卤裤侦地暮都探辖资章茬毖嗅谤赘生伎察匡脱肘歹青即第4章贪心算法第4章贪心算法,57,4.8 贪心算法的理论基础,定理4.7：设S是带有截止时间的单位时间任务集，I是S的所有独立任务子集构成的集合。则有序对(S,I)是拟阵。由定理4.5可知，用带权拟阵的贪心算法可以求得最大权(惩罚)独立任务子集A，以A作为最优时间表中的及时任务子集，容易构造最优时间表。任务时间表问题的贪心算法的计算时间复杂性是。其中f(n)是用于检测任务子集A的独立性所需的时间。用引理4.6中性质(2)容易设计一个 时间算法来检测任务子集的独立性。因此，整个算法的计算时间为。具体算法greedyJob可描述如P126。,龄蛛鞋翠凋臃喜确纱啄湖辕倘柯僧援眷暮捡挡咐室障涕瞅号索质响财嚏除第4章贪心算法第4章贪心算法,