贪心算法浅析
摘要?/p>
本文讲述了贪心算法的基本思路及实现过程,
贪心算法的特点?/p>
存在的问题以及应用?
并通过贪心算法的特点举例列出了几个经典问题?/p>
通过对问题的探讨和研究,
对贪心算法有
了更加深入的了解?/p>
关键?/p>
?/p>
贪心算法;最优解?/p>
最优子结构
问题;删数问题;活动安排问题
贪心算法的基本思路及实现过?/p>
1
贪心的基本思想
用局部解构造全局解,
即从问题的某一个初始解逐步逼近给定的目标,
以尽
可能快地求得更好的解。当某个算法中的某一步不能再继续前进时,算法停止?/p>
贪心算法思想的本质就是分治,
或者说?/p>
分治是贪心的基础?/p>
每次都形成局部最
优解,换一种方法说,就是每次都处理出一个最好的方案?/p>
利用贪心策略解题,需要解决两个问题:
?/p>
1
)该题是否适合于用贪心策略求解?/p>
?/p>
2
)如何选择贪心标准,以得到问题的最?/p>
/
较优解?/p>
2
贪心算法的实现过?/p>
?/p>
1
)应用同一规则
F
,将原问题变为一个相似的、但规模更小的子问题?/p>
?/p>
2
)从问题的某一初始解出发:
While
(能朝给定目标前进一步)
求出可行解的一个解元素?/p>
?/p>
3
)由所有解元素组合成问题的一个可行解?/p>
贪心算法的特?/p>
贪心算法的最大特点就是快,通常是线性二次式,不需要多少额外的内存?/p>
一般二次方级的存储要浪费额外的空间,而且那些空间经常得不出正解。但是,
使用贪心算法时,
这些空间可以帮助算法更容易实现且更快执行?/p>
如果有正确贪
心性质存在,那么一定要采用。因为它容易编写,容易调试,速度极快,并且节
约空间。几乎可以说,此时它是所有算法中最好的。但是应该注意,贪心算法?/p>
两大难点?/p>