基本概念

又名贪心算法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

  • 贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策略的选择，根据不同的问题选择不同的策略。

  • 必须注意的是策略的选择必须具备无后效性，即某个状态的选择不会影响到之前的状态，只与当前状态有关，所以对采用的贪婪的策略一定要仔细分析其是否满足无后效性。

    要素

  • 贪婪选择性质：全局最优解可以通过寻找局部最优解获得（贪婪），局部最优解的选择可能依赖于之前的决策，而不是后续的决策。通过迭代方式算法进行一一个个贪婪选择，将原问题简化为规模更小的问题。

  • 最优子结构：如果原问题的最优解包含子问题的最优解，则认位该问题具有最优子结构。这意味着可以对子问题求解并构建规模更大问题的解。

    基本思路

    1) 建立数学模型来描述问题。
    2) 把求解的问题分成若干个子问题。
    3) 对每一子问题求解，得到子问题的局部最优解。
    4) 把子问题的解局部最优解合成原来解问题的一个解。

    适用范围

    贪婪法适用的前提是：局部最优策略能导致产生全局最优解。
    实际上，其适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

    基本步骤

    贪婪法在每一层递归上都有三个步骤：
    step1 初始解：从某个初始解触发；
    step2 迭代求解：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模;
    step3 合并：将所有解综合起来。
    它的一般的算法设计模式如下：

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

    优缺点

  • 优点：直观、易于理解、易于编码实现，当前的决策不会对已经计算出的结果有任何影响，因此不需要再对已有的局部解进行检查。

  • 缺点：对于许多问题，无法用贪婪算法求解。即在许多情况下，无法保证局部最优解能够产生全局最优解。

    经典问题

    可使用贪婪法求解的一些经典问题：

  • 排序问题：选择排序、拓扑排序

  • 优先队列：堆排序
  • 赫夫曼编码压缩算法
  • Prim和Kruskal算法
  • 加权图的最短路径问题（Dijkstra算法）
  • 硬币找零问题
  • 活动选择算法
  • 背包问题
  • 并查集的按大小或高度合并问题（或排名）
  • 任务调度算法
  • 求解复杂问题的近似算法

    经典问题求解代码实现