第4章4（贪心动态）.ppt

第 四 章 基本的算法策略;4.4 贪婪算法 贪婪算法（也叫贪心算法、登山法） 我们来看一个找硬币的例子： 例1：假设有四种硬币，它们的面值分别为二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。 （要求：所拿出的硬币个数是最少 。） ;这里，我们使用了这样的找硬币算法： 首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。总共用六枚硬币，事实说明这是最好的结果。这个找硬币的方法实际上就是贪婪算法。; 顾名思义，贪婪算法总是以当前情况为基础，而不考虑全部各种可能的情况，作出在当前状态看来是最好的选择。也就是说贪婪算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，我们希望贪婪算法得到的最终结果也是整体最优的。上面所说的找硬币算法得到的结果就是一个整体最优解。 但贪婪算法并不是对所有问题都能得到整体最优解。 ;例2．砝码称物 砝码的种类分别为11克、5克和1克，待称的物体是15克。（所用砝码个数最少） 用贪婪算法应先选一个11克的，然后选四个1克的，共用五个砝码。 但这不是最优结果，实际只要用三个5克的砝码就够了。 所以贪婪算法并不能保证得到的总是最优结果，但对于一些除了“穷举”方法外没有有效算法的问题，用贪婪算法往往能很快地得出较好的结果，如果此较好结果与最优结果相差不是很多的话，此方法还是很实用的。;贪心方法适合的问题： 有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的。那些使目标函数取极值（极大或极小）的可行解，称为最优解。 贪心方法是求解这一类需求取最优解的问题的一个直接有效的方法。贪心方法是一种分级处理方法，首先根据题意，选取一种量度标准。然后按这种量度标准对这n个输入排序，并按序一次输入一个量。如果这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。; 4.4.1 可绝对贪婪问题 4.4.2 相对或近似贪婪问题 4.4.3 贪婪策略算法设计框架;【例2】数列极差问题 　 在黑板上写了N个正整数作成的一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为M=max-min。 问题分析 算法设计 数据结构设计 算法分析 上节 下节;问题分析 我们通过实例来认识题目中描述的计算过程。对三个具体的数据3，5，7讨论，可能有以下三种结果： （3*5+1）*7+1=113、（3*7+1）*5+1=111、（5*7+1）*3+1=109 由此可见，先运算小数据得到的是最大值，先运算大数据得到的是最小值。 上节 下节; 下面再以三个数为例证明此题用贪心策略求解的合理性,不妨假设：ab=a+k1c=a+k1+k2，k1,k20，则有以下几种组合计算结果： 1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+1 2)(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+1 3)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1 显然此问题适合用贪婪策略,不过在求最大值时，要先选择较小的数操作。反过来求最小值时，要先选择较大的数操作。这是一道两次运用贪心策略解决的问题。 上节 下节;算法设计 1）由以上分析，大家可以发现这个问题的解决方法和哈夫曼树的构造过程相似，不断从现有的数据中，选取最大和最小的两个数，计算后的结果继续参与运算，直到剩余一个数算法结束。 2) 选取最大和最小的两个数较高效的算法是用二分法完成， 这里仅仅用简单的逐个比较的方法来求解。 注意到由于找到的两个数将不再参与其后的运算，其中一个自然地是用它们的计算