计算机算法分析与设计 第4章.ppt

《计算机算法分析与设计 第4章.ppt》由会员分享，可在线阅读，更多相关《计算机算法分析与设计 第4章.ppt（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章 贪心算法1学习要点学习要点理解贪心算法的概念。掌握贪心算法的基本要素（1）最优子结构性质（2）贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论通过应用范例学习贪心设计策略。（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最小生成树；（6）多机调度问题。2一个找硬币的例子假设有四种硬币：二角五分、一角、五分和一分。现要找给顾客六角三分。显然，会拿出2个二角五分、1个一角和3个一分的硬币交给顾客。贪心方法思路：首先选出一个面值不超过六角三分的最大硬币，即二角五分，然后在剩余数中再选最大面值的硬币，依此类推，得到其解。3 若硬币面值改为：

2、一角一分、五分和一分，而要找给顾客一角五分钱。用贪心算法将找给1个一角一分和4个一分的硬币。然而，3个五分硬币是最好的找法。此时，贪心算法没有得到整体最优解。但通常可得到最优解的很好近似。4p贪心算法总是作出在当前看来最好的选择。p贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优局部最优选择。p希望贪心算法得到的最终结果也是整体最优的。p虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。p在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。5贪心算法的一般框架贪心算法的一般框架GreedyAlgorithm(paramet

3、ers)初始化；初始化；重复执行以下的操作重复执行以下的操作：选择当前可以选择的最优解；选择当前可以选择的最优解；将所选择的当前解加入到问题的解中去；将所选择的当前解加入到问题的解中去；直至满足问题求解的结束条件直至满足问题求解的结束条件。64.1 活动安排问题p活动安排问题:在所给的活动集合中选出最大的相容活动子集合。p该问题要求高效地安排一系列争用某一公共资源的活动。p贪心算法使得尽可能多的活动能兼容地使用公共资源。7设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个

4、结束时间fi,且si fi。如果选择了活动i，则它在si,fi)内占用资源。若si,fi)与sj,fj)不相交，则称活动i与j是相容的。即当sifj或sjfi时，活动i与活动j相容。活动安排问题就是求活动安排问题就是求E E的最大相容活动子集的最大相容活动子集。8活动安排问题的描述活动安排问题的描述用用数组数组A分别存放所有活动的起始时间、结束时分别存放所有活动的起始时间、结束时间以及是否予以安排的标记间以及是否予以安排的标记。某项活动结束时间愈早，安排其它活动的剩余区某项活动结束时间愈早，安排其它活动的剩余区间愈大。间愈大。贪心策略为尽量选择结束时间早的活动来安排贪心策略为尽量选择结束时间早

5、的活动来安排。为此，将数组中的活动按结束时间的为此，将数组中的活动按结束时间的非减非减顺序排顺序排序，即序，即f1f2fn。显然排序需要的时间为显然排序需要的时间为O(nlogn)。9templatevoid GreedySelector(int n,Type s,Type f,bool A)A1=true;int j=1;for(int i=2;i=fj)Ai=true;j=i;else Ai=false;下面给出解活动安排问题的贪心算法GreedySelectorGreedySelector:各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f f中且按结束

6、时间的非减中且按结束时间的非减序排列序排列 10u由于输入的活动以其完成时间的非减序非减序排列，所以算法greedySelector每次总是选择具有最具有最早完成时间早完成时间的相容活动加入集合A中。u算法贪心选择的意义是使剩余的可安排时间使剩余的可安排时间段极大化段极大化，以便安排尽可能多的相容活动。u当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。u如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。11 例例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011Si130

7、535688212fi4567891011121314124.1 活动安排问题 算法算法greedySelectorgreedySelector 的的计算过程计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。时间时间 13l若被检查的活动i的开始时间si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。l贪心算法并不总能求得问题的整体最优解整体最优解。但对于活动安排问题，greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用

8、数学归纳法证明。14贪心算法也能获得最优解贪心算法也能获得最优解n设活动集合设活动集合E=1,2,n已经按结束时间的非减已经按结束时间的非减顺序排列，活动顺序排列，活动1具有最早结束时间。具有最早结束时间。n首先，必定有一个最优解包含活动首先，必定有一个最优解包含活动1。不然设不然设A E是最优解且是最优解且A中最早结束的活动中最早结束的活动是是k。若。若k=1，则最优解包含活动，则最优解包含活动1。若。若k1，则活动，则活动1必与必与A中除中除k以外的活动相容。令以外的活动相容。令B=（Ak）1，则，则B也是一个最优解。也是一个最优解。n其次，若其次，若A是原问题的包含活动是原问题的包含活动

