算法基础 chap4学习资料

1哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0、1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同。定长变码需要300,000位，而按表中变长编码方案，文件的总码长为224,000，总码长较少约25%。（111110101100）abcdef频率(千次)4513121695定长码000001010011100101变长码0101100111110111002前缀码前缀码对每一个字符规定一个0、1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。编码的前缀性质可以使译码方法非常简单。3前缀码平均码长（WPL：带权路径长度）给定编码字符集C及其频率分布f，C的一个前缀码编码方案对应于一棵二叉树T。字符c在T中的深度为dT(c)（前缀码长），则该方案的平均码长为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。4构造哈夫曼编码哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法从|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。5算法说明算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的两棵具有最小频率的树。一旦两棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的两棵树的频率之和，并将新树插入优先队列Q。经过n-1次的合并后，优先队列中只剩下一棵树，即所要求的树T。算法：P94—95。关于n个字符的哈夫曼算法的计算时间为O(nlogn)。67哈夫曼算法的正确性贪心选择性质C是编码字符集，字符c的频率为f(c)。x和y是C中具有最小频率的两个字符，则存在C的最优前缀码使x，y具有相同码长且仅最后一位编码不同。证明设二叉树T是C的任意一个最优前缀码，只需要证明对T作适当的修改后得到新的二叉树T"，使得新树中x，y是最深叶子且为兄弟，同时T"表示的前缀码也是C的一个最优前缀码。设b,c

是T中最深叶子且为兄弟，设f(b)

f(c),f(x)

f(y),则由于x和y是C中具有最小频率的两个字符，f(x)

f(b),f(y)

f(c)。8哈夫曼算法的正确性在T中交换b,x的位置得到T'，继续在T'交换c,y的位置得到T"。xycbTbycxT'bcyxT"9哈夫曼算法的正确性则树T、T'的前缀码的平均码长之差为：同样，可以证明B(T')－B(T")≥0。因此有：B(T")≤

B(T')≤

B(T)。又由于T所表示的前缀码是最优的，即B(T)≤B(T")，所以：B(T)=B(T")即T"表示的前缀码也是最优的，且x，y具有相同码长且仅最后一位编码不同。10哈夫曼算法的正确性最优子结构性质设T是表示C的一个最优前缀码的完全二叉树，C中字符c的频率为f(c)。设x,y是T中两个叶子结点且为兄弟，z为它们的父结点。若将z看作是具有频率f(x)+f(y)的字符，则树T'=T-{x,y}表示字符集C'=C-{x,y}∪{z}的一个最优前缀码。证明首先T的平均码长B(T)可用T'的平均码长B(T')表示。11哈夫曼算法的正确性12哈夫曼算法的正确性若T'表示的C'的前缀码不是最优的，则存在T"表示的C'的最优前缀码，Ｂ(T")<B(T')。z作为C'中的一个字符，故z作为T"中的一个叶子，若将x,y加入T"中，作为z的儿子结点，得到表示C的前缀码的二叉树Ｔ'"：与Ｔ最优矛盾，T'表示的C'的前缀码是最优的。贪心选择性质和最优子结构性质决定了哈夫曼算法的正确性。13单源最短路径问题描述给定带权有向图G=(V,E)，每条边的权是非负实数。给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。单源最短路径问题的贪心选择策略：选择从源v出发目前最短的路径所到达的顶点，这就是目前的局部最优解。14算法基本思想Dijkstra算法解单源最短路径问题的贪心算法。基本思想是设置顶点集合S并不断作贪心选择扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最小的最短特殊路径长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。15算法基本思想贪心选择每次找到最小的dist[u]，将u添加到S中，同时对数组dist[]作必要的修改。操作步骤由近到远逐步计算，每次最小的最短特殊路径长度就是对应顶点的最短路径长度。然后从这个最近者出发。即依据最近者修订到各顶点的距离，然后再选出新的最近者。如此走下去，直到所有顶点都走到。算法描述P97-981610205010030106012543一个实例对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径。Dijkstra算法的迭代过程迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10∞301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}51050306017算法的正确性和计算复杂性贪心选择性质Dijkstra算法中所做的贪心选择是：若u是V–S中具有最小最短特殊路径的顶点，就将u选入S，并确定了从源到u的最短路径长度dist[u]。即下一条最短路径是中间只经过S中顶点而最后到达u的最短路径。为什么从源到u没有更短的其它路径呢？若有，则这条路径一定经过V–S中的其它顶点：vuxSdist[u](最近距离)dist[x]dist[x]+d(x,u)＜dist[u]（条件假设）从而dist[x]＜dist[u]，与u的选取矛盾18算法的正确性和计算复杂性最优子结构性质算法中确定的dist[u]确实是当前从源到顶点u的最短特殊路径。因此，探讨添加u到S中后，以顶点i为参考，考虑dist[i]的变化。计算复杂性对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n2)时间。19最小生成树最小生成树设G=(V,E)是无向连通带权图，E中每条边(v,w)的权为c[v][w]。如果G的子图G'是一棵包含G的所有顶点的树，则称G'为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。最小生成树在实际中具有广泛的应用。城市间通信网络铺设20树的基本性质相关性质连通无回路的图G称为树。树是点比边多一的连通图，G连通。树是点比边多一的无回路图，G无回路。树若添条边就有回路：G无回路，但对任意的u,v∈V，若(u,v)

