《算法设计与分析实用教程-电子教案-杨克昌 第7章 贪心算法》由会员分享，可在线阅读，更多相关《算法设计与分析实用教程-电子教案-杨克昌 第7章 贪心算法（30页珍藏版）》请在金锄头文库上搜索。
1、教学要求 了解贪心算法的概念与贪心策略的选择 掌握应用贪心算法设计求解删数字问题、可拆背包问题与数列操作问题等最优化典型案例 本章重点 根据案例的实际选择与确定贪心策略,第 7 章 贪心算法,7.1 贪心算法概述,7.1.1 贪心算法的概念 (1) 贪心算法又称贪婪算法，是一种着眼局部的简单而适应范围有限的优化策略。 (2) 当一个问题具有最优子结构性质时，贪心算法有时比动态规划法求解更为简单有效。 (3) 贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是做一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是局部最优选择
2、。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。,（4）贪心策略的选择,贪心算法没有固定的算法框架，算法设计的关键在于贪心策略的选择与确定。 贪心算法的基本思想是通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。 应用贪心算法所做的每一步选择都必须满足： 1）可行的：必须满足问题的约束条件。 2）局部最优：当前所有可能的选择中选择使局部最优的决策。 3）不可取消：选择一旦做出，在后面的步骤中无法改变。 贪心算法是通过做一系列的选择来求出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择，这种启发式策略并不总能产生出最
3、优解。,贪心算法的理论基础为拟阵，是组合优化与图论的重要内容。 矩阵胚（matroid）又称为拟阵，是一个满足以下交换性质的特殊子集系统： 判断一个子集系统是不是矩阵胚常应用以下性质： 定理1 一个子集系统是矩阵胚当且仅当所有极大独立子集具有相同的基数。 例如,若S是一个矩阵中行向量集合，I是S的线性独立子集族，则（S,I）是矩阵胚。 定理2 子集系统优化问题的贪心算法正确，当且仅当该子集系统是一个矩阵胚。,7.1.2 贪心算法的理论基础,7.2 背包问题,7.2.1 可拆背包问题,/ 已对n件物品按单位重量的效益降序排序 cw=c;s=0; / cw为背包还可装的重量 for(i=1;icw
4、) break; xi=1.0; / 若w(i)cw,装入一部分) s=s+pi*xi;,3. 贪心算法描述,7.3 删数字问题,案例提出： 在给定的n个数字的数字串中，删除其中k(kn)个数字后，剩下的数字按原次序组成一个新的正整数。请确定删除方案，使得剩下的数字组成的新正整数最大。 例如在整数79502867154829179316中删除8个数字后，所得最大整数为多大？,操作对象是一个可以超过有效数字位数的n位高精度数，存储在数组a中。 在整数的位数固定的前提下，让高位的数字尽量大，整数的值就大。这就是所要选取的贪心策略。 每次删除一个数字，选择一个使剩下的数最大的数字作为删除对象。选择这
5、样“贪心”操作，是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。 当k=1时，在n位整数中删除哪一个数字能达到最大？从左到右每相邻的两个数字比较：若出现增，即左边数字小于右边数字，则删除左边的小数字。若不出现增，即所有数字全部降序或相等，则删除最右边的小数字。,1. 贪心算法设计要点,例如，在18位整数762191754639820463中，删除1个数字，使剩下的17位数最大，如何删？ 要使删除1个数字后的17位数最大，须首位数字最大。首先，首位数字“7”大于第2位数字“6”比较，首位数字“7”不能删！ 往后推，“6”与“2”比较，因62，为减，“6”不能删； 再往后推，“2”与
6、“1”比较，因21,为减，“2”不能删 ； 继续往后推，“1”与“9”比较，因11（当然小于n），按上述操作,每一次操作从串首开始，每相邻的两个数字比较，出现“增”时，删除左边的小数字。每次操作删除一个数字后，后面的数字向前移位。 因此，只要从左至右每两相邻数字比较，出现“增”，即删除首数字。直到不出现“增”时，此时如果还不到删除指定的k位，打印剩下串的左边nk个数字即可（相当于删除了余下的最右边若干个小数字）。,printf(“ 删除数字个数: “);scanf(“%d“,2. 贪心算法描述,1）以上贪心删数字算法每删除一个数字ai-1，赋值i=0，即必须从头开始查找递增区间。其实此时只需从
7、ai-2开始查找递增区间即可，因为先前的操作能够保证ai-2及之前的数字不是递增区间。 2）以上贪心删数字算法每删除一个数字ai-1，必须逐一把其后的数字往前移动一位，如果n及k相当大，移动过程花费较大。其实每删除数字后，并不一定需要移动数字的位置，只对所删除数位赋标记值-1即可，代表该位置的数字已经删除。同时，查找递增区间时跳过该数位。,3. 贪心算法改进,7.4 埃及分数式,案例提出： “埃及分数”为分子为1的分数。 人们研究较多且颇感兴趣的问题是:把一个给定的分数转化为若干个不相同的埃及分数之和，约定埃及分数的分母不能与给定分数的分母相同。常把分解式中埃及分数的个数最少，或在个数相同时埃
8、及分数中最大分母为最小的分解式称为最优分解式。 对把给定分数分解为埃及分数之和，或对已有的埃及分数式进行优化，往往是一个繁琐艰辛的过程。 例如，对3/11，可分解为: 3/11=1/5+1/15+1/165 试寻求分数3/11新的埃及分数式。,1贪心算法设计要点,2贪心算法设计步骤,以上贪心选择时，每一步都选比本分数小的最大埃及分数。这样尽管快速，但因为太严格可能会失去一些构建时机，或者可能根本找不到埃及分数式。 试把埃及分数贪心选择的环境适当放宽，选择范围适当扩大，即埃及分数的分母由以上贪心选择最小分母c=int(b/a)+1，扩展至c=int(b/a)+d，这里d为放宽尺度1,5等。必要时
9、可把该尺度作扩大或缩小调整。,3贪心选择范围的扩展,7.5.1 数列操作 案例提出： 给定一个由n个正整数组成的数列，对数列进行一次操作：去除其中两项a、b，然后添加一项ab+1。每操作一次数列减少一项，经n1次操作后该数列只剩一个数。 试求在n-1次操作后最后得数的最大值。,7.5 数列操作与极差,设数列有3项x，y，z (xyz)，由 (xy+1)z+1 (xz+1)y+1 (yz+1)x+1 可知选取数列中最小的2项操作，可使积最大。 采用贪心算法，当数列中有3项以上时，为使最后所得数最大，每次选择去掉最小的2项操作。 设置a数组存储数列各项，同时对n项进行升序排列。,1. 贪心算法设计
10、 要点,为了得到最大值，设置控制n-1次操作的k（1n-1）循环。每次操作对最小的前2 项ak、ak+1实施操作： x=ak;y=ak+1;ak+1=x*y+1; 操作后，应用逐项比较对ak+1，an进行升序排列，为下一次操作做准备。 最后所得an即为所求的数列操作的最大值。 因应用逐项比较进行排列，其时间复杂度为O(n2)，因而数列操作的贪心设计的时间复杂度为O(n3)。,/ 先行对原始数据a数组升序排序 for(k=1;kaj) h=ai;ai=aj;aj=h; printf(“n 最大值为：%ld n“,an);,2. 贪心算法设计 描述,按贪心算法，每次操作只对最小的两项进行操作，因而
11、无须对整个数列排序。我们只要把实施排序的2重循环 for(i=k+1;i=n-1;i+) for(j=i+1;j=n;j+) 改进为: for(i=k+1;i=k+2;i+) for(j=i+1;j=n;j+) 这样，把原排序的时间复杂度O(n2)降低为O(n)，于是整个数列操作的时间复杂度降低至O(n2)。,3. 贪心算法设计 优化,7.6.1 哈夫曼树 设二叉树共有n个端点，从二叉树第k个端点到树的根结点的路径长度l(k)为该端结点（或叶子）的祖先数，即该叶子的层数减1。同时，每一个结点都带一个权（实数），第k个端点所带权为w(k)。定义各个端结点的路径长l(k)与该点的权w(k)的乘积之
12、和为该二叉树的带权路径长，即 对n个权值w(1),w(2),w(n)，构造出所有由n个分别带这些权值的叶结点组成的二叉树，其中带权路径长wpl最小的二叉树称为哈夫曼树。,7.6 哈夫曼树及其应用,例如，给出5个权值5,4,7,2,8,可生成多棵二叉树，下图所示为其中的3棵： 它们的带权路径长wpl分别为 (a) wpl=73+23+42+52+82=61 (b) wpl=53+23+82+42+72=59 (c) wpl=23+43+52+72+82=58 比较所有的二叉树，其中图(c)的wpl最小，即为对应权5,4,7,2,8的哈夫曼树。,哈夫曼给出一个贪心策略的算法，称为哈夫曼算法。 1）
13、 根据给定的n个权值w(1),w(2),w(n)构成n棵二叉树的森林F=(T1,Tn)。其中每棵二叉树中只有一个带权为w(k)的根结点，其左右子树为空。 2） 在F中选取两棵结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上结点权值之和。 3） 在F中删除这两棵树，并把新得的二叉树加入F中。 4） 重复以上 2），3），直到F只含一棵树为止。这棵树即为哈夫曼树。,1. 哈夫曼算法,1） 首先，对给定的n个权值作升序排列。 2） 设置n-1次操作的k（1n-1）循环，在第k次操作中，由两个最小权值叶结点生成一个新结点： x=w2*k-1; y=w2*k;
14、 wn+k=x+y; lcn+k=x; rcn+k=y; 3） 新结点参与排序，为下一次操作做准备。 考虑到每一次排序可能改变w数组元素顺序，设置u数组，每次所得新结点，其数据传送给u数组，最后输出时不是按已改变次序的w数组，而是按u数组输出。 4） 为具体画出哈夫曼树提供方便，输出展示每一个结点的左右子结点的表。,1. 哈夫曼算法要点,for(k=1;kwj) h=wi;wi=wj;wj=h; for(j=2*k+1;j=n+k;j+) / 输出第k次操作结果 printf(“ %d“,wj); if(wj=z) printf(“(%d+%d)“,x,y); printf(“n 最小带权路径
15、长为：%d “,s);,2. 哈夫曼算法描述,7.7 贪心算法应用小结,比较动态规划与贪心算法都是求解最优化问题： 1. 着眼点不同 动态规划算法着眼全局，而贪心算法着眼局部。 2. 求解的结果可能不同 动态规划算法求解结果总是最优的，贪心算法对大多数优化问题能得到最优解，但有时并不能求得最优解。 3. 求解效率上的差异 从求解效率来说，贪心算法比动态规划更高，且一般不存在空间限制的影响。 4. 求解范围上的差异 应用贪心算法有时可简化一些构造性问题。,第7章 作业,习题7: 1, 2, 3, 4,第7章上机,（1） 上机通过本章删数字、埃及分数式、可拆背包与数列操作问题等典型案例； （2） 上机通过习题7-5,7-6； （3） 分组讨论：数列操作优化及其时间复杂度；哈夫曼树与哈夫曼编码实现。,欢迎大家提出教学建议,返回,
