贪心法思想及其运用.doc

贪心法思想及其运用摘要:主要介绍贪心算法（又称贪婪算法）的基本思想，以及如何利用贪心算法来求解问题，如何选择最佳的贪心算法的策略，以及贪心算法在一些数学问题上的运用。关键词：贪心算法 最优 策略 正文：贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对一些问题它能产生整体最优解或者是整体最优解的近似解。贪心算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。一定要注意，选择的贪婪策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略影响，也就是说某个状态以后的过程不会影响以前的状态，只与当前状态有关，也称为这种特性为无后效性。因此，适应用贪婪策略解决的问题类型较少，对所采用的贪婪策略一定要仔细分析其是否满足无后效性。为了说明在使用贪心算法中选择策略是关键，下面这个例子可以充分的说明这个问题：题目：设有n个正整数，将他们连接成一排，组成一个最大的多位整数。例如:n=3时，3个整数13,312,343,连成的最大整数为:34331213第一种策略：把整数按从大到小的顺序连接起来，题目中的例子正好符合这个策略；第二种策略：先把整数化成字符串，然后再比较a+b和b+a，如果a+bb+a，就把a排在b的前面，反之则把a排在b的后面。许多同学开始看到这个题目的时候会毫不犹豫的选择第一种策略，这种策略表面上看起来是对的，从大到小排列之后，最终的数肯定会是最大的结果，但实际上这种策略师错误的，反例有很多，比如说当n=2时，2个整数为12，121 按照第一种策略就会组成12112，而正确的结果为12121，按照第二种策略的结果正是12121。由此可见算法策略的选择是非常关键的，会直接影响到最终结果的正确性。当然上面的例子也可以不用贪心算法来实现，但是我们发现用贪心算法来解决这个问题还是比较简单的，很容易理解其实现过程。由此我们也发现，贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。贪心算法的基本思路是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止，简要归纳为以下几点：1. 建立数学模型来描述整个数学问题；2. 把求解的问题分成若干个子问题；3. 对每一子问题求解，得到子问题的局部最优解；4. 把子问题的解局部最优解合成原来解问题的一个解。贪心算法虽然能使一些问题求解比较简单，但是该算法任然存在以下一些问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。实现该算法的过程可以简要概括为：从问题的某一初始解出发；while 能朝给定总目标前进一步 do 求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；贪婪算法策略在数据结构课程中的算法也有广泛的应用，如霍夫曼树、构造最小生成树的Prim算法和Kruskal算法的决策过程，都是使用的贪婪算法策略。教材上也举出了一些经典的实例，通过这些例子，我们可以感觉到使用贪心算法可以使问题逐步简化，最终达到目标结果。下面举一个贪心算法的经典问题，即背包问题,这个问题我们可以了解到贪心算法的特点及应对某些问题的不足之处。问题如下：有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品ABCDEFG重量35306050401025价值10403050354030这个问题当时也是数据结构的一个课后习题，但是我遇到这个问题的第一反应就是要使背包中的物品总价值最大，我可以先计算出每个物品的性价比，然后从性价比高的物品选起，直到达到背包的总容量。我的这个想法看起来还不错，也许刚好能使背包装满，而却物品也不会出现需要拆分，但是实际上是不可行的。一般来讲这个问题有三种策略：第一种策略：选取价值最大者；第二种策略：选取重量最小；第三种策略：选取单位重量价值最大的物品。然而这三种策略都有其不足之处，反例如下：第一种策略反例(M=30)物品ABC重量291515价值352020第二种策略反例（M=30）物品ABC重量291515价值351010第三种策略反例（M=30）物品ABC重量2999价值291010由此可见这三种策略均不完全，不能解决问题。这也说明了用贪心法也不一定能得到最优解，策略在实行前一定要认真考虑其是否全面，是否具有无后向性。对与本题目，在第三种策略上稍作改动还是可以解决的，把第三种策略改为：对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的。这个做法对本体来讲还是可以的，因为题目中不存在所举的反例这样的情况。但是实际上这种做法也存在着问题，反例和表格中的反例一样。从上面的例子可以看出，利用贪心算法解题，需要解决两个问题：一是问题是否适合用贪心法求解。我们看一个找币的例子,如果一个货币系统有3种币值,面值分别为一角、五分和一分，求最小找币数时，可以用贪心法求解；如果将这三种币值改为一角一分、五分和一分，就不能使用贪心法求解。用贪心法解题很方便，但它的适用范围很小，判断一个问题是否适合用贪心法求解，没有一个通用的方法。二是确定了可以用贪心算法之后，如何选择一个贪心标准，才能保证得到问题的最优解。在选择贪心标准时，我们要对所选的贪心标准进行验证才能使用，不要被表面上看似正确的贪心标准所迷惑。贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。但我们选择贪心法来解决问题的时候我们一定要慎重考虑是否符合贪心法使用的条件，但我们选择了贪心法来解决问题的时候，我们要