9、1的最优解，则的最优解，则A=A1是活动集合是活动集合E=iE：sif1的一的一个最优解。个最优解。不然设不然设B 是是E 的解且的解且|B|A|，则，则B 1是是E的解且的解且|B|+1|A|。此与。此与A是是最优解矛盾。最优解矛盾。n对贪心选择次数用数学归纳法即知，贪心算法对贪心选择次数用数学归纳法即知，贪心算法最终产生原问题的最优解。最终产生原问题的最优解。154.2 贪心算法的基本要素考察用贪心算法求解的问题的一般特征 对于一个具体问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。从许多用贪心算法求解的问题中看到，这类问题一般具有2个重要性

10、质：贪心选择性贪心选择性质质和最优子结构性质最优子结构性质。164.2.14.2.1、贪心选择性质、贪心选择性质l贪心选择性质贪心选择性质是指所求问题的整体最优解整体最优解可以通过一系列局部最优局部最优的选择（即贪心选择）来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。l动态规划算法通常以自底向上自底向上的方式解各子问题l贪心算法则通常以自顶向下自顶向下的方式进行，以迭代方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。l对具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。17p当一个问题的最

11、优解包含其子问题的最优解时，称此问题具有最优子结构性质最优子结构性质。p问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。4.2.24.2.2、最优子结构性质、最优子结构性质18共同点：贪心算法和动态规划算法都要求问题具有最优子结构性质。具有最优子结构最优子结构的问题应该选用贪心算法，还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。4.2.3、贪心算法与动态规划算法的差异194.2.3、贪心算法与动态规划算法的差异0-1背包问题背包问题：给定n种物品和一个背包。物

12、品i的重量是wi，其价值为vi，背包的容量为c。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i只有只有2种选择，即种选择，即装入背包或不装入背包。不能将物品装入背包或不装入背包。不能将物品i装入背包多次，也装入背包多次，也不能只装入部分的物品不能只装入部分的物品i。204.2.3、贪心算法与动态规划算法的差异背包问题：背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品可以选择物品i i的一部分的一部分，而不一定要全部装入背包，1in。这2类问题都具有最优子结构最优子结构性质，极为相似，

13、但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。21计算每种物品单位重量的价值vi/wi依贪心选择策略，将尽可能多的单位重量价单位重量价值最高值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。具体算法可描述如下：用贪心算法解背包问题的基本步骤：224.2.3、贪心算法与动态规划算法的差异void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int i;for(i=1;i=n;i+)x

14、i=0;float c=M;for(i=1;ic)break;xi=1;c-=wi;if(i=n)xi=c/wi;算法算法knapsack的的主要计算时间在于将主要计算时间在于将各种物品依其单位重各种物品依其单位重量的价值从大到小排量的价值从大到小排序。因此，算法的计序。因此，算法的计算时间上界为算时间上界为O（nlogn）。）。为了证明算法的正确为了证明算法的正确性，还必须证明背包性，还必须证明背包问题具有贪心选择性问题具有贪心选择性质质。230-10-1背包问题不适用贪心算法背包问题不适用贪心算法背包容量为背包容量为50kg，物品，物品1,2和和3的容量和价值分别的容量和价值分别为为(10

15、kg,$60),(20kg,$100)和和(30kg,$120)。单位重量价值最高的为物品单位重量价值最高的为物品1，6$/kg。但是依照。但是依照贪心算法首选物品贪心算法首选物品1却不能获得最优解：却不能获得最优解：物品物品1物品物品2物品物品1物品物品3物品物品2物品物品3总价总价值为值为$160,空余空余20kg总价总价值为值为$180,空余空余10kg总价值总价值为为$220,没有空没有空余。余。24对于0-1背包问题背包问题，贪心选择之所以不能得到最优解,是因为在这种情况下，无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。在考虑0-1背包问题时，应比较选择该

