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

Presentation on theme: "计算机问题求解 – 论题3-2 - 贪心算法 2018年09月18日."— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

14 How to prove your greedy choice property?
替换法

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

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

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

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

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

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

21 Huffman Code

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

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

24

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

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

27

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

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

30 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.

31