《算法设计与分析DesignandAnalysisofComputerAlgorithm.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析DesignandAnalysisofComputerAlgorithm.ppt（81页珍藏版）》请在三一文库上搜索。
1、算法设计与分析 Design and Analysis of Computer Algorithm,信息工程学院,张永梅,学时分配,第三章 贪心算法,1、基本要求 要求掌握贪心算法的基本思想，运用的条件和限制及常见问题的求解算法。,第三章 贪心算法,2、教学内容 基本思想 背包问题 带有限期的作业排序 最优归并模式,第三章 贪心算法,3、学习目标 掌握贪心算法的基本思想； 掌握贪心法怎样被运用到本章所举的各种问题中； 理解各种问题的具体算法； 了解算法分析。,实验2 贪心算法上机,一、实验目的 1掌握贪心算法的基本思想和效率分析方法； 2掌握贪心算法最优度量标准的选取方法； 3学会利用贪心算法
2、解决实际问题。,已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi，假定将物品i的某一部分xi放入背包就会得到pixi的效益(0xi1, pi0) ，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？并请对自己的程序进行复杂性分析。,二、实验内容,实验2 贪心算法上机,张静： 15501273231 5教802,在现实世界中，有这样一类问题：有n个输入，它的解就由这n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。 把那些必须满足的条件称为约束条件，把满足约束条件的子集称为该问题的可行解。显然满足约束条件的子集可能不止一个，因此可行解不是唯一的。 为了衡量可行解的
3、优劣，以函数的形式给出一个衡量标准，这个函数就称为目标函数。那些使目标函数取极大（极小）值的可行解称为最优解。,3.1 基本思想,解决这类问题的目标就是：目标函数取极大（极小）值的可行解，即寻找最优解。 对于这类需要求取最优解的问题，根据描述约束条件和目标函数的数学模型的特征或求解问题方法的不同，除了可以使用线性规划、整数规划、非线性规划、动态规划等方法求解外，还可以使用一种更直接的贪心法求解。本章就是学习用贪心法解决问题。,顾名思义，贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，我们希望贪心算法得到的最终
4、结果也是整体最优的。 虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。如图的单源点最短路径问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。,贪心算法虽不能保证得到最优结果，但对于一些除了“穷举”方法外没有有效算法的问题，用贪心算法往往能很快地得出较好的结果。 如果此较好结果与最优结果相差不是很多的话，此方法还是很实用的。,贪心法的基本思想： 贪心法是一种改进了的分析处理方法，它首先根据题意选取一个度量标准，以这个标准把这n个输入排序，并按排序顺序一次输入一个量。然后把这个新的输入与当前已构成的
5、在这种度量意义下的部分解加在一起，考察新增这个输入后是否能够产生一个可行解，如果不能，则不把这个输入加入到这部分已经存在的可行解中。,用贪心法处理问题的核心是度量标准的选取。对于一个给定的问题，可以选取的度量标准可能会出现多个，但并不是这些都是可取的。尤其需要指出的是把目标函数作为度量标准得到的解并不是问题的最优解。关于这一点，在学习用贪心法求解背包问题时，会有深刻的体会。因此，选择能产生问题最优解的最优度量标准是使用贪心法设计求解的核心问题。,3.1 基本思想,某一问题的n个输入,该问题的一种解（可行解）,是A的一 个子集,满足一定 的条件,约束条件,目标函数,取极值,最优解,根据题意，选取
6、一种量度标准，然后按量度标准对n个输入排序，按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。,量度标准,该种量度意义下的部分最优解,原问题的n个输入,排序后的n个输入,A(j),3.1 基本思想,贪心方法的抽象化控制,Procedure GREEDY(A,n) solution for I1 to n do xSELECT(A) if FEASIBLE(solution,x) then solutionUNION(solution,x) endif re
7、peat return (solution) End GREEDY,按某种最优量度标准从A中选择一个输入赋给x，并从A中去除,判断x是否可以包含在解向量中,将x与解向量合并，并修改目标函数,贪心算法基本思想,将问题的求解过程看作一系列选择，每次选择一个输入，每次选择都是当前状态下的最好选择(局部最优解)。每作一次选择后，所求问题会简化为 一个规模更小的子问题，从而通过每一步的最优解逐步达到整体最优解。,第三章 贪心算法,教学内容 基本思想 背包问题 带有限期的作业排序 最优归并模式,3.2 背包问题,问题描述 已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi，假定将物品i的某一部
8、分xi放入背包就会得到pixi的效益(0xi1, pi0) ，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？ 问题的形式描述 极大化 pixi 约束条件 wi xi M 0xi1, pi0, wi0, 1in,1in,1in,目标函数,背包问题实例,考虑下列情况的背包问题 n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10) 其中的4个可行解是：,贪心方法的数据选择策略(1),用贪心策略求解背包问题时，首先要选出最优的度量标准。选取目标函数为量度标准，每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益
9、值的非增次序将物品一件件放到背包中。 如果正在考虑的物品放不进去，则可只取一部分来装满背包，当最后一种物品放不下时，才选择一个适当的xi 1 ，使物品装满背包。这里的最优化量度是Pi最大。,贪心方法的数据选择策略(2),按上述的数据选择策略，装入顺序是按照物品的效益值从大到小的输入，由刚才的实例可得这种情况下的总效益值为28.2，是一个次优解，原因是背包容量消耗过快。 以容量作为量度，可让背包容量尽可能地被消耗。这就要求按物品重量的非降次序来把物品放入背包，由刚才的例子可得这种情况下的总效益值为31，仍是一个次优解，原因是容量在慢慢消耗的过程中，效益值却没有迅速的增加。,贪心方法的数据选择策略
10、(3),采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准。即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需使物品的装入次序按pi/wi比值的非增次序来考虑。 这种策略下的量度是已装入物品的累计效益值与所用容量之比。上述例子中的第四个可行解就是这种策略下得到的解。,首先把物品按照P(i)/W(i)P(i+1)/W(i+1)的衡量标准排序，以此顺序读入物品。并且定义一个大小为物品多少的解向量X，X的一个分量就代表某个物品的装入情况。对于当前正在读入考虑的物品i，如果它能够整个装入背包，则相应的X(i)就为1，代表物品被整个装下，并且背包的剩余容量将减少物品i所占
11、用的那么多重量; 如果它不能够整个装入背包，则相应的X(i)就为cu/W(i)，表示最后装入了W(i)分之cu那么多物品。对于n个物品装入背包，则用一个n次循环来完成。,背包问题的贪心算法及说明,P(1:n)用于存放n个物品的效益值，W(1:n)存放n个物品的重量值，X(1:n)存放将要求的向量解。M代表总重量，cu代表背包在某个时刻所能容纳的剩余容量。特别说明的是，物品在P(1:n) 和W(1:n)中已经按照P(i)/W(i)P(i+1)/W(i+1)的衡量标准排序。,背包问题的贪心算法,Procedure GREEDY-KNAPSACK(P,W,M,X,n) real P(1:n),W(1
12、:n),X(1:n),M,cu; integer I,n; X0;cuM for I1 to n do if W(I)cu then exit endif X(I)1;cucu-W(I) repeat if in then X(I)cu/W(I) endif End GREEDY-KNAPSACK,将解向量X初始化为0 cu为背包的剩余容量,只放物品i的一部分,结论： 1、如果将物品分类的时间不算在内，此算法的时间复杂度为O(n)。,2、单位容量中的最大效益作为衡量标准的贪心法所得到的解是背包问题的一个最优解。,算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因
13、此，算法的计算时间下界为 O（nlogn）。 当然，为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。,最优算法,问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。 例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。 堆排序算法是最优算法。,最优解的证明,定理3.1 如果p1/w1 p2/w2 pn/wn，则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。,最优解的证明,基本思想 假设贪心解不是最优解，则把这个贪心解与任一最优解相比较，如果这两个解不同，就去找不相等的且下标最小的第一
14、个xi，然后设法用贪心解的这个xi去代换最优解的那个xi ，并证明最优解在分量代换前后的总效益值无任何变化。 反复进行这种代换，直到新产生的最优解与贪心解完全一样，即推出与假设矛盾的结论，从而证明了贪心解就是最优解。,证明 设X=(x1,x2,xn)是GREEDY-KNAPSACK所生成的解，但不是最优解。如果所有的xi等于1，显然这个解就是最优解。 设j是使xj1的最小下标。由算法可知，对于1ipixi(1in ) 。不失一般性，可以假定wiyiM (1in ) 。设k是使得ykxk的最小下标。显然，这样的k必定存在。,由上面的假设，可以推得ykj三种情况分别进行证明：,由上面的假设，可以推
15、得ykj分别进行证明： 若kj，则xk1。因ykxk，从而ykxk。,证明 设X=(x1,x2,xn)是GREEDY-KNAPSACK所生成的解，但不是最优解。 设j是使xj1的最小下标。由算法可知，对于1ipixi(1in ) 。不失一般性，可以假定wiyiM (1in ) 。设k是使得ykxk的最小下标。,由上面的假设，可以推得ykj分别进行证明： 若kj，由于wixiM(1in) ，且对于1ixk，显然有wiyiM (1in) 。 与Y是可行解矛盾。若ykxk，与假设ykxk矛盾，故ykxk。,由上面的假设，可以推得ykj分别进行证明： 若kj，则wiyiM(1in)，这是不可能的。,若
16、kj，则xk =0，因ykxk，从而yk 0 。 设j是使xj1的最小下标。由算法可知，对于1ixk,若kj，则wiyiM(1in)，这是不可能的。,现在，假定把yk增加到xk，那末必须从(yk+1,yn)中减去同样多的量，使得所用的总容量仍是M。这导致一个新的解Z(z1,z2,zn)，取新的向量z=(z1,z2,zn)满足 z1=y1, z2=y2, zk-1= yk-1, zk= xk 0zk+1yk+1, , 0znyn而且 这样的向量z是存在的，而且是0/1背包问题的解，因为,由上面的假设，可以推得ykj分别进行证明：,至此，我们找到一个新的解向量z。以下证明它的总价值不小于y的总价值
17、：,中间的不等式是由于当ik时有pk/wkpi/wi而得。但z与x的不同分量的个数比y与x的不同分量的个数至少减少一个。以z代替y进行上面的讨论，我们又可以找到新的解向量 。 如此等等，由于分量的个数n有限，必到某一步停止，我们能找到解向量y*,它和x有相同的分量，又与y有相同的总价值（大于x的总价值），矛盾。 这个矛盾源于x不是最优解的假设。故x是最优解。,至此，我们找到一个新的解向量z。以下证明它的总价值不小于y的总价值：,贪心算法主要用于处理优化问题。每个优化问题都是由目标函数和约束条件组成。满足约束条件的解称为可行解，而那些使得目标函数取极值的可行解称为最优解。 如0/1背包问题是一个
18、优化问题，式(3.2)中的函数是目标函数，而(3.3)式描述的要求是约束条件，这里优化是使目标函数取最大值。贪心算法在每一步的决策中虽然没有完全顾忌到问题整体优化，但在局部择优中是朝着整体优化的方向发展的。为此，贪心算法首先要确定一个度量准则，每一步都是按这个准则选取优化方案。如0/1背包问题的贪心准则是选取单位价值p/w最大物品。,背包问题中的物体不能分拆，只能整个装入称为0-1背包问题，用贪心算法能得到0-1背包的最优解吗?,最小代价通讯网络 在N城市之间架设通讯线路,要求造价最低。城市之间所有可能的通讯连接视作一个无向图G，G中每条边的权值表示建成这段线路的代价。问题转化为求一棵最小生成
19、树。,问题描述: 输入:任一连通图G: (e1,em) (该图的边集合) 可行解:图G的生成树 优化函数:生成树的各边权值之和 最优解:使优化函数达到最小值的生成树,最优化问题(optimization problem): 问题可描述为有n个输入(x1,x2,.,xn),一组约束条件和一个优化(目标)函数。满足约束条件的输入称为可行解,它是输入的一个子集，使优化函数取得极值的可行解称为最优解。,适用问题 具备贪心选择和最优子结构性质的最优化问题,算法优点 求解速度快，时间复杂性有较低的阶。,整体的最优解可通过一系列局部最优 解达到。每次的选择可以依赖以前作 出的选择,但不能依赖于后面的选择。,
20、问题的整体最优解中包含着它的子问题的最优解。,算法缺点 需证明是最优解。,常见应用,背包问题，最小生成树，最短路径，作业调度等等,贪心算法的基本要素,对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。,贪心算法的基本要素,1.贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。 贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每
21、作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。,贪心算法的基本要素,2. 最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。,贪心算法的基本要素,0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为pi，背包的容量为M。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?,在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也
22、不能只装入部分的物品i。,贪心算法的基本要素,背包问题： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。,这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。,贪心算法的基本要素,用贪心算法解背包问题的基本步骤： 首先计算每种物品单位重量的价值Pi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过M，则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去，直到背包装满为止。,贪
23、心算法的基本要素,对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。,第三章 贪心算法,教学内容 基本思想 背包问题 带有限期的作业排序 最优归并模式,3.3 带有限期的作业排序,问题描述 假定只能在一台机器上处理n个作业，每个作业均可在单位时间内完成；又假定每个
24、作业i都有一个截止期限di0(是整数)，当且仅当作业i在它的截止期限之前被完成时，则获得pi0的效益。 这个问题的一个可行解是这n个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成，可行解的效益值是J中这些作业的效益之和p。具有最大总效益值的可行解就是最优解。,带有限期的作业排序实例,例3.2 n=4,(p1,p2,p3,p4)=(100,10,15,20)和(d1,d2,d3,d4)=(2,1,2,1),这个问题可能的可行解和他们的效益值为：,3.3 带有限期的作业排序算法,为了得到最优解，应制定如何选择下一个作业的量度标准，利用贪心策略，使得所选择的下一个作业在这种量度下达到
25、最优。 可把目标函数p作为量度，则下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下使p得到最大增加的作业，这只需要将pi按降序来排列就可以了。,算法3.3 带有限期的作业排序算法,作业按p1 p2 pn的次序输入： Procedure GREEDY_JOB(D,J,n) J1 for I2 to n do if JI的所有作业都能在他们的截止期限前完成 then JJI endif repeat End GREEDY_JOB,在这个概略的算法中需要解决的关键是如何判断作业I并入J后仍然能够保证J中的所有作业都能够在它们的截止期限前完成。在做这个判断之前先看两个定理。,定理3.
26、2：算法3.3所描述的贪心方法对于作业排序问题总是得到一个最优解。,定理3.3：设J是k个作业的集合，=i1i2ik是J中作业的一种排列，它使得di1di2dik。J是一个可行解，当且仅当J中的作业可以按照的次序而又不违反任何一个期限的情况来处理。,可行解的确定,对于给定的J，确定它是否可行的一般方法为： 检查J中所有作业的所有可能的排列，对于任一种次序排列的作业序列，判断这些作业是否能在它的期限前完成。 假定J中有k个作业，这就需要检查k！个排列。对于所给出的一个排列=i1i2ik，由于完成作业ij（1jk）的完工时间是j，因此，只要判断出排列中的每个作业的jdij，就可得知是一个允许的调度
27、序列，从而J就是一个可行解。反之，如果排列中有一个jdij，则是一个行不通的调度序列，因为至少作业ii不会在它的限期前完成，故必须去检查J的另外形式的排列。,可行解的确定,对于给定的J，确定它是否可行的一种方法为： 特殊情况：只需检验当J中作业按期限的非降次序排列时，作业I是否能在规定的时间内完成。 定理3.3 设J是k个作业的集合，=i1i2ik是J中作业的一种排列，它使得di1di2dik。J是一个可行解，当且仅当J中的作业可以按照的次序而又不违反任何一个期限的情况来处理。,第三章 贪心算法,教学内容 基本思想 背包问题 带有限期的作业排序 最优归并模式,3.4 最优归并模式（哈夫曼树）,
28、问题的描述： 已知：由n个文件要归并成为一个文件，每个文件的长度为ni，其中任意两个文件i和j归并为一个文件的时间是O(ni+nj)，移动次数为ni+nj。,求取：怎样归并这n个文件，使归并所需要的总时间和总的移动次数最少。,X1,X2,X3,X4,3.4 最优归并模式（哈夫曼树）,什么是归并模式,给出n个文件，则有许多种把这些文件成对地归并成一个单一分类文件的方法。 不同的配对方法要求不同的计算时间。 问题的关键是：确定一个把n个已分类文件归并在一起的最优方法（即需要最少的比较的方法）。,最优归并模式的实现,由于归并一个具有n个记录的文件和一个具有m个记录的文件可能需要m+n次记录移动，因此
29、对于量度标准的一种很明显的选择是：每一步都归并尺寸比较小的两个文件。 例如：有五个文件(F1,F5)=(20,30,10,5,30),5,F4,10,F3,二元归并树,贪心法求文件最优归并的分析,贪心法求文件最优归并很容易描述。由于归并一个具有n个记录的文件和一个具有m个记录的文件可能需要n+m次记录移动，因此对于贪心法量度标准的一种明显的选择是：每一步都归并尺寸最小的两个文件。,从上面的例子，我们可以知道所描述的归并模式被称为二路归并模式，这种模式的归并在归并过程中形成一棵树。,最优归并模式的实现,带权外部路径长度 如果di表示由根到代表文件Fi的外部节点的距离，qi表示Fi的长度，则这棵二
30、元归并树的记录移动总量是： diqi 这个和数叫做这棵树的带权外部路径长度。,i=1,n,一个最优二路归并模式与一棵具有最小外部路径的二元树相对应。,从对带权外部路径长度的解释，我们可以发现：一个最优二路归并模式与一棵具有最小权外部路径的二元树相对应。于是可以得到启示，用贪心法求取文件的最优归并等价于求取一棵具有最小权外部路径的二元树。,把每个文件看成树的叶子结点，文件的长度看成结点的权。起初把每个结点都看成一棵树，每个结点就是一棵单根树。归并时，每次选取权值最小的两棵树，把它们连接到一个新结点上。新结点的权值是这两棵子树权值之和，其中一个子树作为这个新结点的左子树，另一个作为右子树。这样选取
31、的两棵子树和这个新结点又形成一棵新的树，新结点是根。由此不断地重复上面的过程，直到只剩下一棵树。,二元归并树算法,二元归并树算法把n个树的表L作为输入。树中的每一个结点有三个信息段(LCHILD,RCHILD,WEIGHT)。,算法运行期间，对于L中的任何一棵具有根结点T的树， WEIGHT(T)表示要归并的文件的长度。 WEIGHT(T)=树T中外部结点的长度和,起初，L中的每一棵树正好有一个结点。这个结点是一个外部结点，而且其LCHILD和RCHILD信息段为0，而WEIGHT是要归并的n个文件之一的长度。,二元归并树算法,Line procedure TREE(L,n) for I1 t
32、o n-1 do call GETNODE(T) LCHILD(T)LEAST(L) RCHILD(T)LEAST(L) WEIGHT(T)WEUGHT(LCHILD(T)+WEUGHT(RCHILD(T) call INSERT(L,T) repeat return (LEAST(L) End TREE,每个节点有三个信息：LCHILD,RCHILD,WEIGHT,构造一个新结点,找出L中一棵具有最小WEIGHT的树，并删除,把根为T的树插入到表L中,二元归并树算法的计算时间,例：L最初有6个文件，长度分别为：2,3,5,7,9,13 二元归并树算法的计算时间 主循环执行n-1次 如果L中W
33、EIGHT的值为非降次序，则LEAST(L)只需要O(1)的时间 INSERT(L,T)在O(n)时间内被执行 因此，此算法的计算总量为：O(n2),一棵有n个叶子结点的Huffman树有2n-1个结点,最优解证明,定理3.4 若L最初包含n1个单个结点的树，这些树有WEIGHT值为(q1,q2,qn)，则算法TREE对于具有这些长度的n个文件生成一棵最优的二元归并树。 证明（略）,哈夫曼编码,哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 给出现频率高的字符较短的编
34、码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 前缀码 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。,哈夫曼编码,编码的前缀性质可以使译码方法非常简单。 表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。,二叉树的应用 哈夫曼树(Huffman)带权路径长度最短的树 定义 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的 路径长度：路径上的分支数 树的路径长度：从树根到每一个结点的路径长度之和 树的带权路径长度：树中所有带权结点的路径长度之和,Huffman树设有n个权值w1,w2,wn
35、，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树。,例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,构造Huffman树的方法Huffman算法 构造Huffman树步骤 根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令其权值为wj 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和 在森林中删除这两棵树，同时将
36、新得到的二叉树加入森林中 重复上述两步，直到只含一棵树为止，这棵树即为哈夫曼树。,在远程通讯中，要将待传字符转换成由二进制的字符串： 设要传送的字符为： ABACCDA 若编码为：A00 B01 C10 D-11,若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。,00010010101100,设要传送的字符为： ABACCDA 若编码为 ：A0 B110 C10 D-111,0110010101110,A,C,B,D,0,0,0,1,1,1,采用二叉树设计二进制前缀编码,规定：左分支用“0”表示；右分支用“1”表示,译码
37、过程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。,0110010101110,A,C,B,D,0,0,0,1,1,1,ABACCDA,求Huffman编码：由根叶子，若： （1）从左分支下去，则分支为“0”； （2）从右分支下去，则分支为“1”。,A,C,B,D,0,0,0,1,1,1,例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。 由Huffman树得Huffman编码为： T B A C S 00 01 10 110 111,出现频率越大的字符，其H
38、uffman编码越短。,贪心算法的理论基础,借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。 拟阵 拟阵M定义为满足下面3个条件的有序对(S,I)： (1) S是非空有限集。 (2) I是S的一类具有遗传性质的独立子集族，即若BI，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集必为I的成员。 (3) I满足交换性质，即若AI,BI且|A|B|，则存在某一元素xB-A，使得AxI。,小结,贪心算法的基本思想、流程； 使用贪心方法解决背包问题。,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。 虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,