贪心算法

详讲贪心算法，总是作出在当前看来最好的选择。不从整体最优考虑，它作出的选择只是在某种意义上的局部最优选择。

贪心算法

• 概述
  • 总是作出在当前看来最好的选择。 不从整体最优考虑，它作出的选择只是在某种意义上的局部最优选择。 即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
  • 问题特征：对于一个具体的问题，如何知道是否可用贪心策略求解，以及能否得到问题的最优解呢？一般说来，如果一个问题具有贪心选择性质和最优子结构性质，那么我们就可以使用贪心策略得到该问题的最优解。
• 贪心算法性质
  • 贪心选择性质
    • 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
    • 证明思路
      • 首先，考察问题的一个整体最优解，并试图证明如果这个最优解，以贪心选择开始，作了贪心选择后，原问题可以简化为一个规模更小的、与原问题类似的子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到原问题的一个整体最优解。其中，证明贪心选择后的问题可以简化为规模更小的、与原问题类似的子问题的关键在于利用该问题的最优子结构性质。
  • 最优子结构性质
    • 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。（必要条件）
    • 证明思路（反证法）：设规模为n的问题S有最优解E，A是之前一步已经得到的局部最优解，假设E-{A}不是S-{A}规模中最优的解：即存在E'是S-{A}规模中最优的解，且E'≠E-{A}，从而E'∪{A}是S的最优解，显然E'∪{A}≠E，与假设E是原问题S的最优解矛盾。所以如果E是S的最优解，则E-{A}也是S-{A}的最优解，即原问题的最优解包含了子问题的最优解。
  • 典例：活动安排问题，最优装载，哈弗曼编码，单源最短路径，最小生成树，多机调度问题，取数问题，数列极差问题，币种统计问题（找零问题），背包问题，旅行售货员问题