贪心算法(Greedy Algorithms)

1.贪心法的设计思想

         贪心算法在解决问题的策略上目光短浅， 只根据当前已有的信息就做出选择，而且 一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解，但不能总获得整体最优解，通常可以获得近似最优解。

该算法存在问题：

1). 不能保证求得的最后解是最佳的；
2). 不能用来求最大或最小解问题；
3). 只能求满足某些约束条件的可行解的范围。
Dijkstra算法、Prim算法和Kruskal算法都属于典型的贪心算法

引例 [找零钱]

一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目

引例分析

为使找回的零钱的硬币数最小，不考虑找零钱的所有各种方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，只当不足大面值币种的金额才会去考虑下一种较小面值的币种。这就是在采用贪婪法。这种方法在这里之所以总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1，5和11单位的硬币，而希望找回总额为15单位的硬币，按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。

贪心法的求解过程 

           用贪心法求解问题应该考虑如下几个方面：

（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种            面值的货币构成候选集合。

（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。

（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。

（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款             问题中，贪心策略就是在候选集合中选择面值最大的货币。

（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选              择的货币和已付出的货币相加不超过应付款。

贪心法的一般流程

Greedy(C)  //C是问题的输入集合即候选集合
{
    S={ };  //初始解集合为空集
    while (not solution(S))  //集合S没有构成问题的一个解
    {
       x=select(C);    //在候选集合C中做贪心选择
       if feasible(S, x)  //判断集合S中加入x后的解是否可行
          S=S+{x};
          C=C-{x};
    }
   return S;

2.贪心法的基本要素

      对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。

      但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质： 贪心选择性质和 最优子结构性质。

子问题：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，对于任何一个整数k，1 < k < n，以Dk作为问题的初始状态，来进行以后的决策，这样的问题就成为是原问题的一个子问题。

1) 贪心选择性质

      所谓 贪心选择性质是指所求问题的 整体最优解可以通过一系列 局部最优的选择，换句话说，当考虑做何种选择的时候， 我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。

贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

      对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2) 最优子结构性质

       当 一个问题的最优解包含其子问题的最优解时，称此问题具有 最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

3.贪心算法与动态规划算法的差异

      贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。大多数时候，能用贪心算法求解的问题，都可以用动态规划算法求解。但是能用动态规划求解的，不一定能用贪心算法进行求解。（因为贪心选择性质比动态规划的两个属性约束更强）

3.贪心算法的基本要素

• 哈夫曼编码
• 磁盘文件的存储
• 生产调度问题
• 信息查询
• 活动安排问题
• 0-1背包问题和背包问题（knapsack problem）

        1.活动安排问题

      设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。  

在下面所给出的解活动安排问题的贪心算法选择函数greedySelector :

int greedySelector(int s[MAXNUM] , int f[MAXNUM], bool a[])  //s数组记录着相应活动开始时间，f数组记录着相应活动结束时间
{                                                            //各个活动按结束时间的非减序排列 
      int n=MAXNUM-1;
      a[1]=true;                                             //安排第一个活动
      int j=1,count=1;

      for (int i=2;i<=n;i++)
      {
        if (s[i]>=f[j])                                      //检验当前最早结束的活动的开始时间是否晚于前一个活动的结束结束时间
        {                                                    //如果晚于，则表示两个活动相互兼容
            a[i]=true;                                       //标记为true，表示已经安排
            j=i;                                             //记已经安排活动的个数
            count++;
        }
        else 
            a[i]=false;                                      //与已安排活动不兼容，标记此活动未安排
      }
      return count;
}

 由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

      算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排（随机快排）。

例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：（必须先进行排序）

算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。

      若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。

      贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。

4.贪心法的适用范围

贪心算法并不能总求得问题的整体最优解。但对于某些问题，却总能求得整体最优解，这要看问题时什么了。只要能满足贪心算法的两个性质：贪心选择性质和最优子结构性质，贪心算法就可以出色地求出问题的整体最优解。即使某些问题，贪心算法不能求得整体的最优解，贪心算法也能求出大概的整体最优解。如果你的要求不是太高，贪心算法是一个很好的选择。最优子结构性质是比较容易看出来的，但是贪心选择性质就没那么容易了，这个时候需要证明。证明往往使用数学归纳法。

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2616926.html

http://blog.csdn.net/xywlpo/article/details/6439048