关于贪心法

         贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况。

        在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。

        从贪心算法的定义可以看出，贪心算法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法是否可以得到最优解。

利用贪心法求解需要注意以下两点：

（1）贪心法求解是否适合。

用贪心法解题很方便，但它的适用范围很小，判断一个问题是否适合用贪心法求解，需要在平时多加练习，依据解题经验来判断是否适合使用贪心算法。如下边的例子：以找币问题为例，如果一个货币系统有3种币值，面值分别为一角、五分和一分，求最小找币数时，可以用贪心法求解；如果将这三种币值改为一角一分、五分和一分，就不能使用贪心法求解。

（2）选择何种贪心标准才能保证求得最优解。

在选择贪心标准时，要对所选的贪心标准进行验证才能使用，不要被表面上看似正确的贪心标准所迷惑。

贪心法的基本原理是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

因此，贪心法存在以下问题：

（1）不能保证求得的最后解是最优解；

（2）不能用来求最大或最小解问题；

（3）只能求满足某些约束条件的可行解的问题。

利用贪心法解题，通常的解题思路为：

（1）建立数学模型来描述问题；

（2）把求解的问题分成若干个子问题；

（3）对每一子问题求解，得到子问题的局部最优解；

（4）把子问题的解局部最优解合成原来解问题的一个解

利用贪心法解题，通常的步骤为以下三步：

（1）从问题的某一初始解出发；

（2）循环求解，求出可行解的一个解元素；

（3）由所有解元素组合成问题的一个可行解。

© 著作权归作者所有,转载或内容合作请联系作者