目标

  1. 理解贪心算法的基本概念以及实现机制
  2. 掌握贪心算法设计的基本思想,理解贪心算法的基本设计原理
  3. 掌握使用贪心策略来解决背包问题、单源点最短路径问题以及最小成本生成树问题等各类问题
  4. 掌握如何分析使用贪心算法求解的最优化问题的时间复杂度与空间复杂度
  5. 如何运用数学归纳法证明求解此问题所使用的贪心算法得出的解就是最优解(难点)

学习指南

在我们设计算法解决一个实际问题之前,

  1. 必须首先分析这个实际问题具有哪些特质
  2. 然后依据这些特征选择相应的算法进行求解,往往会获得事半功倍的效果

针对每个可以使用贪心算法进行求解的问题

  1. 首先熟练掌握贪心策略的设计思路
  2. 将其转化为贪心算法
  3. 最后用数学归纳法证明按照贪心算法求出的贪心解就是这个最优解

注意:这个证明过程是必要的,如果不对贪心算法求解的过程进行证明,只能说明根据这个贪心策略设计的贪心算法得到的解仅仅只是贪心解,并不能说明是最优解!

贪心法证明最优解

  1. 按步骤归纳:例如活动选择问题
  2. 按规模归纳:例如装载问题
  3. 交换论证:例如最小延迟调度

基本概念

当有这样一类问题,有n个输入,而它的解就是由这n个输入的某个子集组成,只是这个子集必须满足某些实现给定的条件。

这些必须满足的条件称为约束条件

将满足这些约束条件的子集称为该问题的可行解

由于可行解不止一个,为了衡量可行解的优劣,通常会预先给定一些标准,一般以函数形式给出,称为目标函数

使得目标函数取得极值得可行解称为最优解

注意:根据约束条件与目标函数的数学模型的特性或求解问题方法的不同,可以细划分为如下类:

  1. 整数规划问题
  2. 线性规划问题
  3. 非线性规划问题
  4. 动态规划问题

尽管各类规划问题都有一些相应的求解方法,但是对于其中某些问题,我们仍然可以使用一种更为直接的方法进行求解,就是贪心算法

基本思想

贪心算法是一种改进了的分级处理方法

首先根据优化问题的要求,选取一种度量标准,然后按照这种量度标准对这n个输入进行排序,并且按照排好的顺序依次输入每一个量。如果这个输入与当前已经构成的在这种量度意义下的部分最优解组成在一起不可能产生一个可行解,那么我们就不把该输入纳入到这一部分最优解中,这种能够得到某种量度意义下的最优解分级处理方法叫做贪心算法。

注意:将目标函数作为量度标准产生的贪心解也并不一定就是原问题的最优解!

采用贪心算法设计求解原优化问题的最优解的核心问题就是选择能够产生优化问题最优解的最优量度标准,如果我们可以选择出最优量度标准,那么用贪心算法解决这个问题就会特别有效!

实现机制

贪心算法总是做出在当前看来是最好的选择(局部最优),也就是说贪心算法并不是从整体最优上加以考虑。当然,我们希望贪心算法求得的最终结果也是整体最优的!

设计思想

贪心算法通常用于解决具有最大值或者最小值的最优化问题

从某一个初始状态开始,依据当前局部的但却不一定是全局的最优策略,并且需要满足问题给出的约束条件,从而能够确保目标函数的值增加最快或者最慢,选择一个可以最快达到问题要求的输入元素,以便尽可能的构成问题的局部最优解!

1
2
3
4
5
6
7
8
9
10
11
greedy(S,n)
{
solution = Ø; //将初始可行解集设置为空集
for (i = 1; i < n; i++)
{
x = select(S);
if(feasible(solution, x))
solution = union(solution, x);
}
return solution;
}

​ 开始时,我们将初始可行解集设置为空集,然后采用select按照某种量度标准,从集合S中选择一个输入元素x,并且使用feasible进行判断,在可行解集中添加一个新元素x以后,是否可以组成新的可行解,如果可以,就把x加入到可行解集solution中,同时将其从原来的集合S中删去,如果不行,舍弃元素x,重新从原集合S中选择另一个元素y作为新的输入元素,重复前面的步骤,直到找出一个满足原优化问题的可行解为止!

在设计贪心算法时,其困难在于证明所设计的算法就是真正解决这个问题的最优算法!

适用于贪心法求解的问题具有的两个重要性质

  1. 贪心选择性质:待求解最优化问题的全局最优解,可以通过一连串的局部最优选择来实现
  2. 最优子结构性质:一个待求解的最优化问题的最优解中包含子问题的最优解