贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法的基本思路:
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
重量:28 20 15
价值:28 20 15
附:本题是个DP问题,用贪心法并不一定可以求得最优解,以后了解了动态规划算法后本题就有了新的解法。
备注:
贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
所以需要说明的是,贪心算法可以与随机化算法一起使用,具体的例子就不再多举了。(因为这一类算法普及性不高,而且技术含量是非常高的,需要通过一些反例确定随机的对象是什么,随机程度如何,但也是不能保证完全正确,只能是极大的几率正确)
分享到:
相关推荐
贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法
贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法
贪心算法、分治算法和动态规划的区别 贪心算法和动态规划.pdf
贪心算法 贪心算法的理解 贪心算法的算法 贪心算法的讲解
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优解要穷尽所有可能而...
贪心算法 找零钱 c语言 简洁 绝对无误
贪心算法和动态规划以及分治法的区别? (1) 贪心算法和动态规划.pdf
TSP贪心算法C++ TSP贪心算法C++
算法作业-贪心算法论文含实例,可以借鉴其中的算法原理。加深自己的理解
算法这么课程的结课论文,以最短路径算法为例描述贪心算法
用贪心算法解单源最短路径问题 明确单源最短路径问题的概念;利用贪心算法解决单源最短路径问题;并通过本例熟悉贪心算法在程序设计中的应用方法。
贪心算法 背包问题 c语言 绝对无误 运行成功
贪心算法之最优合并问题
实验2装箱问题-贪心算法
活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是在8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
使用贪心算法求解tsp问题,使用vc实现,资源中包含有程序的文档,包含tsp问题说明、贪心算法分析和程序源码。
流水作业调度C++(贪心算法)流水作业调度C++(贪心算法)流水作业调度C++(贪心算法)
贪心算法贪心算法贪心算法贪心算 背包问题背包问题背包问题
多机调度问题的贪心算法实现。示例代码,可直接在VC上运行。
用贪心算法解决背包问题,用netbeans做的。百分百下载就可以直接运行。JAVA 源文件。