计算机问题求解 – 论题3-2 - 贪心算法 2018年09月18日

问题1: 你还记得什么是“Optimal Substructure”吗? 该结构特 性对求解最优解问题有什么启 发？ 最优子结构性质：最优解包含的子问题的解也一定是最优的； 最优子结构性质，能够保证我们这么一点：最优解必定是某些子问题的最优解的组合，因此，找出所有子问题的最优解，一定能够得到最优解。

Activity Selection Problem 贪心：无需求出所有子问题的最优解。 一个样本输入：

问题2： Activity Selection问题是否具 有“最优子结构”，为什么？ 具象思考：任取一种最优解，假设包含活动ak，那么a1到ak的子问题以及ak+1到an的子问题的解，一定是最优的； 再抽象思考（可以借鉴矩阵连乘）：将问题归结为求ai到aj的最优解，可以得到下一页的递归公式

Sij表示开始时间不早于活动ai的结束时间，而结束时间早于aj的结束时间的所有活动的集合。 假设我们知道其中包含活动ak。 Sij中最多相互兼容的活动数

问题3： 是否有可能不必解所 有的子问题？ 动态规划解法 在上述递归关系中，ak可以是Sij中任一活动，每选定一个特定的ak, 则确定特定的子问题。动态规划方法按照合适的次序解所有的子问题。 问题3： 是否有可能不必解所 有的子问题？ 如果我们每次都能很确定地定位那个最优解中必定存在的ak，则问题就简单很多了 比如：当前格局下，最早完成的活动，必定出现在最优解中。 但是特别要注意：这不是最优子结构性质带来的必然，因此我们必须要证明：在某种子问题分解方案中，我们的每一步选择都是最优解的选择（贪心特性）

问题4: 所谓“Greedy”是指什 么？ 本质上说就是：每次确定一个子问题的解，并确保它必定是最优解的一部分。 多数时候表现为在一个线性多阶段决策中，选择当前最优解并能够确保是最终的最优解的一部分。

Activity Selection: the Idea 要解的问题用 表示，S是原始问题所给的所有活动的集合，则原始问题为S0; Greedy方法： 选择完成时间最早的活动，假设是a1; 解子问题S1。 Greedy可以指不同的“最”，但有的“最”可以得到正确的解，有的“最”却未必！ 特别关注，通常我们的多阶段选择会将C[I,j]简化为Sk

如何去“编程表达”这样的递归式？ 解子问题S1

问题5： 为什么不需 要递归？ 为什么无条件地把a1放到最优解中？ 输入活动可以按照结束时间单调递增排序； 问题6： 为什么代价是线性的？

问题7： 仅仅具有“最优子结构” 能保证贪心算法的正确吗？ 还需要什么条件？ 两个子问题中：一个子问题的规模为1（广义上的1），剩余问题空间为另一个子问题。 需要证明：贪心选择的安全性；贪心选择+剩余子问题最优解=完整问题最优解。两个需要可以合并到后者中去证明

问题8： 你能设想一个证明这个特性的基本方法吗？ 贪心选择特性： 替换法证明。证明当前的最优选择Ck，必定存在于Sk子问题的某个最优方案中（贪心选择的策略不变）。 如果证明了这一点，我们可以结合最优子结构性质得到结论：

贪心算法解活动选择问题的正确性

How to prove your greedy choice property? 替换法

问题9： 为什么这个定理保证我 们需要的正确性？ Sk定义下的子问题划分方法，形成了一个最优子结构性质； 数学归纳法 最优子结构

Greedy vs. Dynamic Programming 能用贪心算法你不用，你就“亏”了； 不能用贪心算法你用了，你就错了！ 0-1背包问题和fraction背包问题均有最优子结构性质：任意将某个装包方案分为两阶段，两个独立阶段的装包方案均是最优的。 0-1背包问题不具备“依据单价最高原则优先选择”的贪心选择特性：反例 Fraction背包问题具备“依据单价最高原则优先选择”的贪心选择特性：任意找到某个最优解方案，采用替换方法证明这种贪心选择一定在该最优方案中 问题10： 你觉得为什么fractional knapsack 行，0-1就不行？

Review the idea of Activity Selection 要解的问题用 表示，S是原始问题所给的所有活动的集合，则原始问题为S0; Greedy方法： 选择完成时间最早的活动，假设是a1; 解子问题S1。 Greedy可以指不同的“最”，但有的“最”可以得到正确的解，有的“最”却未必！ 问题：一个问题能否采用贪心方法，依赖于“如何贪心”吗？

问题11： 字母编码，用固定长度与 可变长度，各有什么利弊？

0.0.101.1101 前缀码可以发挥可变长编码的优点，又可以避免使用界限符。 界限符： 前缀码：没有任何码字是其它码字的前缀。解码没有歧义。

哈夫曼编码： 使得B(T)最小的dT(c)如何构造？ 给定一段位串001011101，如何解码？

Huffman Code

Q 是一个最小优先队列。 下划线部分，在后期证明贪心时用到 两次extract和一次Insert之后，我们面临了一个“新”的子问题。

问题12： 最优前缀码问题满足 greedy-choice property， 这一点该如何表述？ 当前选择+子问题的最优解=原问题的最优解 最不频繁使用的，最长码长；树中高度最高，最先合并。 替换法

Xy是频率最低的两个字母； T是某种最优编码，但xy不是最深的兄弟，ab是最深的； 构造一棵新树（编码）T’’，新树代价更小 E .

问题13: 最优前缀码问题满足 optimal-substructure property，这点该如何 表述？ 最优子结构：最优解包含相关子问题的最优解，且子问题独立求解。 一个问题的最优解，包含了某种分解方向下的子问题的最优解，该问题具有最优子结构性质（在该分解方案下）。 继而，一旦存在这种方案，则问题本身具有最优子结构特性。

注意： 给定一个C，求其最优前缀码： 给定某种编码方式产生的最优解：一定可以表现成一颗满二叉树，总是存在第一个选择：哪两个是最底层的叶节点 首选(最不频繁使用的)两个字母：choice 子问题：zxy和C‘’ C‘’最优； 如果T是一个最优解，T‘和{z,x,y}也一定是最优解。 即：

T’’’和T’都是C‘的最优编码树。’

Open Topics： 1，Ternary Huffman. Trimedia Disks Inc. has developed .ternary. hard disks. Each cell on a disk can now store values 0, 1, or 2 (instead of just 0 or 1). To take advantage of this new technology, provide a modified Huffman algorithm for compressing sequences of characters from an alphabet of size n, where the characters occur with known frequencies f1; f2; : : : ; fn. Your algorithm should encode each character with a variable-length codeword over the values 0; 1; 2 such that no codeword is a prifex of another codeword and so as to obtain the maximum possible compression. Prove that your algorithm is correct.