【贪心】贪心算法总结
发布时间
阅读量：
阅读量
贪心算法：
声明：此文档是由重庆八中郭茂老师制作
1、什么是贪心算法:
**贪心算法（又称贪婪算法，Greedy Algorithm）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。** 2、基本思路
(1) 划分求解的问题为若干个子问题。
(2) 每个子问题通过求解获得其局部最优解。
(3) 将各个子优化结果整合形成整体优化方案。
3、算法实现。
(1) 以问题的一个初始解为基础展开分析与探讨。
(2) 通过循环结构，在能够逐步接近求解目标时不断迭代优化，并依据局部最优策略获得一个阶段性解决方案，并相应地缩小问题规模。
(3) 整合所有阶段性解决方案，在全面分析后最终得出整体解决方案。
贪心方法的基本思想
贪心是一种解题策略和一种分析思路
使用贪心算法时需注意局部最优与全局最优之间的关系
采用贪心策略解决问题需要解决两个关键问题：
该问题是否适合采用贪心算法求解？
如何确定贪心标准以获得问题的最优化解答？
【引例】
在一个由N行M列组成的方格阵中（即为网格），每个单元格被赋予一个数值（称为权重）。规定每次移动只能向上或向右进行（即不可逆）。请确定一条从左下角至右上角的路径（可选路线），使其经过的所有单元格权重之和达到最大值。
若按贪心策略求解，所得路径为：1→3→4→6；
若按动态规划求解，所得路径为：1→2→10→6。
贪心法的特点
1. 贪心特性：在算法运行过程中每一步都采取看起来最有利的行动，在此过程中每一步的决策只受之前决策的影响而不会考虑未来的可能性。
2. 优化子结构：在解决问题的过程中每一次都能获得局部最佳结果，并且只有当这些局部结果能够整合成整体最佳解决方案时才能得到最终的整体优化效果。
然而并非所有具备优化子结构的问题都可以应用贪心方法来求解……需要用动态规划的方法来解决（例如0-1背包问题与部分背包问题）。
全部评论 (0)
还没有任何评论哟~