算法导论复习（七）| 贪心算法

贪心算法是这样一种方法：分步骤实施，它在每一步仅作出当时看起来最佳的选择，即局部最优的选择，希望这样的选择能导致全局最优解。
考题

贪心算法原理

• 贪心算法通过做出一系列选择来求问题的最优解 —— 即贪心选择：在每个决策点，它做出在当时看来是最佳的选择。
• 贪心算法通常采用自顶向下的设计，做出一个选择，然后求解剩下的子问题。

贪心求解的一般步骤：
1）确定问题的最优子结构；
2）每次对其作出一次选择；
3）证明作出贪心选择后，原问题总是存在最优解，即安全；
4）证明作出贪心选择后，剩余的子问题满足：其最优解与贪心选择组合即可得到原问题的最优解。

贪心算法中贪心选择性质和最优子结构性是两个关键要素。
1）贪心选择性质
贪心选择性质：可以通过做出局部最优（贪心）选择来构造全局最优解。

如何证明每个步骤贪心选择能生成全局最优解？
通常先考查某个子问题的最优解，然后用贪心选择替换某个其它选择来修改此解，从而得到一个相似但更小的子问题。

2）最优子结构性
最优子结构性质是能否应用动态规划和贪心方法的关键要素。

证明最优子结构

归纳+反证法

活动选择问题

假定有一个n个活动的集合S={a1,a2,…,an}，这些活动都要求使用同一资源(如演讲会场)，而这个资源在某个时刻只能供一个活动使用。每个活动ai都有一个开始时间si和一个结束时间fi，且0≤si<fi<∞。
若两个活动ai和aj满足[si, fi）与区间[sj, fj）不重叠，则称它们是兼容的。

活动选择问题就是从活动集合中选出最大兼容活动的集合。

哈夫曼编码

编码树：用于表示字符二进制编码的二叉树。
叶子结点：对应给定的字符。
编码构造：由从根到字符叶子结点的简单路径：0代表“转向左孩子”，1代表“转向右孩子”。