《JX算法分析与设计（四）贪心算法课件》由会员分享，可在线阅读，更多相关《JX算法分析与设计（四）贪心算法课件（41页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计（四） -贪心算法,教学课件,主讲人：王春平 Email : ,浙江工业大学计算机学院,2,活动安排问题 贪心算法的基本要素 最优装载 哈夫曼编码 单源最短路径,主要内容,3,活动安排问题(1),活动安排问题(Activity-Selection Problem) 问题约束： 1) 设有n个活动的集合E=1, 2, , n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。 2) 每个活动i要求使用该资源的起始时间为si，结束时间fi , 且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。 3) 相容规则的定义：若
2、区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。即：当sifj或sjfi时，活动i与活动j相容。 求解目标： 要求在上述活动集合中选出最大的相容活动子集合 。,4,活动安排问题(2),使用贪心算法求解活动安排问题： 1) 令数组s和f分别存储了各活动的起始时间和结束时间，其中f数组是按活动结束的非减序排序的，即：f1f2 fn。 2) 数组A用于存储对各活动的选择结果，即：Ai=true表示活动i被选择，Ai=false表示活动i未被选择。 算法如下：,template void GreedyActivitySelector(int n, Type s, Type f
3、, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; ,算法的复杂度为：(n),5,活动安排问题(3),GreedyActivitySelector算法示例,设有11个活动待安排，它们的起始时间和结束时间排列如下：,图例说明： 1) 每行相应于算法的一次循环。 2) 阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。,6,活动安排问题(4),GreedyAcitivitySelector贪心算法的解析： 1) 由于输入的活动以其完成时间的非减序排列，所以算法G
4、reedyActivitySelector每次总是选择具有最早完成时间的相容活动加入集合A中。即：该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 2) 算法GreedyActivitySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,7,活动安排问题(5),GreedyAcitivitySelector贪心选择的正确性证明1（每次贪心选择都是贪相容的结束时间最早的活动）：,设：E=1,2,n为活动集合，其中的活
5、动是按照结束时间的非减序排列。 令：A是E的活动安排问题的某个最优解(A也是按结束时间非减序排列)，则显然有： ，现在要证明：一定存在着一个最优解A，其第一个活动为活动1（即：贪心的第1步是正确的）。 现假设最优解A集合的第一个活动是k。 若k=1，则与贪心的第一次选择相符合，说明第一次贪心是对的。 若k1，则设 ， 由于 f1= fk ，且A中的活动是相容的，因此B中的活动也是相容的， 又因为，B的活动个数与A的活动个数相同，由A最优可推知B也是最优。 故：活动B是一个以活动1开始的最优解。 证毕（即总存在着以贪心选择开始的最优解）。,8,活动安排问题(6),GreedyAcitivityS
6、elector贪心选择的正确性证明2（每次贪心选择都是贪相容的结束时间最早的活动）： 前面我们证明了第一次贪心能够得到一个最优解（即第一次贪心的方向是正确的），下面要证明该最优解（除去活动1）仍然是所产生子问题的最优解。,经过第1次贪心后，情况变成：活动1已被选择，问题就简化为：对E中所有与活动1相容的活动的活动安排问题。 设：A是原问题的最优解(含活动1)，则有： 是 的一个最优解。 反证法： 如果能找到E的一个解B,它包含比A更多的活动，则将活动1加入到B中将产生E的一个解B，它包含了比A更多的活动。这与假设相矛盾，证毕。 依此类推，问题最终证明可以由数学归纳法得证。,9,活动安排问题 贪
7、心算法的基本要素 最优装载 哈夫曼编码 单源最短路径,主要内容,10,贪心算法的基本要素(1),用贪心算法求解的问题一般具有2个重要的性质：贪心选择性质(Greedy-choice Property)和最优子结构性质(Optimal substructure)。 贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选择)来求解出。这是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 贪心选择性质的证明：即要证明每一步所作的
8、贪心选择最终导致问题的整体最优解。 最优子结构性质：问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,11,贪心算法的基本要素(2),散装背包问题(Fractional Knapsack Problem)： 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。物品i可以部分装入背包，那么如何选择装入背包的物品，使得装入背包中物品的总价值最大? 解题思路： 1) 计算每种物品单位重量的价值vi/wi； 2) 依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。 3) 若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高
9、的物品并尽可能多地装入背包。如此贪心选择直到背包装满为止。,12,贪心算法的基本要素(3),散装背包问题(Fractional Knapsack Problem)：,void FractionalKnapsack(int n, float M, float v,float w,float x) Sort(n, v, w); /按vi/wi进行排序 int i; for (i=1; ic) break; xi=1; c-=wi; if (i=n) xi=c/wi; ,说明：算法的计算时间上界为O(nlogn)。,13,贪心算法的基本要素(4),散装背包问题示例：,令： n=5, c=10, w=
10、2, 2, 6, 5, 4, v=6, 3, 5, 4, 6,按vi/wi排序后： n=5, c=10, w=2,2,4,6,5, v=6,3,6,5,4 1) c=10，放入物品1，c=c-w1=c-2=8，x1=1 2) c=8，放入物品2， c=c-w2=c-2=6，x2=1 3) c=6，放入物品3，c=c-w3 =c-4=2，x3=1 4) c=2，放入物品4，w4c，故x4=c/w4=2/6=1/3 最终，放入物品的价值为：v1+v2+v3+v4/3=15+5/3。,14,贪心算法的基本要素(5),散装背包问题和0-1背包问题的求解讨论： 1) 贪心算法不能求得0-1背包问题的最优
11、解，因为它无法保证尽量将背包装满，部分闲置的背包空间会使每公斤背包空间的价值降低了。 2) 动态规划算法也可以用于求解散装背包问题，但是效率要比贪心算法低的多。,15,贪心算法的基本要素(6),贪心算法求解0-1背包问题的反例：,令： n=3, c=50, w=10,20,30, v=60,100, 120,贪心算法,非贪心算法,非贪心算法,16,活动安排问题 贪心算法的基本要素 最优装载 哈夫曼编码 单源最短路径,主要内容,17,最优装载问题(1),最优装载问题 约束与目标：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽
12、可能多的集装箱装上轮船。 问题的形式化描述：,规划目标：,约束条件：,说明： xi=0表示集装箱i不装入，xi=1表示集装箱i 装入,18,最优装载问题(2),最优装载问题的贪心策略：重量最轻者先装。 算法描述如下：,template void Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); /t表示排序后的集装箱数组 for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n ,19,最优装载问题(3),最优装载问题：贪心选择性质的证明。
13、,设：集装箱已按重量从小 到大排序，(x1, x2, , xn)是一个最优解， k=min i | xi=1且1in，如果 问题有解，显然有： 1kn。 1) 当k=1时， (x1, x2, , xn)是满足贪心选择性质的最优解。 2) 当k1时，取y1=1，yk=0，yi=xi，1i n，i k，则有：,故：(y1, y2, , yn)是所给定最优装载问题的可行解。,又：由 可知，(y1, y2, , yn)是满足贪心选择性质 的最优解。因此，最优装载问题具有贪心选择性质。,最优装载问题：最优子结构性质的证明。,设：集装箱已按重量从小 到大排序，(x1, x2, , xn)是一个满足贪心性质
14、的最优解，则易知，x1=1， (x2, , xn)是轮船载重量为c-wi，待装船集装箱为2, 3, , n时相应最优装载问题的最优解。,20,活动安排问题 贪心算法的基本要素 最优装载 哈夫曼编码 单源最短路径,主要内容,21,哈夫曼编码(1),哈夫曼编码( Huffman Codes，P109 )：广泛用于数据文件(如传真、图像)的无损压缩，压缩率常在20%90%之间。 文件编码问题描述： 给定一个文件，该文件长度为 100,000 个字符，其中包含a, b, c, d, e和f 六种字符，各字符出现频率如下表，试对该文件进行编码存储。,22,哈夫曼编码(2),定长码(Fixed-lengt
15、h Codeword)存储：,定长码文件长度为：3*100,0000=300,000 位(bits),变长码(Variable-length Codeword)存储(Huffman编码)：,变长码文件长度为：45*1+13*3+12*3+16*3+9*4+5*4=224,000 位(bits),23,哈夫曼编码(3),变长编码的贪心策略2：频率越高，使用越少编码位。,变长码文件长度为：45*1+13*1+12*2+16*2+9*3+5*3=156,000 位(bits)，这样得到了最大压缩率，但是这样存在解码问题。示例如下：,abcdef,011011100101,贪心策略2： (解码歧义),
16、abcdef,010110011111011100,Huffman编码： (解码无歧义),24,哈夫曼编码(4),前缀码 (Prefix Codes)的概念： 对每个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。 前缀码的性质使译码方法非常简单，例如：001011101，根据上述编码可直接译出：aabe。 Huffman提出了最优前缀码的贪心算法。,David A. Huffman ( 1925.08 - 1999.10 ),1944年在俄亥俄州立大学(Ohio State University)获学士学位。 1945-1946年在美国海军服役，工作内容是在驱逐舰上维护雷达。 1949年在俄亥俄州立大学获硕士学位。1953年在MIT获博士学位，在攻读博士学位期间提出了Huffman编码( “A Method
