贪心算法--------------------------

现在程序越来越人工智能化了。。。。。有点跟不上了！

找了点资料。。。。

贪心算法
----------------------------------------
基本思路
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。 　　
3.对每一子问题求解，得到子问题的局部最优解。 　　
4.把子问题的解局部最优解合成原来解问题的一个解。 　

　实现该算法的过程： 　　

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

while 能朝给定总目标前进一步 do 　　

求出可行解的一个解元素； 　　

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

下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。

例题分析
　　
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。 　　

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 　　

物品 A B C D E F G 　　重量 35 30 60 50 40 10 25 　　价值 10 40 30 50 35 40 30 　　

分析： 　　

目标函数：∑pi最大 　　

约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150） 　　

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ 　　

（2）每次挑选所占重量最小的物品装入是否能得到最优解？ 　　

（3）每次选取单位重量价值最大的物品，成为解本题的策略。 　　

值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高
效的算法。 　　

贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。 　　

可惜的是，它需要证明后才能真正运用到题目的算法中。 　　

一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优

解得来的。 　　

对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下： 　　

（1）贪心策略：选取价值最大者。 　　

反例： 　　W=30 　　物品：A B C 　　重量：28 12 12 　　价值：30 20 20 　　

根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。 　　

（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。 　　

（3）贪心策略：选取单位重量价值最大的物品。 　　

反例： 　　W=30 　　物品：A B C 　　重量：28 20 10 　　价值：28 20 10 　　

根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错

误。 　　【注意：如果物品可以分割为任意大小，那么策略3可得最优解】 　　

对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样

的，则优先选择重量小的！这样，上面的反例就解决了。 　　

但是，如果题目是如下所示，这个策略就也不行了。 　
　W=40 　　物品：A B C 　　重量：25 20 15 　　价值：25 20 15 　　

附：本题是个NP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有

了新的解法。

编辑本段备注
　　贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法

。 　　贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式 　　所以

需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类

算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程

度如何，但也是不能保证完全正确，只能是极大的几率正确）


黑色星空，有你精彩，这里只是你的一个起点。。。。。。更多资料请用搜索引擎查找！