E，则G+(u,v)中恰有一条回路。树若减条边就不连通：G连通，但对

e∈E,G–e不连通。n个顶点的连通图的生成树含有n–1条边。21最小生成树性质MST性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这两个算法做贪心选择的方式不同，它们都利用了最小生成树性质。设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)∈E，且u∈U，v∈V-U，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。22最小生成树性质一定只有一条边连接左右两部分Why？23构造最小生成树要保证n–1条边构成树，必须使这n–1条边是连通无回路的。Prim算法：在保证连通的前提下依次选出权重较小的n–1条边（实现中体现为n个顶点的选择）。Kruskal算法：在保证无回路的前提下依次选择权重较小的n–1条边。24Prim算法基本思想在保证连通的前提下，依次选出权重较小的n–1条边。G=(V,E)为无向连通带权图，令V={1,2,…,n}。设置一个集合S，初始化S={1}，T=Φ。贪心策略：如果V–S中的顶点j与S中的某个点i连接且(i,j)是E中的权重最小的边，于是就选择j(将j加入S)，并将(i,j)加入T中。重复执行贪心策略，直至V–S为空。时间复杂度为O(n2)

25Prim算法一个实例给定一个连通带权图如下：1234561655536624初始时S={1}，T=Φ；1第一次选择：∵(1,3)权最小∴S={1,3}T={(1,3)}

；3第二次选择：∵(3,6)权最小∴S={1,3,6}，

T={(1,3),(3,6)}

；6第三次选择：∵(6,4)权最小∴S={1,3,6,4}，

T={(1,3),(3,6),(6,4)}

；4第四次选择：∵(2,3)权最小∴S={1,3,6,4,2}，

T={(1,3),(3,6),(6,4),(2,3)}

；2第五次选择：∵(5,2)权最小∴S={1,3,6,4,2,5}，

T={(1,3),(3,6),(6,4),(3,2)(2,5)}

；526Kruskal算法基本思想在保证无回路的前提下依次选择权重较小的n–1条边。贪心策略如果(i,j)是E中尚未被选中的边中权重最小的，并且(i,j)不会与已经选择的边构成回路，于是就选择(i,j)。如何知道(i,j)不会造成回路？若边(i,j)的两个端点i和j属于同一个连通分支，则选择(i,j)会造成回路，反之则不会造成回路。因此，初始时将图的n个顶点看成n个孤立分支。27Kruskal算法算法执行首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就