贪心算法(一)——概述

贪心法用于求解最优化问题，即求解某一问题的最优解。 既然能用贪心法求解的问题是一个最优化问题，那么我们首先来了解下最优化问题的几个基本概念。

最优化问题的几个基本概念

目标函数 解决一个最优化问题，首先要将问题抽象成一个数学函数，这也就是一个数学建模的过程，这个能够描述问题的函数就称为『目标函数』，这个函数的最大/小值就是我们要求的最优值。 约束条件 任何函数都有它的取值范围，所有取值范围的集合就称为『约束条件』。 可行解 满足所有约束条件的解称为『可行解』。 最优解 满足约束条件，并且使得目标函数最大/小的解称为『最优解』。

贪心法的求解思路

既然贪心法用于解决最优化问题，所以我们首先对问题进行数学建模，找出其中的：目标函数、约束条件。 最优化问题的结果需要用一个n元组来表示，如X=(x1,x2,x3,……,xn)。 贪心法的执行一共需要n步，每一步都会确定n元组中的一个元素，并保证每一步选取的值都是局部最优的。在经过n步之后，一共选取了n个值，每个值都是局部最优的，最终我们就可以认为这n个局部最优的值是整体最优的。

那么，在每一步中，究竟通过怎样的策略来选取一个当前局部最优解呢？这个选取策略就叫做『最优量度标准』（也叫做贪心准则）。 最优量度标准选择的好坏，直接影响最终的结果是不是整体最优。 而最优量度标准的选择往往是根据经验来确定的，也就是并不是所有的最优量度标准都能达到整体最优。所以你选取的那个最优量度标准能否导致整体最优，这是需要额外证明的。

贪心算法原型

SolutionType greedy(int[] a){

    // 一开始结果集为空
    SolutionType solution = {};
    // 进行n步选值
    for ( int i=0; i<n; i++ ) {
        // 选出当前局部最优解x
        x = select(a);
        // 判断x是否满足约束条件，若不满足则继续选
        while( !isFeasible(x) ){
            x = select(a);
        }
        // 将当前最优解添加至结果集中
        solution.add(x);
    }
}

何时使用贪心法

满足如下条件，可以使用贪心法：

1. 要求解的问题是一个最优化问题；
2. 这个问题的解可以用n元组表示；
3. 该问题满足最优子结构特性；
4. 可以找到最优量度标准，并可以证明该最优量度标准能导致一个整体最优解；

PS：并非对所有最优化问题都能找到最优量度标准，若找不到可以使用动态规划法。

贪心法的应用

一般背包问题 最佳合并模式 最小代价生成树 单元最短路径

总结

贪心法用于求解最优化问题。采用多步决策的方式求解，每一步根据最优量度标准求出结果集的一个分量，保证该分量为当前的局部最优解。那么当进行n步决策后，就求出结果集的所有分量。只要最优量度标准选的合理，最终的结果就是一个最优解。 当然，你选取的那个最优量度标准究竟能不能导致整体最优解，这是需要证明的。