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

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