程序设计技术第八章Greedy算法简介.pptVIP

* 程序设计技术 第八章 Greedy算法简介 * Greedy 算法的基本元素 Greedy算法的基本概念 Greedy选择性 优化子结构 Greedy算法正确性证明方法 * Greedy算法的基本思想 求解最优化问题的算法包含一系列步骤 每一步都有一组选择 作出在当前看来最好的选择 希望通过作出局部优化选择达到全局优化选择 Greedy算法不一定总产生优化解 Greedy算法是否产生优化解，需严格证明 Greedy算法产生优化解的条件 Greedy-choice-property Optimal substructure Greedy算法的基本概念 * Greedy选择性 Greedy选择性 若一个优化问题的全局优化解可以通过 局部优化选择得到，则该问题称为具有 Greedy选择性. 一个问题是否具有Greedy选择性需证明 * ? 若一个优化问题的优化解包含它的 子问题的优化解，则称其具有优化 子结构 优化子结构 * 证明算法所求解的问题具有优化子结构 证明算法所求解的问题具有Greedy选择性 证明算法确实按照Greedy选择性进行局部优化选择 Greedy算法正确性证明方法 * Huffman codes 问题的定义 优化解的结构分析 算法设计 算法复杂性分析 算法正确性证明 * 二进制字符编码 每个字符用一个二进制0、1串来表示. 固定长编码 每个字符都用相同长的0、1串表示. 可变长编码 经常出现的字符用短码，不经常出现的用长码 前缀编码 无任何字符的编码是另一个字符编码的前缀 问题的定义 * 编码树 叶结点: 用字符及其出现频率标记 内结点: 用其子树的叶结点的频率和标记 边标记: 左边标记0，右侧边标记1 100 a: 45 55 30 25 c: 12 b: 13 14 d: 16 e: 9 f: 5 0 0 0 0 0 1 1 1 1 1 * 编码树T的代价 设C是字母表,?c?C f(c)是c在文件中出现的频率 dT(c)是叶子c在树T中的深度，即c的编码长度 T的代价是编码一个文件的所有字符的代码位数: B(T)= * 优化编码树问题 输入: 字母表 C = {c1, c2, ...., cn }， 频率表 F = {f(c1), f(c2), ..., f(cn)} 输出: 具有最小B(T)的C前缀编码树 贪心思想： 循环地选择具有最低频率的两个结点， 生成一棵子树，直至形成树 * 我们需要证明 优化前缀树问题具有优化子结构 优化前缀树问题具有Greedy选择性 优化解的结构分析 * 优化子结构 引理1.设T是字母表C的优化前缀树，?c?C，f(c) 是c在文件中出现的频率.设x、y是T中任意 两个相邻叶结点，z是它们的父结点，则z作 为频率是f(z)=f(x)+f(y)的字符，T’=T-{x,y}是 字母表C’=C-{x,y} 的优化前缀编码树. b c z T’ 0 0 1 1 f(c) f(b) f(x)+f(y) b c x y T 0 0 0 1 1 1 f(x) f(c) f(y) f(b) z * 证. 要证B(T)=B(T’)+f(x)+f(y). ?v?C-{x,y}, dT(v)=dT’(v), f(v)dT(v)=f(v)dT’(v). 由于 dT(x)=dT(y)=dT’(z)+1, f(x)dT(x)+f(y)dT(y) =(f(x)+f(y))(dT’(z)+1) =(f(x)+f(y))dT’(z)+(f(x)+f(y)) 由于 f(x)+f(y)=f(z), f(x)dT(x)+f(y)dT(y)=f(z)dT’(z)+(f(x)+f(y)). 于是B(T)=B(T’)+f(x)+f(y). 若T’不是C’的优化前缀编码树， 则必存在T’’，使B(T’’)B(T’). 因为z是C’中字符，它必为T’’中的叶子. 把结点x与y加入T’’，作为z的子结点， 则得到C的一个如下前缀编码树T’’’： b c z T’ 0 0 1 1 f(c) f(b) f(x)+f(y) u v T’’ 0 0 1 1 f(v) f(u) z f(z) * T’’’代价为： B(T’’’)= ……+(f(x)+f(y))(dT’’(z)+1) = ……+f(z)dT’’(z)+(f(x)+f(y)) (dT’’(z)=