Question

能采用贪心算法求最优解的问题,一般具备()性质?

Answer 1

贪心算法适用的问题必须满足两个属性： (1) 贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。 (2) 最优子结构：问题的整体最优解包含着它的子问题的最优解。

贪心算法，“贪心”二字顾名思义，因此其规律特征就是更加注重当前的状态，贪心法做出的选择是对于当前所处状态的最优选择，它的解决问题的视角是微观的“局部”，而不是从全局宏观的角度思考和看待问题，根据这样的性质。

要求贪心法解决的问题有“无后效性”——当前的决策不会影响到后续的决策，因为如果问题前后勾连紧密的话，会造成求解过程十分混乱。贪心算法常常用于组合优化问题，它的求解过程是多步判断的过程。如果一个待求解的问题具有以上的特征，很有可能可以使用贪心算法解决。

贪心算法设计的核心是——“贪心选择的标准”，结合《算法设计与分析》书中的“活动安排问题”，该问题有“最早开始时间”“持续时间最短”“结束时间最早”三种贪心选择的标准。

当选定了“贪心选择的标准”之后，要按照这个对已知的数据信息进行预处理，通常的预处理是“排序”。本题中就要按照结束时间从小到大的顺序进行排序。

将数据进行预处理（排序）之后，一次按顺序遍历，并根据条件进行选取，构建两个集合，其中一个集合用于装符合条件的元素，另一个集合用于装未进行判断的元素，这是一个分步完成的过程。（有这个特征的典型应用就是在《数据结构》课程中曾经学习的求解最小生成树使用的prim算法、kruskal算法，两者都是分步的将符合条件的边收纳进入一个集合，再从另一个集合中挑选出符合“贪心标准”的边放入最小生成树集合）。