算法设计与分析_11算法设计-贪婪算法.pptx

算法设计与分析;贪婪算法（greedy algorithms,也叫登山法）;顾名思义，贪婪算法总是作出在当前看来是最好的选择。也就是说贪婪算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，我们希望贪婪算法得到的最终结果也是整体最优的。上面所说的找硬币算法得到的结果就是一个整体最优解。虽然贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。如图的单源最短路径问题，最小生成树问题等。在一些情况下，即使贪婪算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。;例1．选取砝码 设天平有一些25克的砝码，一些10克的砝码，一些5克的砝码和一些1克的砝码。现要称 63克的物体，问至少需要用几个砝码。 用贪婪算法，为了砝码数最少，在不超过 63克的前提下，每次都尽量选择大的砝码，即头两次选25克的，然后选一个10克的，最后选三个1克的。总共用六个砝码，事实说明这是最好的结果。;如果问题改成：砝码的种类分别为11克、5克和1克，待称的物体是15克。用贪婪算法应先选一个11克的，然后选四个1克的，共用五个砝码。这不是最优结果，只要用三个5克的砝码就够了。 贪婪算法虽不能保证得到最优结果，但对 于一些除了“穷举”方法外没有有效算法的问 题，用贪婪算法往往能很快地得出较好的结果，如果此较好结果与最优结果相差不是很多的话，此方法还是很实用的。;例2. 背包问题 设有n=8个体积分别为54，45，43，29，23， 21，14，1的物体和一个容积为C=110的背包， 问选择哪几个物体装入背包可以使其装的最满。 如直接用贪婪算法，将物体由大到小顺次 装入背包，到装不下时再逐个试装更小的一些，直至试到最小的一个或装满为止。按此处所给 数据，先装入54和45两个，容积尚余11，最后 只能再装入体积为1的一个，总体积达到100， 并不算太满。此方法的好处是节省时间，主要 的运算时间是用来对n个元素进行排序，故其复杂性是O（nlogn）。;如果对上述算法作一些改进，可得到更好的结果。先从n个物体中试着取j个总体积不超过C的装入背包，剩下的(n-j)个物体则利???贪婪算法尽量往里装。此j值从零开始逐渐增加，反复进 行试探，直至j达到某预先给定的常数k(0kn)，最后从这些结果中取其最好的一个。如果在试 探中能得到一个完全装满的方案，则此过程就可提前结束。因为从n个物体中取出j个共有 种方案，此值随着j的增加而增加较快，但可以 证明此改进算法的复杂性为O（knk+1）,因k是常数，故仍为多项式界的算法。;按本例所给数值，取j=0时，因就是前述普通贪婪算法，已经得到100的结果；取j=1时，共有8种方案，当用29或23先装入时，可得到 54+29+23+1=107的更好结果；取j=2时，共有 28种方案，其中有能将背包完全装满的结果 （43+23+29+14+1=110）。故知此问题当取k≥ 2时就可得到最优解。;当n不太大时，适当的取k值，此改进方法常常可以得到最优解，但不能因此就说一般背包问题有多项式算法。当n增大时，k不能随着n不断的加大，如k随n增大而同时加大，其复杂性就 是指数型而不是多项式型的了，而如k取值较小，又不能保证得出最优解。;例3．巡回推销员问题 设有5座城市，城市间的距离矩阵为：;将城市间的距离从小到大排列有： d24(1),d13(2),d15(2),d25(3),d45(6),d35(9),d34(9), d12(14),d14(16),d23(25)。;d24(1)； d24(1)+d13(2)； d24(1)+d13(2)+d15(2)；;例4 设有六个??市，其坐标分别为a(0,0), b:(4,3), c:(1,7), d:(15,7), e(15,4), f:(18,0)。如下图所示：;6座城市间的距离矩阵为：;用贪婪算法，先将任两城市间的连线距离按从小到大的次序排列，然后从中逐个选择。但有两种情况的连线应舍弃： 使任一城市的度数（连线数）超过2的连线必须舍弃； 在得到经过所有点的回路前就形成小回路的连线必须舍弃。 距离按从小到大的次序排列:;按贪婪算法原则，其选择过程如下： Dde； Dde+Dab； Dde+Dab+Dbc； Dde+Dab+Dbc+Def； Dde+Dab+Dbc+Def+[Dae]；(形成小回路，舍弃) Dde+Dab+Dbc+Def+[Ddf]；(形成小回路，舍弃) Dde+Dab+Dbc+Def+[Dbe]；(b顶点度数超过2，舍弃) Dde+Dab+Dbc+Def+[Dbd]；(b顶点度数超过2，舍弃) Dde+Dab+Dbc+Def+Dcd； Dde+Dab+Dbc+Def+Dcd+[Dbf]；(b顶点度数超过2，舍弃)