《算法设计与分析-13贪心算法1》由会员分享，可在线阅读，更多相关《算法设计与分析-13贪心算法1（29页珍藏版）》请在金锄头文库上搜索。
1、第十三章 贪心算法 n贪心算法概念 n活动选择问题（过程及分析） n贪心算法正确性证明 n贪心算法的基本内容 贪心算法概念 顾名思义，贪心算法总是作出在当前看 来最好的选择。也就是说贪心算法并不 从整体最优考虑，它所作出的选择只是 在某种意义上的局部最优选择。当然， 希望贪心算法得到的最终结果也是整体 最优的。 活动安排问题 活动安排问题就是要在所给的活动集合 中选出最大的相容活动子集合，是可以 用贪心算法有效求解的很好例子。该问 题要求高效地安排一系列争用某一公共 资源的活动。贪心算法提供了一个简单 、漂亮的方法使得尽可能多地活动能兼 容地使用公共资源。 活动安排问题 设有n个活动的集合E=
2、1，2，n，其中每 个活动都要求使用同一资源，如演讲会场等， 而在同一时间内只有一个活动能使用这一资源 。每个活动i都有一个要求使用该资源的起始时 间si和一个结束时间fi，且si fi。如果选择了活 动i，则它在半开时间区间si,fi)内占用资源。若 区间si,fi)与区间 sj,fj）不相交，则称活动i与活 动j是相容的。也就是说，当sifj或sjfi时，活 动i与活动j相容。 活动安排问题 例：设待安排的11个活动的开始时间和 结束时间按照结束时间的非减序排列如 下： 活动安排问题 在此例中，子集a3,a9,a11由互相兼容地 活动组成。然而，它不是最大的子集， 子集a1,a4,a8,a
3、11更大。事实上， a1,a4,a8,a11是一个最大的相互兼容活动 子集；另外一个最大子集是a2,a4,a9,a11 。下面我们就来看是如何用算法得到最 大相互兼容活动子集的。 活动安排问题（动态规划） 用动态规划方法，首先找到问题的最优子结构 ，然后利用这一结构，根据子问题的最优解来 构造出原问题的一个最优解。首先定义如下的 集合： Sij=akS:fiskfksj Sij是S活动的子集。为了能表示完整的问题， 加入虚构活动a0与an+1，用惯例f0=0以及 sn+1=。于是，S=S0,n+1,i和j的范围为0i，j n+1。 活动安排问题 考虑某个非空子问题Sij，并假设Sij包含某 活
4、动ak，其中fiskfk sj。用活动ak生 成两个子问题：Sik和Skj，它们都是Sij的子 集。Sij的解是连同活动ak在内的Sik和Skj的 解的并集。因此，Sij解中的活动数等于Sik 解的大小加上Skj解的大小再加上1. 活动安排问题 下面来讨论最优子结构问题。假设现在已 知Sij的最优解Aij包含活动ak，则包含在Sij 最优解中的针对Sik的解Aik和针对Skj的解 Akj必定也是最优的。于是 Aij=AikakAkj 整个问题的一个最优解也是S0，n+1的一个 解。 活动安排问题 如何求出最优解？ 设ci,j为Sij中最大兼容子集中的活动数。如果 ak在Sij的最大兼容子集中被
5、使用，则子问题Sik 和Skj的最大兼容子集也被使用，有 ci,j=ci,k+ck,j+1 此递归式假设k值已知，然而我们并不知道。k 的取值有j-i-1种，它们是k=i+1,j-1。由于Sij的 最大子集一定使用了k值中的某一个，故检查 过所有的k值后，就可以找到最好的一个。因 此，ci,j的完整递归定义变为（板书） 活动安排问题 如何用贪心算法简化此问题呢？ 首先看一个定理 对任意非空子问题Sij，设am是Sij中具有最早结束时 间的活动：fm=minfk:akSij那么， 1）活动am在Sij的某最大兼容活动子集中被使用。 2）子问题Sim为空，所以选择am将使子问题Smj为 唯一可能非
6、空的子问题。 活动安排问题贪心算法正确性证明 证明2）：假设Sim非空，因此有某活动ak满足 fiskfksmfm。ak同时也在Sij中，且比am有 更早的结束时间，这与am的选择相矛盾。 证明1）：设Aij为Sij的最大兼容活动子集，ak为Aij 的第一个活动。如果ak=am，得到结论；如果 akam，构造子集Aij=Aji-ak am，可证明 得到Aij是包含am的Sij的最大兼容活动集合 活动安排问题 在动态规划方法中，最优解有两个子问 题；在求解子问题Sij时，最多有j-i-1种选 择。上述定理将两者的数量大大减少： 在最优解中只使用一个子问题（另一个 为空）；在解决子问题Sij时，只
7、需要考虑 一种选择：在Sij中有着最早结束时间的那 个活动。可以自顶向下解决每一个子问 题 活动安排问题 递归贪心算法 RECURSIVE-ACTIVITY0SELECTOR(s,f,i,n) 1mi+1 2While mn and smfi 3 do mm+1 4 if mn 5 then return amRECURSIVE-ACTIVITY0SELECTOR(s,f,m,n) 6 else return 活动安排问题 迭代贪心算法 GREEDY-ACTIVITY-SELECTOR(s,f) 1n lengths 2A a1 3i 1 4for m 2 to n 5 do if smfi
8、6 Then A Aam 7 i m 8return A 基本性质 对于一个具体的问题，怎么知道是否可 用贪心算法解此问题，以及能否得到问 题的最优解呢?这个问题很难给予肯定的 回答。 但是，从许多可以用贪心算法求解的问 题中看到这类问题一般具有2个重要的性 质：贪心选择性质和最优子结构性 质。 基本内容最优子结构性质 当一个问题的最优解包含其子问题的最 优解时，称此问题具有最优子结构性质 。问题的最优子结构性质是该问题可用 动态规划算法或贪心算法求解的关键特 征。 基本内容贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通 过一系列局部最优的选择，即贪心选择来达到。这是 贪心算法可
9、行的第一个基本要素，也是贪心算法与动 态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而 贪心算法则通常以自顶向下的方式进行，以迭代的方 式作出相继的贪心选择，每作一次贪心选择就将所求 问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质 ，必须证明每一步所作的贪心选择最终导致问题的整 体最优解。 基本性质 对于具有最优子结构的问题应该选用贪 心算法还是动态规划算法求解?是否能用 动态规划算法求解的问题也能用贪心算 法求解?下面研究1个经典的组合优化问题 ，并以此说明贪心算法与动态规划算法 的主要差别。 基本性质0-1背包 给定n种物品和一个背包。物
10、品i的重量是 Wi，其价值为Vi，背包的容量为C。应如 何选择装入背包的物品，使得装入背包 中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即 装入背包或不装入背包。不能将物品i装入背包多次，也不能只 装入部分的物品i。 基本性质部分背包 与0-1背包问题类似，所不同的是在选择 物品i装入背包时，可以选择物品i的一 部分，而不一定要全部装入背包， 1in。 这2类问题都具有最优子结构性质，极为 相似，但部分背包问题可以用贪心算法 求解，而0-1背包问题却不能用贪心算法 求解。 基本性质 部分背包问题：首先计算每种物品单位重 量的价值Vi/Wi，然后，依贪心选择策略 ，将
11、尽可能多的单位重量价值最高的物 品装入背包。若将这种物品全部装入背 包后，背包内的物品总重量未超过C，则 选择单位重量价值次高的物品并尽可能 多地装入背包。依此策略一直地进行下 去，直到背包装满为止。 基本性质 对于0-1背包问题，贪心选择之所以不能得到最 优解是因为在这种情况下，它无法保证最终能 将背包装满，部分闲置的背包空间使每公斤背 包空间的价值降低了。事实上，在考虑0-1背包 问题时，应比较选择该物品和不选择该物品所 导致的最终方案，然后再作出最好选择。由此 就导出许多互相重叠的子问题。这正是该问题 可用动态规划算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效 地解0
12、-1背包问题。 哈弗曼编码 哈夫曼编码是广泛地用于数据文件压缩的十分有效的 编码方法。其压缩率通常在20%90%之间。哈夫曼编 码算法用字符在文件中出现的频率表来建立一个用0， 1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字 符以较长的编码，可以大大缩短总码长。 哈弗曼编码 对每一个字符规定一个0,1串作为其代码，并要求 任一字符的代码都不是其他字符代码的前缀。这 种编码称为前缀码。编码的前缀性质可以使译码 方法非常简单。 表示最优前缀码的二叉树总是一棵完全二叉树，即 树中任一内结点都有2个儿子结点。 平均码长定义为： 使平均码长达到最小的前缀码编码方案称为给定
13、 编码字符集C的最优前缀码。 abcdef 频度4513121695 固定长代码字000001010011100101 变长代码字010110011111011100 哈弗曼编码 哈夫曼算法以自底向上的方式构造表示最优前缀码的 二叉树T。 算法以|C|个叶结点开始，执行|C|1次的“合并”运算 后产生最终所要求的树T。 在书上给出的算法huffmanTree中，编码字符集中每一 字符c的频率是f(c)。以f为键值的优先队列Q用在贪心 选择时有效地确定算法当前要合并的2棵具有最小频率 的树。一旦2棵具有最小频率的树合并后，产生一棵新 的树，其频率为合并的2棵树的频率之和，并将新树插 入优先队列Q
14、。经过n1次的合并后，优先队列中只 剩下一棵树，即所要求的树T。 哈弗曼编码 要证明哈夫曼算法的正确性，只要证明 最优前缀码问题具有贪心选择性质和最 优子结构性质。 哈弗曼编码 贪心选择性质设C为一字母表，其中每个字符 cC具有频度fc。设x和y为C中具有最低频度 的两个字符，则存在C的一种最优前缀编码， 其中x和y的编码长度相同但最后一位不同 最优子结构性质C，x，y如上。设C为字母表 移去x和y，再加上z后的字母表，其中 fz=fx+fy。设T为表示字母表C上最优前 缀编码的任意一棵树。那么将T中的叶子结点z 替换成具有x和y孩子的内部节点所得到的树T ，表示字母表C上的一个最优前缀编码。
