法设计与分析 第4章.pptVIP

?前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。 译码过程可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 * 4.4 哈夫曼编码 编码的前缀性质可以使译码方法非常简单。 表示最优前缀码的二叉树总是一棵正则二叉树，即树中任一结点都有2个儿子结点。 平均码长定义为： 使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。 * 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 平均码长达到最小 贪心策略体现：要使平均编码长度最短，那么直观上使频率最大的字符对应的编码方案最短。 4.4 哈夫曼编码 2、构造哈夫曼编码 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。 * * 定长编码树 变长编码树 其构造步骤如下： (1)假设编码字符集中每一字符c的频率是f(c)。 (2)以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。 (3)一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。 (4)经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。 * 若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 正则二叉树：只有度为0或者2的节点； 4.4 哈夫曼编码 时间复杂度： 算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn) 。 * 4.5 单源最短路径 给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 1、算法基本思想 Dijkstra（迪杰斯特拉）算法是解单源最短路径问题的贪心算法。 * * * 5 1 6 4 3 2 0 8 5 6 2 30 13 7 17 32 9 13 长度 最短路径 V0,V1 V0,V2 V0,V2,V3 V0,V2,V3,V4 V0,V2,V3,V4,V5 V0,V1,V6 8 13 19 21 20 从某个源点到其余各顶点的最短路径 注意：用户可能只需要找到从源点到某一特定终点的最短路径， 但是，该问题复杂度与求解到所有顶点的最短路径是一样的。 最优值：V0到V6，长度为20 最优解：V0，V1，V6 * * * STEP 1:初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值 若存在V0,Vi，距离值为V0,Vi弧上的权值 若不存在V0,Vi，为? STEP 2:从T中选取一个其距离值为最小的顶点W，加入S STEP 3:对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值 STEP 4:重复上述步骤，直到S中包含所有顶点. * 2、迪杰斯特拉(Dijkstra)算法思想 * * v1 v2 v6 v7 v3 v4 v5 2 4 2 1 3 10 2 5 8 4 6 1 0 v1 Dist Path ? v2 ? v3 ? v4 ? v5 ? v6 ? v7 0 0 0 0 0 0 0 2 v1 1 v1 3 v4 3 v4 9 v4 5 v4 8 v3 6 v7 4，算法描述 初始化： S ← { v1 }; dist[j] ← Edge[0][j], j = 1, 2, …, n-1; // n为图中顶点个数 求出最短路径的长度： dist[k] ← min{ dist[i] }, i ? V- S ; S ← S U { k }; 修改： dist[i] ←