贪心算法浅析

贪心算法浅析摘要：本文讲述了贪心算法的基本思路及实现过程，贪心算法的特点、存在的问题以及应用。并通过贪心算法的特点举例列出了几个经典问题，通过对问题的探讨和研究，对贪心算法有了更加深入的了解。关键词：贪心算法；最优解；最优子结构问题；删数问题；活动安排问题贪心算法的基本思路及实现过程1贪心的基本思想用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。利用贪心策略解题，需要解决两个问题：（1）该题是否适合于用贪心策略求解；（2）如何选择贪心标准，以得到问题的最优/较优解。2贪心算法的实现过程（1）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题；（2）从问题的某一初始解出发：While（能朝给定目标前进一步）求出可行解的一个解元素；（3）由所有解元素组合成问题的一个可行解。贪心算法的特点贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，此时它是所有算法中最好的。但是应该注意，贪心算法有两大难点：（1）如何贪心怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。正因为贪心有如此性质，它才能比其他算法快。具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪心算法取得（近似）最优解的。或者，总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性，如果面值发生变化，可能贪心算法就不能返回最优解了。但是，值得指出的是，当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。另外，我们经过实践发现，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。（2）贪心的正确性要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。对某些问题贪心性质也许是错的，即使它在大部分数据中都是可行的，但还必须考虑到所有可能出现的特殊情况，并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。贪心算法存在的问题（1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑；（2）贪心算法只能用来求某些最大或最小解的问题；（3）贪心算法只能确定某些问题的可行性范围贪心算法的应用1哈夫曼编码20-1背包问题3磁盘文件的存储4生产调度问题5信息查询贪心算法经典应用举例删数问题问题提出：给定n位正整数a，去掉其中任意k=n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。分析：n位数a可表示为x1x2…xixjxk…xn，要删去k位数，使得剩下的数字组成的整数最小。设本问题为T，其最优解A=(y1，y2…yk)表示依次删去的k个数，在删去k个数后剩下的数字按原次序排成的新数。即最优值记为TA。本问题采用贪心算法求解，采用最近下降点优先的贪心策略：即x1x2…xixj；如果xkxj，则删去xj，即得到一个新的数且这个数为n一1位中为最小的数Nl，可表示为x1x2…xixkxm…xn。对N1而言，即删去了1位数后，原问题T变成了需对n-1位数删去k-1个数新问题T’。新问题和原问题相同，只是问题规模由n减小为n-1，删去的数字个数由k减少为k-1。基于此种删除策略，对新问题T’，选择最近下降点的数进行删除，如此进行下去，直至删去k个数为止。证明：先来证明该问题具有贪心选择性质，即对问题T删除最近下降点的数xj后得到的N1是n一1位数是中最小的数。根据数的进制特点，对a按权展开得：a=x1*10n-1+x2*10n-2+…+xi*10n-i+xj*10n-j+xk*10n-k+…+xn则有：Nl=x1*10n-2+x2*10n-3+…+xi*10n-i-1+xk*10n-k+…+xn假设删去的不是xj而是其它位，则有N2=x1*10n-2+x2*10n-3+…+xi*10n-i-1+xj*10n-k+…+xn因为有x1x2…xixj且xjxk，则有NlN2。因此删数问题满足贪心选择性质。删数问题的C++代码：#includeiostream#includestringusingnamespacestd;intmain(){stringn;ints,i,x,l,m;printf(请输入一个正整数和将要删去的个数!\n);while(cinns){i=-1,m=0,x=0;l=n.length();while(xs&&m==0){i++;if(n[i]n[i+1])//出现递减,删除递减的首数字{n=n.erase(i,1);x++;//x统计删除数字的个数i=-1;//从头开始查递减区间}if(i==l-x-2&&xs)m=1;//已经无递减区间,m=1脱离循环}printf(最后结果为:\n);coutn.substr(0,l-s+x);//只打印剩下的左边l-(s-x)个数字}}问题的最优子结构性质在进行了贪心选择后，原问题T就变成了对N1如何删去k-1个数的问题T’，是原问题的子问题。若A=(xj，A’)是原问题T的最优解，则A’是子问题T’的最优解，其最优值为TA’。证明：假设A’不是子问题T’的最优解，其子问题的最优解为B’，其最优值记为TB’，则有TB’TA’。而根据TA的定义可知：TA=TA’+xj*1On-j，而TB’TA’，因此有TB’+xj*1On-jTA’+xj*1On-j=TA。即存在一个由数a删去1位数后得到的n-1位数比最优值TA更小。这与TA为问题T的最优值相矛盾。因此，A’是子问题T’的最优值。因此，删数问题满足最优子结构性质。从以上贪心选择及最优子结构性质的证明可知删数问题用贪心算法可以求得最优解。活动安排问题问题：设有n个活动的集合E={1,2,...,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间Fi，且SiFi。如果选择了活动i，则它在半开时间区间[Si,Fi)内占用资源。若区间[Si,Fi)与区间[Sj，Fj）不相交，则称活动i与活动j是相容的。也就是说Si=Fj或Sj=Fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选择出最大的相容活动子集合。证明：这个问题可以使用贪心算法进行求解。其实这个问题的关键并不是如何用贪心算法求解，而是如何证明这个问题可以用贪心算法求解。鉴于证明的复杂性，还是不在此讨论证明问题。其实贪心算法问题的证明无非都是用数学归纳法证明，不错就是那个传说中万能证明法，数学归纳法。还是直接讨论实现过程吧。实现：首先将活动按照活动的结束时间非递减：F1=F2=...=Fn排序。如果所给的活动未排序，则先将活动按此序排列，时间复杂度一般为O(nlogn)可解决。以下是解决问题的算法。1//贪心算法-活动安排的实现23#includestdafx.h4#includestdio.h56templateclassType7voidGreedySelector(intn,Types[],Typef[],boolA[])8{9A[0]=1;//第一个直接选取10intj=0;11for(inti=1;in;i++)12{13if(s[i]=f[j]){A[i]=true;j=i;}//如果第i+1的活动的开始时间大于或等于第i个活动的结束时间，则标记该活动14elseA[i]=false;15}16}1718int_tmain(intargc,_TCHAR*argv[])19{20//初始化数据21intn=3;22ints[3]={1,2,4};//开始时间23intf[3]={3,3,5};//结束时间24boolA[3]={0,0,0};//数组A用于标记是否选择活动，1表示选择，0表示不选择2526GreedySelectorint(n,s,f,A);27for(inti=0;in;i++)28{29printf(%d\n,A[i]);30}31}该算法的贪心选择的意义是使剩余的可安排的时间段极大化，以便安排尽可能多的相容活动。也就是说，每次选择完了之后，保证这次的选择之后留下的时间是最多的。时间复杂度：GreedySelector算法效率极高。当输入的数据是已经按照结束时间非递减排序好的时候，算法只需要O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。总结贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围。贪心算法所作的选择依赖于以往所作过的选择，但决不依赖于将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。对一个问题可以同时用几种方法解决，贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。与回溯法、动态规划法等比较，它的适用区域相对狭窄许多。总之，如果一个贪心解决方案存在，就可以使用它。参考文献[1]严蔚敏,吴伟民.数据结构(c语言版)[M].北京:清华大学出版社,1997．[2]M.H.ALSUWAIYEL.算法设计技巧与分析[M].北京:电子工业出版社,2004．[3]常友渠.贪心算法的探讨与研究[M].重庆电力高等专科学报,第13卷，第13期，2008.9.[4]龚雄兴,堆与贪心算法[M],湖北襄樊学院，2003.[5]张洁,朱莉娟.贪心算法与动态规划的比较[M].新乡师范高等专科科学学报,第19卷，第五期，2005.9.[6]殷建平.关于贪心算法的正确性证明[M].江西师范大学学报（自然科学版）,第22卷增刊,1998.10.