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