4-贪心法.pptVIP

应用实例 最优前缀码问题—Huffman编码 哈夫曼提出了构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。 应用实例 最优前缀码问题—Huffman算法 应用实例 最优前缀码问题—Huffman算法的正确性 贪心选择性质 最优子结构性质 * 应用实例 1．证明具有最优子结构性质 定理1（最优子结构）： 设T是字母表C的哈夫曼树， ，f(c)是c在文件中出现的概率。设x，y是T中任意两个相邻叶结点，z是它们的父结点，则z作为概率为f(z)=f(x)+f(y)的字符，T1=T-{x,y}表示了字母表C1=C-{x,y}∪{z}的哈夫曼树。 * b z T1 c f(x)+f(y) f(b) f(c) 往证：z作为概率为f(z)=f(x)+f(y)的字符， T1=T-{x,y}表示了字母表C1=C-{x,y}∪{z}的哈夫曼树。 证: b y c T f(x) f(b) f(c) x f(y) * 往证：z作为概率为f(z)=f(x)+f(y)的字符， T1=T-{x,y}表示了字母表C1=C-{x,y}∪{z}的哈夫曼树。 b y c T3 f(x) f(b) f(c) x f(y) 因为z在C1中是一个字符，它必是T2中的叶子。把结点x，y加入T2，作为z的子结点，则得到C的一个前缀树T3。T3的代价为： 若T1不是C1的优化前缀编码树，则必存在T2，其叶子在C1中，使B(T2)B(T1)。 z b f(x)+f(y) c f(b) f(c) T2 = B(T2)+ f(x) +f(y) B(T) 与T是优化的(即HUFFMAN树)矛盾，故T1是优化的。 * 应用实例 2．证明具有贪心选择性 定理2（贪心选择性）: 设C是字母表， ,f(c)是c在文件中出现的频率。设x,y是C中具有最小概率的两个字符，则存在一个C的优化前缀树,在该优化前缀树中x,y具有最大深度，其编码长度相同，仅在最末一位不同。 证：设T是C的优化前缀树，且b,c是具有最大深度的两个字符。不失一般性，设f(b)f(c)，f(x)f(y). 因x与y是具有最低概率的字符,所以f(b)≥f(x),f(c)≥f(y). 从T构造T1，交换T的b和x; 从T1构造T2,交换T1的c和y; 往证，T2是最大前缀树。 b x y c T x b y c T1 x b c y T2 * * b x y c T x b y c T1 x b c y T2 应用实例 因为f(b)≥f(x)，dT (b)≥dT(x) （因为b的深度最大） 所以B(T)-B(T1)≥0，B(T)≥B(T1)。 * 同理可证，B(T1)≥B(T2)。于是B(T)≥B(T2)。 又由于T是优化的，所以B(T)≤B(T2)。 于是B(T)=B(T2). 所以T2是C的最优前缀编码树。在T2中，x,y具有相同长度编码，而且仅最后一位不同（且在该优化前缀树中具有最大深度）。 应用实例 3．哈夫曼算法是按定理2的Greedy选择性进行局部优化选择的. 因此哈夫曼算法是正确的，即HUFFMAN(C)产生C的一个最优前缀码。 应用实例 最小生成树问题 设G =(V,E)是无向连通带权图，即一个网络。E中每条边(u,v)的权为w[u][v]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。 网络的最小生成树在实际中有广泛应用。 例如，在设计通信网络时，用图的顶点表示城市，用边(u,v)的权w[u][v]表示建立城市u和城市v之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 问题：给定无向联通带权图G(V,E,W)，求W(T)最小的生成树 应用实例 最小生成树问题 最小生成树性质： 设G=(V,E,W)是连通带权图，U是V的真子集。如果(u,v)?E，且u?U，v?V-U，且在所有这样的边中，(u,v)的权w[u][v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST (Most Small Tree )性质。 证明： Prim算法和Kruskal算法是根据最小生成树性质应用贪心策略进行设计的典型算法。 应用实例 最小生成树问题—Prim算法 设G=(V,E,W)是连通带权图，V={1,2,