16、物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此导出许多互相重叠的子问题。这正是该问题可用动态规划算法动态规划算法求解的另一重要特征。25贪心选择与最优子结构贪心选择与最优子结构满足贪心选择性质必满足最优子结构性质。满足贪心选择性质必满足最优子结构性质。若原问题若原问题E的最优解的最优解A是经过有限次贪心选择是经过有限次贪心选择后获得的，则并必定包含了贪心选择后获得的，则并必定包含了贪心选择1。实际。实际上在选择了贪心选择上在选择了贪心选择1后，就将原问题分解为后，就将原问题分解为子问题子问题E和和E”，贪心选择，贪心选择1显然是显然是E的最优的最优解，而解，而A1必定是必定是E”

17、的最优解。否则将导的最优解。否则将导出出A不是最优解的矛盾。因此原问题的最优不是最优解的矛盾。因此原问题的最优解是由子问题的最优解组成的。用归纳法可解是由子问题的最优解组成的。用归纳法可证明其后的贪心选择同样保持最优子结构性证明其后的贪心选择同样保持最优子结构性质。质。n但是满足最优子结构性质却未必满足贪心选择但是满足最优子结构性质却未必满足贪心选择性质。性质。因为原问题因为原问题E尽管满足最优子结构性质，尽管满足最优子结构性质，即它的最优解即它的最优解A是由两个子问题的最优解是由两个子问题的最优解B1和和B2所构成的，但所构成的，但B1和和B2都不是用贪心选择可以都不是用贪心选择可以做出的。

18、例如在矩阵连乘积问题中：做出的。例如在矩阵连乘积问题中：mij=minikjmik+mk+1j+pi1pkpj这个断点这个断点k就不是用贪心选择可以做出来的。就不是用贪心选择可以做出来的。n因此能够应用动态规划法的不一定能够应用贪因此能够应用动态规划法的不一定能够应用贪心算法。心算法。n虽然能够应用贪心算法一定能够应用动态规划虽然能够应用贪心算法一定能够应用动态规划法，但是一般来说，贪心算法的效率高于动态法，但是一般来说，贪心算法的效率高于动态规划法，因而还是应用贪心算法。规划法，因而还是应用贪心算法。264.3 最优装载p有一批集装箱,要装上一艘载重量为c的轮船。其中集装箱i的重量为wi。p

