贪心算法

• 是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。 必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

适用情况

适用于局部最优策略能导致产生全局最优解的问题。

基本步骤

• 从某个初始解开始；
• 在迭代的过程中，根据局部最优策略，得到可行解的一部分解，缩小问题规模；
• 将所有解组合成问题的一个最终可行解。

算法优缺点

优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用。

缺点：不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。