算法设计策略----贪心法

最优化问题：问题给出某些约束条件，满足这些约束条件的解称为可行解；为了衡量可行解的好坏，问题还给出了目标函数，使目标函数取最大（小）值的可行解称为最优解。

贪心法是求解最优化问题的一种设计策略。贪心法通过分步决策来求解问题。在对问题求解时，总是做出在当前这一步看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心法在每一步上用作决策依据的选择准则被称为最优量度标准或贪心准则，这种量度标准通常只考虑局部最优性。

贪心法基本要素：

最优度量标准：所谓贪心法的最优度量标准，是指可以根据该度量标准，实行多步决策进行求解，虽然在该度量标准下所做的这些选择都是局部最优的，但最终得到的解却是全局最优的。选择最优度量标准是使用贪心法求解问题的核心问题。贪心算法每步做出的选择可以依赖以前做出的选择，但绝不依赖将来的选择，也不依赖子问题的解。也正是如此，贪心法的特征是自顶向下，一步一步地做出贪心决策。

最优子结构：当一个问题的最优解中包含了自问题的最优解时，则称该问题具有最优子结构特性。一个可用贪心法求解的问题往往呈现最优子结构性质。

并不是所有具有最优子结构特性的问题，都可以有幸的找到最优量度标准，此时可以考虑采用动态规划法求解。

算法模板：

SolutionType Greedy(SType a[],int n){
    SolutionType solution = null;    //初始解向量不含任何分量
    for(int i = 0;i<n;i++){    //多步决策，每步选择一个分量
        SType x = Select(a);    //遵循最优度量标准选择一个分量
        if(Feasible(solution,x)    //判断新分量x加入后是否可行
            solution = Union(solution,x);    //形成新的最优解
    }
    return solution;    //返回生成的最优解
}

相关算法：

• 一般背包问题
• 霍夫曼树
• 最小代价生成树问题（Prim算法、Kruskal算法）
• Dijkstra算法