贪心法

来自计算思维百科
跳转至: 导航搜索
贪心法1.png

贪心法(Greedy Method)解此类问题的设计思想是将待求解的问题分解成若干个子问题进行分步求解,且每一步总是做出当前最好选择,即得到局部最优解,再将各个局部最优解整合成问题的解。

基本描述

贪心法广泛应用于最优化问题求解中。所谓最优化问题 (Optimization Problem),是指寻找一组参数值,在满足一定的约束条件下,使得目标函数的值达到最大或最下。最优化问题广泛应用于生活、工业、经济、管理等各个领域。如生产安排中,如何在现有人力物力的条件下,合理安排几种产品的生产,使总产值最高或总利润最大;出行时,如何用最短的时间到达目的地等。

贪心法(Greedy Method)解此类问题的设计思想是将待求解的问题分解成若干个子问题进行分步求解,且每一步总是做出当前最好选择,即得到局部最优解,再将各个局部最优解整合成问题的解。它体现了一种“快刀斩乱麻”的思想,以当前和局部利益最大化为导向的问题求解策略。

贪心算法是最接近于人类日常思维的一种问题求解方法,且由于优化问题在生活中比比皆是,因此贪心法的应用在生活和工作中处处可见。如,公司招聘新员工是从一批应聘者中招收最能干的人,学校招生是从众多报考者中招收一批最好的学生,这种按照某种标准挑选最接近该标准的人或物的做法就是贪心算法。商场找零时,希望货币张数最少,收银员也会贪心选择从大额货币开始支付。

使用方法及步骤

步骤一:建立数学模型来描述问题;

步骤二:把求解的问题分成若干个子问题;

步骤三:对每一子问题求解,得到子问题的局部最优解;

步骤四:把子问题的解局部最优解合成原来解问题的一个解;

应用

贪心法是最接近人类日常思维的一种问题求解方法,且由于优化问题在生活中比比皆是,因此贪心法的应用在生活和工作中处处可见,工业、经济、管理等各个领域。

田忌赛马

中国古代历史故事“田忌赛马”是大家所熟知的。战国时期,齐威王与大将田忌赛马,齐威王和田忌各有三匹好马:上马,中马与下马。比赛分三次进行,每赛马以千金作赌。由于两者的马力相差无几,而齐威王的马分别比田忌相应等级的马要好,所以一般人都以为田忌必输无疑。但是田忌采纳了门客孙膑的意见,用下马对齐威王的上马,用上马对齐威王的中马,用中马对齐威王的下马,结果田忌以2比1胜齐威王而得千金。

这里孙膑所采用的策略就是贪心法。将齐王的马、田忌的马均按上、中、下马顺序排列,齐王依次出马,田忌的贪心选择策略是:

  1. 若剩下的最强的马都赢不了齐王剩下的最强的马,选择用最差的一匹马对阵齐王最强的马;
  2. 若剩下的最强的马可以赢齐王剩下的最强的马,选择用这匹马去赢齐王剩下的最强的马;
  3. 若剩下的最强的马和齐王剩下的最强的马打平的话,可以选择打平或者用最差的马输掉比赛。

最小生成树

贪心策略也指导着实际工程建设,如铺设管道、光缆、建设公路等。假设要在n个城市之间铺设光缆,铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,问如何铺设,使得 n 个城市的任意两个之间都可以通信,且使铺设光缆的总费用最低。这一问题可用图论中的最小生成树求解,而求解最小生成树的两个算法都是贪心算法。

                      9.2.7.png


                                    图1 最小生成树

假设图1(a),图中顶点表示城市,边上权值表示两个城市之间铺设电缆的费用。

图的生成树含图中全部n个顶点,但只有边集合的n-1条边,且不构成回路,即生成树中任何两个顶点之间有路径。一个图的生成树不是唯一的,如图1(a)中选择AB、BC、DA三条边构成生成树,选择AC、AB、DC边也构成生成树。在图的所有生成树中边上权值之和最小的生成树称为图的'最小生成树'(Minimum Spanning Tree)。

用贪心法求解最小生成树,其中一种贪心选择策略是:贪心选择权值最小的边,若与之前加入的边构成回路,则放弃;否则,加入最小生成树。图1(a)的最小生成树计算过程为:

  1. 贪心选择边AD;
  2. 贪心选择边DC,不构成回路;
  3. 贪心选择边AC,构成回路A->D->C->A,放弃;
  4. 贪心选择边DB,不构成回路,结束。

图1(a)的最小生成树如图1(b)所示。最小生成树也可用在网络路由中。

应用案例

应用1-找零

案例:例如,人民币中硬币的面额有1角、5角、1元,我们如何利用这些面额的硬币给出4元8角的找零?

解决步骤:

4元8角可以用很多种方式给出,但是一般生活中找零遵循的原则是硬币越少越好,所以我们需要给出找零情况的最优解。对于4元,四个1元的为当前最优;对于8角,则是一个5角,三个3角为当前最优。所以,最后我们找出四个1元、一个5角、三个3角。

应用2-公司招聘

案例:公司招聘新员工招聘条件如下:年龄18~30岁,形象良好,有2年工作经验,会讲粤语。王建国和李革命都来应聘该公司,但是王建国除了年龄35岁之外其他都符合招聘条件,而李革命是应届毕业生,除了没有工作经验外其他条件都符合。公司人力资源经理如果更在乎年龄,那么他会选择李革命,如果更在乎经验,那么必然会选择王建国,这就是贪心选择最合适的人。

应用3-铺设光缆

案例:要在4个城市之间铺设光缆,铺设光缆费用很高,且各个城市之间铺设光缆的费用不同,问如何铺设,使得4个城市的任意两个之间都能通信,且铺设光缆的费用最低?

解决步骤: 步骤一:建立数学模型来描述问题,这个问题可以用下图表示,A、B、C、D代表着四个城市,直线或曲线边上的数字代表两个城市之间铺设光缆的费用;

贪心法2.png

步骤二:每次选择最小费用的边,但是不能构成回路,因为构成回路就会造成线路重复浪费;

步骤三:最后铺设方式见下图。

贪心法3.png

可以体现的计算思维

规划指的是妥善运用系统能力,有效地利用既有的资源,避免浪费,是使问题得到最优求解的方法。在实际生活中有很多问题因为各种因素的限制都无法找出最优解,所以我们只能在约束下尽可能地使问题的解或者方案最符合要求。贪心法体现了计算思维中的“规划”特点。