贪心算法浅析

贪心算法浅析

ID:44872689

大小:24.79 KB

页数:7页

时间:2019-11-01

贪心算法浅析_第1页
贪心算法浅析_第2页
贪心算法浅析_第3页
贪心算法浅析_第4页
贪心算法浅析_第5页
资源描述:

《贪心算法浅析》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、贪心算法浅析摘要:本文讲述了贪心算法的基本思路及实现过程,贪心算法的特点、存在的问题以及应用。并通过贪心算法的特点举例列出了几个经典问题,通过对问题的探讨和研究,对贪心算法有了更加深入的了解。关键词:贪心算法;最优解;最优子结构问题;删数问题;活动安排问题贪心算法的基本思路及实现过程1贪心的基本思想用局部解构造全局解,即从问题的某一个初始解逐步逼近给定的目标,以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时,算法停止。贪心算法思想的本质就是分治,或者说:分治是贪心的基础。每次都形成局部最优解,换一种方法说,就是每次都处理出一个最好的方案。利用贪心策略

2、解题,需要解决两个问题:(1)该题是否适合于用贪心策略求解;(2)如何选择贪心标准,以得到问题的最优/较优解。2贪心算法的实现过程(1)应用同一规则F,将原问题变为一个相似的、但规模更小的子问题;(2)从问题的某一初始解出发:While(能朝给定目标前进一步) 求出可行解的一个解元素;(3)由所有解元素组合成问题的一个可行解。贪心算法的特点贪心算法的最大特点就是快,通常是线性二次式,不需要多少额外的内存。一般二次方级的存储要浪费额外的空间,而且那些空间经常得不出正解。但是,使用贪心算法时,这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在,那么一定要

3、采用。因为它容易编写,容易调试,速度极快,并且节约空间。几乎可以说,此时它是所有算法中最好的。但是应该注意,贪心算法有两大难点:(1)如何贪心怎样用一个小规模的解构造更大规模的解呢?总体上,这与问题本身有关。但是大部分都是有规律的。正因为贪心有如此性质,它才能比其他算法快。具有应当采用贪心算法的问题,当“贪心序列”中的每项互异且当问题没有重叠性时,看起来总能通过贪心算法取得(近似)最优解的。或者,总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性,如果面值发生变化,可能贪心算法就不能返回最优解了。但

4、是,值得指出的是,当一个问题具有多个最优解时,贪心算法并不能求出所有最优解。另外,我们经过实践发现,单纯的贪心算法是顺序处理问题的;而且每个结果是可以在处理完一个数据后即时输出的。(2)贪心的正确性要证明贪心性质的正确性,才是贪心算法的真正挑战,因为并不是每次局部最优解都会与整体最优解之间有联系,往往靠贪心算法生成的解不是最优解。这样,贪心性质的证明就成了贪心算法正确的关键。对某些问题贪心性质也许是错的,即使它在大部分数据中都是可行的,但还必须考虑到所有可能出现的特殊情况,并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔,

5、因为贪心算法的适用范围并不大,而且有一部分极难证明,若是没有把握,最好不要冒险,还有其他算法会比它要保险。贪心算法存在的问题(1)不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择,因此并不从整体上加以考虑;(2)贪心算法只能用来求某些最大或最小解的问题;(3)贪心算法只能确定某些问题的可行性范围贪心算法的应用1哈夫曼编码20-1背包问题3磁盘文件的存储4生产调度问题5信息查询贪心算法经典应用举例删数问题问题提出:给定n位正整数a,去掉其中任意k<=n个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k,设计一

6、个算法找出剩下数字组成的新数最小的删数方案。分析:n位数a可表示为x1x2…xixjxk…xn,要删去k位数,使得剩下的数字组成的整数最小。设本问题为T,其最优解A=(y1,y2…yk)表示依次删去的k个数,在删去k个数后剩下的数字按原次序排成的新数。即最优值记为TA。本问题采用贪心算法求解,采用最近下降点优先的贪心策略:即x1

7、相同,只是问题规模由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+x

8、2*10n

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。