贪心算法

http://blog.csdn.net/xywlpo/article/details/6439048

贪心算法的设计思想

         贪心算法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解,但不能总获得整体最优解,通常可以获得近似最优解。

引例 [找零钱]

一个小孩买了价值少于1美元的糖,并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数,每次加入一个硬币。选择硬币时所采用的贪婪准则如下:每一次选择应使零钱数尽量增大。为保证解法的可行性(即:所给的零钱等于要找的零钱数),所选择的硬币不应使零钱总数超过最终所需的数目

引例分析

为使找回的零钱的硬币数最小,不考虑找零钱的所有各种方案,而是从最大面值的币种开始,按递减的顺序考虑各币种,先尽量用大面值的币种,只当不足大面值币种的金额才会去考虑下一种较小面值的币种。这就是在采用贪婪法。这种方法在这里之所以总是最优,是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1,5和11单位的硬币,而希望找回总额为15单位的硬币,按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。但最优的解答应是3个5单位面值的硬币。

贪心法的求解过程 

           用贪心法求解问题应该考虑如下几个方面:

(1)候选集合C:为了构造问题的解决方案,有一个候选集合C作为问题的可能解,即问题的最终解均取自于候选集合C。例如,在付款问题中,各种            面值的货币构成候选集合。

(2)解集合S:随着贪心选择的进行,解集合S不断扩展,直到构成一个满足问题的完整解。例如,在付款问题中,已付出的货币构成解集合。

(3)解决函数solution:检查解集合S是否构成问题的完整解。例如,在付款问题中,解决函数是已付出的货币金额恰好等于应付款。

(4)选择函数select:即贪心策略,这是贪心法的关键,它指出哪个候选对象最有希望构成问题的解,选择函数通常和目标函数有关。例如,在付款             问题中,贪心策略就是在候选集合中选择面值最大的货币。

(5)可行函数feasible:检查解集合中加入一个候选对象是否可行,即解集合扩展后是否满足约束条件。例如,在付款问题中,可行函数是每一步选              择的货币和已付出的货币相加不超过应付款。

贪心法的一般流程

Greedy(C)  //C是问题的输入集合即候选集合
{
    S={ };  //初始解集合为空集
    while (not solution(S))  //集合S没有构成问题的一个解
    {
       x=select(C);    //在候选集合C中做贪心选择
       if feasible(S, x)  //判断集合S中加入x后的解是否可行
          S=S+{x};
          C=C-{x};
    }
   return S;

贪心法的基本要素

      对于一个具体的问题,怎么知道是否可用贪心算法解此问题,以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。

      但是,从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质:贪心选择性质最优子结构性质

子问题:假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,对于任何一个整数k,1 < k < n,以Dk作为问题的初始状态,来进行以后的决策,这样的问题就成为是原问题的一个子问题。

1.贪心选择性质

      所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,换句话说,当考虑做何种选择的时候,我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。

贪心算法以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。

      对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2.最优子结构性质

       当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

贪心法的应用

  • 哈夫曼编码
  • 0-1背包问题
  • 磁盘文件的存储
  • 生产调度问题
  • 信息查询

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

一文看懂主成分分析

主成分分析法是数据挖掘中常用的一种降维算法,是Pearson在1901年提出的,再后来由hotelling在1933年加以发展提出的一种多变量的统计方法,其最主...

13.9K40
来自专栏海天一树

AtCoder Beginner Contest 099 解题报告

https://abc099.contest.atcoder.jp/assignments

10020
来自专栏PPV课数据科学社区

深度学习( Deep Learning )软件资源列表

? 列表源自http://deeplearning.net/software_links/,本文进行分类整理。 星号代表对软件库的推荐度,考虑了适用范围、开发...

32970
来自专栏AI科技大本营的专栏

霉霉 vs AI:谁的歌词写的更好

翻译 | AI科技大本营(rgznai100) 参与 | Shawn 从小到大我一直都是Taylor Swift的死忠粉。上初中时,我的 iPod Nano 里...

36570
来自专栏小樱的经验随笔

利用向量积(叉积)计算三角形的面积和多边形的面积

利用向量积(叉积)计算三角形的面积和多边形的面积: 向量的数量积和向量积: (1)  向量的数量积 ? (1)  向量的向量积 两个向量a和b的叉积(向量积)可...

51190
来自专栏封碎

一些重要的算法 博客分类: 算法 算法网络应用网页游戏领域模型游戏

      下面是一些比较重要的算法,原文 罗列了32个,但我觉得有很多是数论里的或是比较生僻的,和计算机的不相干,所以没有选取。下面的这些,有 的我们经常在用...

11910
来自专栏一个会写诗的程序员的博客

勾股定理·圓周率·無窮級數·微積分勾股定理圓圓周率定义1定义2定义3代数数学分析数论概率论统计学圆的内接正多边形和外接正多边形歐拉公式三角函數分析微積分宇宙運行軌道萬有引力定律電磁場方程相對論量子力學

量子力学理论在20世纪初期诞生,而沃利斯圆周率公式已经存在了数百年,但这两者之间的内在关联直到今天才被发现。

11710
来自专栏钱塘大数据

32类计算机与数学领域最为重要的算法

导读: 奥地利符号计算研究所的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家,他请这些科...

31880
来自专栏封碎

当今世界最为经典的十大算法 博客分类: 经典文章转载 算法数据结构网络应用数据挖掘J#

本文转载自July CSDN博客:http://blog.csdn.net/v_JULY_v/archive/2011/03/07/6228235.aspx

27220
来自专栏marsggbo

计算某年某月的某一天是星期几的算法

说多了没意思,直接送上公式。 W = (Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + D          ...

25080

扫码关注云+社区

领取腾讯云代金券