您好, 访客   登录/注册

贪心算法探究

来源:用户上传      作者:

  [摘要]为了在有限的时间内找到问题的最优解或近似解,可以采用贪心算法通过选取最可能到达解的情况来考虑。本文阐述了贪心算法的基本设计思想,即“贪心”思想,探讨了可用此算法解决的问题所应具有的基本性质:最优子结构性质和贪心选择性质,详细描述了贪心算法的实现过程,并通过具体的实例分析了贪心算法在日常生活中的应用。贪心算法是很接近人们日常思维的算法思想,它不能保证求得问题的最优解,但至少是最优解的近似解。
  [关键词]最优解 近似解 贪心算法 最优子结构 贪心选择
  [中图分类号]TP301.6 [文献标识码]A
  
  一、引言
  求最优解问题时,在解的范围确定的情况下,常采用枚举或递归法找出该问题的所有解,然后一一比较它们,直到找到最优解。但当解的范围特别大时,采用上述两种方法的效率非常低,可能在有限的时间内不能找到问题的解。在这种情况下,如果一个问题的最优解只能用蛮力法穷举得到,则可以采用贪心算法,通过选取那些最可能到达解的情况来考虑[1]。
  二、贪心算法的设计思想
  面临复杂问题时,通常把它分解为若干个类似的子问题进行求解。动态规划法把一个复杂问题分解为若干个相互重叠的子问题,通过求解子问题形成的一系列决策得到原问题的解;而贪心法把一个复杂问题分解为一系列较为简单的局部最优选择,每做一次选择就将所求问题简化为规模更小的子问题。
  贪心算法也称为登山法,它的根本恩想是逐步到达山顶,即逐步获得问题的最优解,是解决最优子问题时的一种简单但适用范围有限的策略。正如它的名字一样,贪心法的精神是“今朝有酒今朝醉”,在解决问题的策略上采用“目光短浅”的方针,因此,每一步面临选择时,贪心法都作对当前来讲是最有利的选择,不考虑该选择对将来是否有不良影响[2]。每一步都根据当前已有的信息做出选择,而且一旦做出了选择,就不会改变。这种策略是一种简单有效的方法,但它不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能够获得整体最优解,但通常是最优解的近似值。
  三、贪心算法的性质
  对于一个问题,如何知道是否可用贪心法求解,以及能否得到问题的最优解呢?从许多可以用贪心算法求解的问题中可以发现,这类问题一般具有以下两个性质:
  1.最优子结构性质
  当一个问题的最优解包含其子问题的最优解时,称该问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划法或贪心法求解的关键特征。遇到具体问题时,哪些该用贪心算法求解,哪些该用动态规划法求解呢?用贪心算法求解问题,每一步操作都对结果产生影响,不能回溯,常用于解决一维的问题;动态规划法根据以前的选择结果对当前进行选择,可以回溯,主要用于二维或三维问题[3]。
  2.贪心选择性质
  贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来得到,这是贪心法和动态规划法的主要区别。贪心策略采用自顶向下的方式,每做一次贪心选择就将问题简化为一个规模更小的子问题,这种选择依赖于已做出的选择,但不依赖于将来做出的选择。而动态规划算法采用自底向上的方式求解各个子问题。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。通常首先证明问题一个整体最优解,是从贪心选择开始的,在做出贪心选择后,原问题简化为规模更小的类似子问题。然后,用数学归纳法证明,通过每一步贪心选择,最终可得到问题的一个整体最优解。
  四、贪心算法的实现过程
  就像登山一样,贪心法求解问题的过程是逐步向前推进,从一个初始状态出发,根据当前的局部最优策略,以满足约束方程为条件,以使目标函数增长最快(最慢)为准则,在候选集合中进行一系列的选择,以便尽快构成问题的可行解[4]。当算法中的某一步不能再继续前进时,算法停止。贪心算法求解过程包括以下几个方面:
  1.候选集合C:作为问题的可能解,问题的最终解均取自候选集合。
  2.解集合S:随着贪心选择的进行,解集合S不断扩展,直到构成一个问题的完整解。
  3.选择函数select:贪心策略,这是贪心算法的关键,指出哪个候选对象最有希望构成问题的解。它的取值范围是候选集合。
  4.可行函数feasible:检查解集合中加入一个候选对象后是否可行。
  5.解决函数resolve:用于检查解集合S是否构成问题的完整解。
  候选集合C中包含所有问题的可能解,解集合S初值为空。然后根据选择函数select确定的贪心策略,从候选集合C中选择一个元素x,同时用可行函数feasible来判断解集合S加入x后是否可行。如果可行,把x加入到解集合S中,同时将它从候选集合C中删除;否则,丢弃x,从候选集合C中根据贪心策略再选择一个元素,重复上述操作,直到找到满足解决函数resolve的完整解。贪心算法描述如下:
  Greedy(C)
  {
  S={}; //解集合初值为空集
  while(not resolve (S)) //解集合S没有构成问题的完整解时
  {
  x=select(C); //在候选集合C中用贪心策略进行选择
  If feasible(S,x)//判断解集合S中加入x后是否可行
  S=S+x; //将x加入解集合S中
  C=C-x; //丢弃x
  }
  return S;
  }
  五、贪心算法的应用
  贪心算法可应用于日常生活中买卖东西经常遇到的找零问题。例如目前人民币的面值有100元、50元、20元、10元、5元、1元、5角、2角和1角,要求找出的人民币张数n最少,给出找R元钱的最佳方案。
  根据常识,找零时,在不超过应付金额的条件下,总是先找给顾客最大面值的货币,在金额不足的情况下,采取同样的方法考虑面值次大的人民币,以此类推,直到找满为止。
  根据上一节的内容进行分析,由已知条件可知:
  候选集合C:由各种面值的货币构成,初始时,C={100元,50元,20元,10元,5元,1元,5角,2角,1角};
  解集合S:由已找出的货币构成,初值为空;
  选择函数select:是该问题的贪心策略,即在候选集合中选择面值最大的货币;
  可行函数feasible:每一步选择的货币和已找零的货币相加不超过R元钱;
  解决函数resolve:已找出的货币金额等于应支付的货币金额R。
  找零问题的算法描述如下[5]:
  C={100元,50元,20元,10元,5元,1元,5角,2角,1角};
  Greedy(C)
  {
  S={};
  while(当前需找零的金额>0)
  {
  当前找零的张数=当前需找零的金额/当前剩下的最大货币面值;
  当前需找零的金额=当前需找零的金额-当前找零的张数*当前剩下的最大货币面值;
  for(int i=0;i<当前找零的张数;i++)
  S=S+当前剩下的最大货币面值;
  C=C-当前剩下的最大货币面值;
  }
  return S;
  }
  运用贪心算法求解找零问题,有时并不能得到问题的最优解,但至少是最优解的近似解。
  贪心算法还常用来解决其它一些实际问题,如哈夫曼编码、单源最短路径、最小生成树、背包问题、多机调度问题和马踏棋盘问题。
  六、结束语
  贪心算法没有固定的算法框架,贪心策略的选择是整个算法的关键。很多问题表面上看用贪心算法可以找到最优解,但实际却将最优解漏掉了。所以贪心策略即选择函数一定要精心确定,在使用之前,最好对策略的可行性进行数学证明。贪心法不是从整体上进行最优的选择,而是在当前状态下做出局部最优选择。贪心算法的优点是求解速度快,时间复杂性较低,其缺点是需证明要求解问题的解是最优解。贪心算法是很接近人的日常思维的一种解题思想,虽然不能保证求得的解一定是问题的最优解,但至少是最优解的近似解。
  [参考文献]
  [1]吕国英.算法设计与分析[M].清华大学出版社,2006:143-154.
  [2]徐保民,陈旭东,李春艳著.计算机算法与实践教程[M].清华大学出版社,2007:112-137.
  [3]肖衡.浅析贪心算法[J].办公自动化杂志,2009,164:25-26.
  [4]王红梅.算法设计与分析[M].清华大学出版社,2006:139-141.
  [5]常友渠,肖贵元,曾敏.贪心算法的探讨与研究[J].重庆电力高等专科学校学报,2008,3(13):40-47.
  (作者单位:空军雷达学院四系 武汉)

转载注明来源:https://www.xzbu.com/9/view-9285438.htm