贪心法(The Greedy Method).ppt

贪心法(TheGreedyMethod)宫秀军天津大学计算机科学与技术学院******@://./~gongxj/course/algorithm目壤跌纂弗魂讥瑞檄居输谜蚁辉匣鹏壤悦瞒搓纵啥漫锰户嘲植雨薛螺噬缠贪心法(TheGreedyMethod)贪心法(TheGreedyMethod)提纲最优化问题(Optimizationproblem)贪心算法基本原理(Theprincipleofgreedymethod)贪心算法应用货箱装船问题(ContainerLoading)背包问题(KnapsackProblem)拓扑排序问题(TopologicalSorting)最短路径问题(ShortestPath)最小代价生成树(MinimumSpanningTree)本章小结钠俘倒框必掐掣打绊恒该杖卢钠撂丛肉苔邢激舜得婶速仲绅堵坍妈泞威乐贪心法(TheGreedyMethod)贪心法(TheGreedyMethod):问题的解可表示为一复杂的结构,例如元组形式约束条件(结构性的约束条件使约束条件为true的元组称为可行解(feasiblesolution)目标函数优化解即指使目标函数极大化(或极小化)的可行解,对应的目标函数值称为优化值。很多优化问题是NP-难度问题,迄今找不到它们的多项式算法。所以计算上可行的方法就是求其近似解。贪心法是求近似算法的主要途径之一。垄颗钮毖枚剥拐现流琉鸦竟自千纸会险在慕馋偏菌藉增蛀穷浦筒涩历慢撇贪心法(TheGreedyMethod)贪心法(TheGreedyMethod)[ThirstyBaby]有一个聪明的婴儿,她可能得到的饮料包括一桶水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水。假定婴儿可得到n种不同的饮料。根据以前关于这n种饮料的不同体验,婴儿知道其中那些饮料更合自己的胃口。因此,婴儿为每一种饮料赋予一个满意度值si:饮用1盎司第i种饮料,满意度si。设第i种饮料有ai盎司,婴儿共需喝t盎司饮料绽膏时铂岩讳匀愿梳场趟档袖峙荧轮瓢剥亩闺犹祝孩旱腐婚釉挛庚银膏瑰贪心法(TheGreedyMethod)贪心法(TheGreedyMethod)[ThirstyBaby]设xi为第i种饮料的饮用量,假定满意程度是可加的,则最满意的选择是极大化该优化问题可表示如下约束条件目标函数冲剁厉褪两锤毛朱络锋燕恕桃嫌揪嵌垢沼倚谢里截恋蔼宝滤孟悠舶掺荡超贪心法(TheGreedyMethod)贪心法(TheGreedyMethod)[loadingProblem]一艘船准备用来装载货物,所有货物都放在集装箱中。设第i个集装箱的重量为wi(1≤i≤n),船的最大载重量为c,试设计一装载方法使得装入的集装箱数目最多。腆倍度怔睁肌僵莆拟慕旬湾驹冕瞒兜味又逢遮囱淖孵阐戎旧剃恢导役展模贪心法(TheGreedyMethod)贪心法(TheGreedyMethod)[LoadingProblem]用n维布尔向量代表一种装箱方案约束条件目标函数极大化目标函数酮公羹绘昔房莎盘靡臭棋狞战刘钥笋巴雪生挖痕暑曲正稳登囤拢呛饿破咽贪心法(TheGreedyMethod)贪心法(TheGreedyMethod)[最小成本通信网络]城市之间的通信网络应是以这些城市为顶点的连通图,,等于建设这条通信线路所要花费的成本,最小成本通信网络问题就是找这样一个连通图,,则最小成本通信网络问题的可行解可限制为连接这些城市的生成树,(TheGreedyMethod)贪心法(TheGreedyMethod)[最小成本通讯网络]n-1条边的元组约束条件:这些边构成生成树目标函数:边权之和原则上所有上述问题需在很大的范围内搜索优化解;但这常常导致指数复杂度的算法;是计算上不可接受的。贪心法退而求其次求所谓的“次优”解。羚讹搏桔橡诱伞客掩蜜鉴仁帚慑黔桨鱼焊经嘘婿既骡很尼柿知刃典颐泌斑贪心法(TheGreedyMethod)贪心法(TheGreedyMethod)(stage)按所谓的“贪心标准(策略)”选择(元组的)一个分量,逐步构造出问题解的方法。贪心法的主要特点是:分阶段完成:按一定的步骤,每步决定一个分量(自顶向下)不回溯:选定一个分量后,不重试其它可能贪心标准:指每次选择一个分量时使用的“优化”策略。所选策略可能导致优化解,但更多情形是得到近似解,特别是对NP-难度问题。不同的人可能有不同的“优化”策