贪心算法 --- 算法思想介绍

一.贪心算法的基本概念

贪心算法也称为优先策略
顾名思义是“择优录取”，在某些方面的应用是非常成功的，也是我们设计算法时经常使用的一种策略。国外叫做Greedy method，意即见到好的就抓住不放。它并不一定对所有问题都成功，但是对某些问题特别简单、有效。
在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则( criterion)。

顾名思义,贪心算法只是做出在当前看来是最好的选择,也就是说,贪心算法并不从整体最优上加以考虑,所做的选择只是在某种意义上的局部最优选择.当然,我们希望贪心算法得到的最终结果也是整体最优的.这对于大部分问题来说是可行的.

二.贪心算法的适用条件

贪心法在作每一次选择时，都是当前状态下的最好选择，希望以此得到整个问题的最优解。能否奏效？
用贪心法求解的问题应具备两个特性：

• （1）贪心选择性质
  贪心选择性质是指,所求问的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到.这是贪心算法剋性的第一个基本要素,也是贪心算法与动态规划算法的主要区别.在动态规划算法中,每部所做的选择往往依赖于相关子问题的解.因而只有在解出相应的子问题后,才能做出选择.而在贪心算法中,仅在当前状态下做出最好选择,即局部最优.再去解做出这个选择后产生的相应的子问题.贪心算法所做的贪心选择可以依赖以往所做的选择,但决不依赖将来所作的选择,也不依赖子问题的解.正是由于这种差别,动态通常以自底向上的方式解各子问题,贪心算法则通常以自顶向下的方式进行.以迭代的方式做出相继的贪心选择,每做一次贪心选择,就将所求问题简化成规模更下的子问题.
• (2) 最优子结构性质
  当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质.最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征.

贪心算法常常用于求解某些问题得最优解。

这类问题一般有n个输入，而其解由这n个输入的某个子集组成，要求该子集满足预先给定的约束条件。这一子集称为该问题的一个可行解。其中使目标函数取得极值的可行解称为最优解。

N个输入 ---> 约束条件 ---> 可行解 ---> 贪婪准则 ---> 最优解

贪心法的关键是找到一个衡量优劣的标准，然后把n个输入按这种标准排序并尝试局部解。如果这个输入和当前的部分解加起来不能产生一个可行解，则不把此输入加入到部分解当中.

一般地，选取最优度量标准并非易事，因此贪心法得到的解往往不是最优解，而是次优解。而一旦找到最优度量标准，则贪心法特别有效。
贪心法逐步给出解的各部分，在每一步“贪婪地”选择最好的部分解，而不顾及这样选择对整体的影响，因此未必得到最优解。
贪心法应用的成功示例有：单源最短路径问题、最小生成树问题以及作业调度等。即使得不到最优解，往往能得到较好的近似解。

三.贪心算法和动态规划算法的区别

贪心法：当前状态下，局部最优选择，然后求解作出此选择之后的子问题。贪心选择依赖于以往作出的选择，但不受将来所作的选择，既不依赖于子问题的解。

动态规划法：每步所作的选择依赖于相关子问题的解，只有在解出相关子问题以后，才能作出选择。

能用贪心解决的问题，也可以用动态规划解决

如何证明一个问题具有贪心选择性质？ 思路：证明每步贪心选择à问题的整体最优解

参考毕方明老师《算法设计与分析》课件.

欢迎大家访问个人博客网站---乔治的编程小屋,和我一起努力ba!