19、最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。p算法描述算法描述p最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。274.3 最优装载Template void Loading(int x,Type w,Type c,int n)int*t=new int n+1;Sort(w,t,n);for(int i=1;i=n;i+)xi=0;for(int i=1;i=n&wti 1时,取y1=1,yk=0,yi=xi,1in,ik,则l故(y1,y2,yn)是所给最优装载问题的一个可行解.l而由(y1+y2+yn)=(x1+

20、x2+xn)知,(y1,y2,yn)是一个满足贪心选择性质的最优解.l最优装载问题具有贪心选择性质。x1=0,xk=1 29 3、最优子结构性质、最优子结构性质p若(x1,x2,xn)是最优装载问题的一个满足贪心选择性质的最优解,则有x1=1。p(x2,xn)是轮船载重量为c-w1且待装集装箱为2,3,n时,相应最优装载问题的一个最优解.p最优装载问题具有最优子结构性质。p由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。p算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。304.4 4.4 电脑里的数据压

21、缩电脑里的数据压缩 哈夫曼编码哈夫曼编码第一，可以节省空间第一，可以节省空间第二，可以减少对带宽的占用第二，可以减少对带宽的占用如果没有如果没有数据压缩技术数据压缩技术:没法用没法用WinRAR为为Email中的附件瘦身；中的附件瘦身；数码录音笔就只能记录不到数码录音笔就只能记录不到20分钟的语音；分钟的语音；从从Internet上下载一部电影要花太长的时间上下载一部电影要花太长的时间;31n严格意义上的数据压缩起源于人们对概率的认识严格意义上的数据压缩起源于人们对概率的认识n当对文字信息进行编码时，当对文字信息进行编码时，如果为出现概率较高的如果为出现概率较高的字母赋予较短的编码字母赋予较短

22、的编码，为出现概率较低的字母赋予，为出现概率较低的字母赋予较长的编码，较长的编码，总的编码长度就能缩短不少总的编码长度就能缩短不少。n远在计算机出现之前，著名的远在计算机出现之前，著名的Morse（摩尔斯式）（摩尔斯式）电电码就已经成功地实践了这一准则。码就已经成功地实践了这一准则。n在在Morse码表中，码表中，每个字母都对应于一个唯一的每个字母都对应于一个唯一的点划组合点划组合，出现概率最高的字母，出现概率最高的字母e被编码为一个点被编码为一个点“.”，而出现概率较低的字母，而出现概率较低的字母z则被编码为则被编码为“-.”。显然，这可以有效缩短最终的电码长度。显然，这可以有效缩短最终的电

23、码长度。32u设计具体的压缩算法的过程设计具体的压缩算法的过程通常更像是一场数学通常更像是一场数学游戏游戏。u要寻找一种要寻找一种能尽量精确地统计或估计信息中符号能尽量精确地统计或估计信息中符号出现概率的方法出现概率的方法u还要设计一套用最短的代码还要设计一套用最短的代码,描述每个符号的编描述每个符号的编码规则码规则u统计学知识对于前一项工作相当有效，已经陆续统计学知识对于前一项工作相当有效，已经陆续实现了实现了静态模型、半静态模型、自适应模型、静态模型、半静态模型、自适应模型、Markov Markov 模型、部分匹配预测模型模型、部分匹配预测模型等等概率统计模型概率统计模型。u相对而言，编

24、码方法的发展历程更为曲折一些。相对而言，编码方法的发展历程更为曲折一些。33p第一个实用的编码方法第一个实用的编码方法是由是由D.A.Huffman在在1952年的论文年的论文“最小冗余度代码的构造方法（最小冗余度代码的构造方法（AMethodfortheConstructionofMinimumRedundancyCodes）”中提出的。中提出的。p直到今天，许多直到今天，许多数据结构数据结构教材教材,在讨论二叉树在讨论二叉树时时,仍要提及这种称为仍要提及这种称为Huffman编码编码的方法。的方法。pHuffman编码在计算机界是如此著名，以至于连编码在计算机界是如此著名，以至于连编码的发

25、明过程本身也成了人们津津乐道的话题。编码的发明过程本身也成了人们津津乐道的话题。p据说，据说，1952年时，年轻的年时，年轻的Huffman还是还是麻省理工麻省理工学院的一名学生学院的一名学生，他为了向老师证明自己可以不参加，他为了向老师证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却某门功课的期末考试，才设计了这个看似简单，但却影响深远的编码方法影响深远的编码方法.34lHuffman编码效率高，运算速度快，实现方式灵活编码效率高，运算速度快，实现方式灵活，从，从20世纪世纪60年代至今，在数据压缩领域得到了广泛的应用。年代至今，在数据压缩领域得到了广泛的应用。l早期早期UN

26、IX系统上系统上,一个不太为现代人熟知的压缩程序一个不太为现代人熟知的压缩程序COMPACT,实际就是实际就是Huffman0阶自适应编码的具体实阶自适应编码的具体实现。现。l在许多知名的压缩工具和压缩算法（如在许多知名的压缩工具和压缩算法（如WinRAR、gzip和和JPEG）中，都有）中，都有Huffman编码的身影。编码的身影。l然而，然而，Huffman编码所得的编码长度编码所得的编码长度,只是对信息熵计算只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。结果的一种近似，还无法真正逼近信息熵的极限。l现代压缩技术通常只将现代压缩技术通常只将Huffman视作最终的编码手段，视

27、作最终的编码手段，而非数据压缩算法的全部。而非数据压缩算法的全部。35字符编码问题字符编码问题1编码和解码编码和解码数据压缩过程数据压缩过程称为称为编码编码。即将文件中的。即将文件中的每个每个字符字符均转换为一个惟一的均转换为一个惟一的二进制位串二进制位串。数据解压过程数据解压过程称为称为解码解码。即将二进制位串转。即将二进制位串转换为对应的字符。换为对应的字符。2等长编码方案和变长编码方案等长编码方案和变长编码方案给定的字符集给定的字符集C，可能存在多种编码方案，可能存在多种编码方案.36字符编码问题字符编码问题-字符字符abcdef频度（单位：千次）频度（单位：千次）4513121695定

28、长编码定长编码000001010011100101变长编码变长编码010110011111011100-设待压缩的数据文件共有设待压缩的数据文件共有100000个字符，这些字个字符，这些字符均取自字符集符均取自字符集C=a，b，c，d，e，f，其中每个，其中每个字符在文件中出现的字符在文件中出现的次数次数(简称简称频度频度)如下表：如下表：等长编码方案等长编码方案将给定字符集将给定字符集C中每个字符的码长定中每个字符的码长定为为log|C|，|C|表示字符集的大小表示字符集的大小等长编码等长编码需要需要3位二进制数字来表示六个字符，位二进制数字来表示六个字符，因此，整个文件的编码长度为因此，整

29、个文件的编码长度为300000位位。37变长编码方案变长编码方案将频度高的字符编码设置短，将频将频度高的字符编码设置短，将频度低的字符编码设置较长度低的字符编码设置较长根据计算公式：根据计算公式：(45*1+13*3+12*3+16*3+9*4+5*4)*1000=224000整个文件被编码为整个文件被编码为224000位，比定长编码方式位，比定长编码方式节约节约了了约约25的存储空间的存储空间前缀码方案前缀码方案对字符集进行编码时，要求字符集中对字符集进行编码时，要求字符集中任一字任一字符的编码都符的编码都不是不是其它字符编码的前缀其它字符编码的前缀，这种编码，这种编码称为称为前缀前缀(编编

30、)码码。等长编码是前缀码等长编码是前缀码38最优前缀码最优前缀码平均码长或文件总长最小的前缀编码平均码长或文件总长最小的前缀编码称为最优的称为最优的前缀码。前缀码。最优的前缀码对文件的压缩效果亦最佳最优的前缀码对文件的压缩效果亦最佳其中：其中：pi为第为第i个字符的频率个字符的频率li为码长为码长39译码需要方便地取出编码的前缀，需要前缀码合译码需要方便地取出编码的前缀，需要前缀码合适的数据结构适的数据结构二叉树二叉树（BinaryTree）树叶代表给定的字符树叶代表给定的字符每个字符的前缀码是每个字符的前缀码是从树根到代表该字符的树从树根到代表该字符的树叶叶的一条道路的一条道路代码中代码中0

31、、1分别作为分别作为指示某结点的指示某结点的左左儿子和儿子和右右儿子的儿子的“路标路标”。最优前缀码的二叉树总是一棵完全二叉树最优前缀码的二叉树总是一棵完全二叉树40树的路径长度树的路径长度定义为：树中每个结点的路径长度之和。结点的路径长度结点的路径长度定义为：从根结点到该结点的路径上 分支的数目。一棵树上两个结点间的路径一棵树上两个结点间的路径：从一个结点到另一个结点之间所有的分支构成路径。41ABCDEFGH ID到H的路径 DGHD到H路径的长为2 A到H的路径 ADGHA到H路径的长为3树的路径长度=1+1+1+2+2+2+3+3=15n个结点的二叉树路径长度最小的是完全二叉树42二叉

32、树带权路径的长ABCDEFGH I每个叶子结点都带权的二叉树叫带权二叉树7524叶结点C的权为7，根结点A到C走7次的路径长度称为A到C的带权路径的长根到每个叶的带权路径的长的总和叫二叉树的带权路径的长本树带权路径的长=7*3+5*2+2*3+4*3=49带权路径的长带权路径的长WPL=wklkk=1n43n个叶结点,权分别为w1,w2,wn的二叉树中带权路径长度WPL最小的二叉树叫Huffman Tree 最优二叉树最优二叉树 也叫也叫赫夫曼树赫夫曼树 哈夫曼树哈夫曼树，霍夫曼树，霍夫曼树 52745274WPL=49WPL=(7+5+2+4)*2 =364452475247WPL=36WP

33、L=7+5*2+2*3+4*3 =35哈夫曼树 45哈夫曼编码哈夫曼编码哈夫曼哈夫曼提出提出构造最优前缀码构造最优前缀码的贪心算法的贪心算法u贪心策略与最优二叉树贪心策略与最优二叉树哈夫曼算法以哈夫曼算法以自底向上自底向上的方式构造表示的方式构造表示最优前最优前缀码缀码的二叉树的二叉树T。算法以算法以|C|个叶结点开始，执行个叶结点开始，执行|C|1次的次的“合合并并”运算后运算后,产生最终所要求的树产生最终所要求的树T。46哈夫曼算法1）根据给定的权值w1,w2,wn构造n个 二叉树F=T1,T2,Tn,每个Ti只有一个 根结点，权为wi。2）在F中选取两棵根结点的权值最小的树 构成一棵新的

34、二叉树，其根的权值为左 右子树根的权值的和。3）F中删去这两棵树，加上新得的树。4）重复2）3）直到只剩一棵树。471.贪心选择性质贪心选择性质p设设C是编码字符集，是编码字符集，C中字符中字符c的频率为的频率为f(c)。p设设x,y是是C中具有最小频率的两个字符，则存在中具有最小频率的两个字符，则存在C的的最优前缀码最优前缀码,使使x,y具有相同码长且仅有最后一位编码具有相同码长且仅有最后一位编码不同不同。证明：（证明：（思路思路）设二叉树设二叉树T是是C的任意一个最优前缀码，的任意一个最优前缀码，只需要证只需要证明明对对T作适当的修改后得到一新的二叉树作适当的修改后得到一新的二叉树T，使，

35、使得新树中得新树中x,y是最深叶子且为兄弟，同时新树是最深叶子且为兄弟，同时新树T表示的前缀码也是表示的前缀码也是C的一个最优前缀码。的一个最优前缀码。哈夫曼算法的正确性哈夫曼算法的正确性48xycbTbycxTbcyxT设设b,c是是T中最深叶子且为兄弟，设中最深叶子且为兄弟，设f(b)f(c),f(x)f(y),则则f(x)f(b),f(y)f(c).在在T中交换中交换b,x的位置得到的位置得到T，继续在，继续在T交换交换c,y的位置得到的位置得到T.49首先，树首先，树T，T的前缀码的平均码长之差为的前缀码的平均码长之差为同样，可以证明同样，可以证明c与y不变,相减抵消 50由于由于T是

36、是C的一个最优前缀码，故的一个最优前缀码，故新树新树T T 表示的前缀码也是表示的前缀码也是C C的一个最优前缀码的一个最优前缀码，x,y是最深叶子且为兄弟，是最深叶子且为兄弟，x,y具有相同码长且仅具有相同码长且仅有最后一位编码不同有最后一位编码不同.512 2 最优子结构性质最优子结构性质n设设T是表示是表示C的一个最优前缀码的完全二叉树，的一个最优前缀码的完全二叉树，C中字符中字符c的频率为的频率为f(c)。设。设x,y是是T中两个叶子结点中两个叶子结点且为兄弟，且为兄弟，z为它们的父结点。为它们的父结点。n若将若将z看作是具有频率看作是具有频率f(x)+f(y)的字符，则树的字符，则树

37、T=T-x,y表示字符集表示字符集C=(C-x,y)z的一个最的一个最优前缀码。优前缀码。证明证明：先证先证T的平均码长的平均码长B(T),可用可用T的平均码长的平均码长B(T)表示：表示：52由（*）式和（*）式两端相加得：53若若T表示的表示的C前缀码不是最优的，则存在前缀码不是最优的，则存在T表示表示的的C的最优前缀码，的最优前缀码，(T)B(T).uz作为作为C中的一个字符，故中的一个字符，故z作为作为T中的一个叶中的一个叶子，若将子，若将x,y加入加入T中，作为中，作为z的儿子结点，得到的儿子结点，得到表示表示C的前缀码的二叉树的前缀码的二叉树T，与最优矛盾与最优矛盾T表示的表示的C

38、的前缀码是最优的的前缀码是最优的满足最优子结构性质满足最优子结构性质54哈夫曼编码的实现算法算法huffmanTree中，编码字符集中中，编码字符集中c的频率是的频率是f(c)。以以f为键值的优先队列为键值的优先队列Q用在贪心选择用在贪心选择时，有效地确定时，有效地确定算法当前要合并的算法当前要合并的2棵具有最小频率的树。棵具有最小频率的树。一旦一旦2棵具有最小频率的树合并后，产生一棵新树，棵具有最小频率的树合并后，产生一棵新树，频率为其合并频率之和，并将新树插入优先队列频率为其合并频率之和，并将新树插入优先队列Q。经过经过n1次的合并后，优先队列中只剩下一棵树，即次的合并后，优先队列中只剩下

39、一棵树，即所要求的树所要求的树T。初始化初始化Q需要需要O(n)计算时间，由于最小堆的计算时间，由于最小堆的removeMin和和put运算均需运算均需O(logn)时间，时间，n1次的合次的合并总共需要并总共需要O(nlogn)计算时间。计算时间。n个字符的哈夫曼算法的计算时间为个字符的哈夫曼算法的计算时间为O(nlogn)554.5 4.5 单源最短路径单源最短路径给定一个图给定一个图G=(V,E)，其中每条边的权，其中每条边的权是一个非负实数。另外给定是一个非负实数。另外给定V中的一个顶中的一个顶点点v，称为，称为源源。问题问题：求从源求从源v v到所有其它各个顶点的最到所有其它各个顶点

40、的最短路径短路径。单源最短路径问题的贪心选择策略：单源最短路径问题的贪心选择策略：选择选择从源从源v出发目前用最短的路径所到达的顶出发目前用最短的路径所到达的顶点点，这就是目前的局部最优解。，这就是目前的局部最优解。56单源最短路径的贪心算法单源最短路径的贪心算法基本思想基本思想：设置一个集合：设置一个集合S，初始时，初始时S中仅含中仅含有源有源v，然后，然后不断地用贪心选择来扩充这个集不断地用贪心选择来扩充这个集合合，直至直至S包含所有包含所有V中顶点中顶点。把从源到把从源到u中间中间只经过只经过S中顶点中顶点的路称为的路称为从源从源到到u的特殊路径的特殊路径，用，用distu来记录当前顶点

41、来记录当前顶点u所对应的所对应的最短特殊路径长度最短特殊路径长度。贪心选择贪心选择：每次找到最小的每次找到最小的distu，将，将u添加添加到到S中，同时对数组中，同时对数组dist作必要的修改。作必要的修改。57Dijkstra算法算法Dijkstra(迪杰斯特拉迪杰斯特拉)算法算法思想思想：由近到远逐步计算，每次最近的顶点的距离由近到远逐步计算，每次最近的顶点的距离就是它的最短路径长度。就是它的最短路径长度。再从这个最近者出发。即再从这个最近者出发。即依据最近者修订到依据最近者修订到各顶点的距离各顶点的距离，然后再选出新的最近者。，然后再选出新的最近者。如此走下去，直到所有顶点都走到。如此

42、走下去，直到所有顶点都走到。58Dijkstra 算法算法Procedure(1)S:=1;/初始化初始化S(2)fori:=2tondo/初始化初始化D(3)disti=C1,i;/Ci,j表示边表示边(i,j)的权，初始时为的权，初始时为源到顶点源到顶点i的一步距离的一步距离(4)fori:=1ton-1do(5)从从V-S中选取一个顶点中选取一个顶点u使得使得distu最小；最小；(6)将将u加入到加入到S中；中；/将新的最近者加入将新的最近者加入S(7)for wV-Sdo/依据最近者依据最近者u修订修订distw(8)distw:=min(distw,distu+Cu,w)59Dij

43、kstra算法举例算法举例迭代 S u dis2 dis3 dis4 dis5初始 1 -10 30 100 1 1,2 2 10 60 30 100 2 1,2,4 4 10 50 30 90 3 1,2,4,3 3 10 50 30 60 4 1,2,4,3,5 5 10 50 30 60 12543102050100301060加权图加权图Gp由数组由数组disi可知：从顶点可知：从顶点1到顶点到顶点2、3、4、5的的最短通路的长度分别为最短通路的长度分别为10、50、30和和60。60Dijkstra算法的计算复杂性算法的计算复杂性Dijkstra算法有两层循环，外层循环为算法有两层循

44、环，外层循环为n次，次，内层有两个循环：一个是选出最小的内层有两个循环：一个是选出最小的u(第第5行行)，另一个是修订，另一个是修订disw(第第7、8行行)。它们。它们的次数都是的次数都是n/2，所以内层循环的时间为，所以内层循环的时间为O(n)。Dijkstra算法的时间复杂度为算法的时间复杂度为O(n2)Dijkstra算法能求出从源到其它各顶点的最算法能求出从源到其它各顶点的最短通路的长度，但是却短通路的长度，但是却并没有给出其最短通并没有给出其最短通路路。可借助。可借助prev数组得到。数组得到。61Dijkstra算法的正确性算法的正确性算法的贪心选择算法的贪心选择：若：若u是是V

45、S中具有最短特殊路中具有最短特殊路径的顶点，就将径的顶点，就将u选入选入S，并确定了从源到，并确定了从源到u的的最短路径长度最短路径长度distu。i.e.,下一条最短路径是中下一条最短路径是中间只经过间只经过S中顶点而最后到达中顶点而最后到达u的路径。的路径。为什么为什么从源到从源到u没有更短的路径呢没有更短的路径呢？若有，则如下图所示：若有，则如下图所示：Svdistu(最近距离最近距离)uxdistx若该路径经若该路径经S外一点外一点x到到达达u，则：，则：distx+d(x,u)distu从而从而distxdistu，这与这与u的选取矛盾的选取矛盾类似可证最优子结构性质类似可证最优子结

46、构性质624.6 4.6 最小生成树最小生成树设设G=(V,E)是一个是一个无向连通带权无向连通带权图，即一个网络。图，即一个网络。E的每条边的每条边(v,w)的权为的权为cvw。如果如果G的一个子图的一个子图G是一棵包含是一棵包含G的所有顶点的的所有顶点的树，则称树，则称G为为G的生成树的生成树。生成树的生成树的各边权的总和各边权的总和称为该称为该生成树的耗费生成树的耗费。在在G的所有生成树中，耗费最小的生成树称为的所有生成树中，耗费最小的生成树称为G的的最小生成树最小生成树MST(minimum spanning tree)。63树的基本性质树的基本性质连通无回路的图连通无回路的图G称为称

47、为树树。树是点比边多一的树是点比边多一的连通图连通图:G连通且连通且q=p1。树是点比边多一的树是点比边多一的无回路图无回路图：G无回路且无回路且q=p1。树若加条边就有回路树若加条边就有回路：G无回路，但对任意的无回路，但对任意的u,vV(G)，若若uv E(G)，则则G+uv中恰有一条回路。中恰有一条回路。树若减条边就不连通树若减条边就不连通：G连通，但对连通，但对 eE(G),Ge不连通。不连通。n个顶点的连通图的生成树含有个顶点的连通图的生成树含有n1条边。条边。64最小生成树的贪心选择性质最小生成树的贪心选择性质令令G中权最小的边为中权最小的边为e1。必定有图。必定有图G的一棵最小生

48、的一棵最小生成树包含了成树包含了e1。若若G的任何最小生成树都不包含的任何最小生成树都不包含e1。设设T为为G的最的最小生成树，小生成树，e1 T。于是。于是T+e1是一个有回路的图是一个有回路的图且该回路中包含且该回路中包含e1。该回路中必有条不是。该回路中必有条不是e1的边的边ei。令。令T=T+e1ei。T也是也是G的生成树。又的生成树。又c(T)=c(T)+c(e1)c(ei)，c(e1)c(ei)，从而，从而c(T)c(T)，T是是G的最小生成树且含有边的最小生成树且含有边e1。矛。矛盾。故必定有图盾。故必定有图G的最小生成树包含了的最小生成树包含了e1。n选定第一条边选定第一条边e

49、1以后，该如何选择第二条边呢以后，该如何选择第二条边呢？n依据各条边的权重，依次选出权重较轻的n 1条边。这n 1条边必定包括了G的n个顶点。这样就得到了G的一棵最小生成树。这样做是否可以呢？这样做是否可以呢？n不行！因为不能保证这不行！因为不能保证这n1条边构成树？条边构成树？n要保证这要保证这n1条边构成树，必须使这条边构成树，必须使这n1条边条边是连通的或者是无回路的。是连通的或者是无回路的。nPrim算法的做法算法的做法：在保证连通的前提下在保证连通的前提下依次选依次选出权重较小的出权重较小的n1条边（在实现中体现为条边（在实现中体现为n个个顶点的选择）。顶点的选择）。nKruskal

50、算法算法的做法的做法：在保证无回路的前提下在保证无回路的前提下依次选择权重较小的依次选择权重较小的n1条边。条边。65Prim算法算法基本思想：基本思想：在保证连通的前提下依次选出权重较在保证连通的前提下依次选出权重较小的小的n n 1 1条边条边。G=(V,E)为无向连通带权图，令为无向连通带权图，令V=1,2,n。设置一个集合设置一个集合S，初始化，初始化S=1，T=。贪心策略贪心策略：如果：如果VS中的顶点中的顶点j与与S中的某个点中的某个点i连连接接,且且(i,j)是是E中的权重最小的边，则选择中的权重最小的边，则选择j(将将j加加入入S)，并将，并将(i,j)加入加入T中。中。重复执