贪心法(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-难度问题。不同的人可能有不同的“优化”策