《算法设计与分析教学资料》第4章

1、1,第4章 贪心算法,2,理解贪心算法的概念 掌握贪心算法的基本要素 （1）最优子结构性质 （2）贪心选择性质 理解贪心算法与动态规划算法的差异 理解贪心算法的一般理论,学习要点,3,通过应用范例学习贪心设计策略 （1）活动安排问题； （2）最优装载问题； （3）哈夫曼编码； （4）单源最短路径； （5）最小生成树； （6）多机调度问题。,学习要点,4,问题描述： 有位顾客买了两斤苹果，需付3元7角，实付10元，你需找零6元3角。假设你抽屉里有一些硬币，面值分别为：2元5角、1元、5角和1角，现在问题是：怎么找币最快（取硬币次数最少）？,贪心算法的引入-找币问题,5,问题抽象： M=6.3 ，

2、n=4 V=2.5, 1.0, 0.5 ,0.1（分量用vi表示） X= x1, x2, x3, x4 （xi=0, i=14） 问题即求: 约束条件：,贪心算法的引入-找币问题,6,贪心算法的引入- 0-1背包问题,0-1背包问题的形式化描述： 约束条件： 结论：找币问题可以使用动态规划算法实现！ 思考：找币问题还可以使用其他方法求解吗？,7,一种更简单可行的方法： 先取2.5 2枚 价值2.5+2.5=5.0 余6.3-5=1.3 再取1.0 1枚 价值1.0 余1.3-1=0.3 不取0.5 0枚 因为0.50.3 再取0.1 3枚 价值0.13=0.3 余0.3-0.3=0 找零完毕。

3、 得最优解X= 2, 1, 0, 3 ，共需最少的硬币数6枚。 方法总结：在不超余额的前提下，每次都找最大面值的硬币。这种找币的方法叫做贪心算法。 思考：有没有可能不是最好的方法？,贪心算法的引入-找币问题,8,顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。,贪心算法描述,9,在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近

4、似。 动态规划一定可以得到问题最优解，而贪心算法不一定，这也是贪心算法使用的困难之处，如何去证明它得到的是问题需要的解。,贪心算法描述,10,贪心算法描述,11,贪心算法基本思想,12,贪心算法基本思想,13,活动安排问题引入,新学期来临，为迎接新生，各院系都要举办迎新晚会。时间将近，各院系在申请使用学院礼堂进行彩排。为了提高礼堂使用率，决定白天不间断的开放，各院系可以上报各自使用的时间区间（开始时间以及终止时间，时间长短不限），由礼堂管理人员安排尽可能多的院系在同一天里彩排。 请根据以下时间段尽可能多安排几个院系：8:00,10:30), 9:00,11:30), 7:00,11:00),

5、11:30-14:00), 12:00,13:30) , 13:00,15:30), 15:00,16:00), 14:30,16:00), 16:00,18:00),14,活动安排问题描述,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的典型例子。 该问题要求高效地安排一系列争用某一公共资源的活动。 贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,15,活动安排问题描述,设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源（争用！）。 每个活动i都有一个要求使用

6、该资源的起始时间si和一个结束时间fi,且sifi 。 如果选择了活动i，则它在时间的半开半闭区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。,16,活动安排问题解决方案,将各活动的起始时间和结束时间存储于数组s和f中，且按结束时间的非减序排列： f1=f2 =f3. . =fn 即需要先对各活动按结束时间排序。 如：2,3), 1,4), 3,5), 1,2) 按结束时间排序后： 1,2), 2,3), 1,4), 3,5),剩余时间越多，可安排的活动就越多！,17,活动安排问题算

7、法实现,public static int greedySelector(int s, int f, boolean a) int n=s.length-1; a1=true; /加入最早结束的活动 int j=1; /刚加入集合的活动号 int count=1; for (int i=2;i=fj) ai=true; j=i; /j用以记录最近一次加入到集合A中的活动 count+; else ai=false; return count; ,各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列,18,活动安排问题算法分析,由于输入的活动以其完成时间的非减序排列，所以算法Gr

8、eedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。 直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。 也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。,19,活动安排问题算法分析,算法GreedySelector的效率极高。当输入的活动已按结束时间的非减序排列时，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。 如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,20,例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：,活动安排问题示例,21,活动安排问

9、题示例,22,计算过程如左图所示。 图中每行相应于算法的一次迭代。 阴影长条表示的活动已选入集合，而空白长条表示当前正在检查相容性的活动。 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。,23,活动安排问题结论,考虑：完整的算法如何实现？,24,贪心算法的基本要素,下面着重讨论可以用贪心算法求解的问题的一般特征。 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质： 贪心选择性质 最优子结构性质,2

10、5,1.贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。,贪心算法的基本要素贪心选择性质,26,贪心算法的基本要素贪心选择性质,1.贪心选择性质 动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因此，动态规划算法通常以自底向上的方式解各子问题。 贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最

11、优解。,27,2.最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,贪心算法的基本要素最优子结构性质,28,以下证明活动安排问题具备这两个基本要素，即可由贪心算法求最优解。,贪心算法的基本要素活动安排问题,29,设E1,2,n为所给的活动集合。 E中活动按结束时间的非减序排列，故活动1具有最早的完成时间。 首先，需要证明活动安排问题有一个（仅有一个？）最优解以贪心选择开始，即该最优解中包含活动1。,活动安排问题-贪心选择性质,30,设A是E的一个子集，且A是所给的活动安排问题的一个最优

12、解，且A中活动也按结束时间非减序排列，A中第一个活动是活动k。 若k=1，则A中第一个活动是活动1，活动1是E中最早结束的，即A就是一个以贪心选择开始的最优解。 若k1，则我们可以设B=(A-k) 1.即用活动1替换掉活动k，由于f1fk，且A中活动是互为相容的，故B中活动也是互为相容的（说明B是一个可行解）。又B中活动个数与A中活动个数相等，且A是最优的，则B也是最优的。,活动安排问题-贪心选择性质,31,也就是说，B是一个以贪心选择活动1开始的最优活动安排。因此，我们证明了总存在一个以贪心选择开始的最优活动安排方案（a） 。 以下证明在贪心选择了活动1之后，原问题简化为对E中所有与1相容的

13、活动进行活动安排的子问题。,活动安排问题-贪心选择性质,32,若A是原问题的一个以贪心选择开始的最优解，则 A=A-1是活动安排问题E=iE:sif1的一个最优解。 -最优子结构性质 证明：如能找到E的一个解B，它包含比A更多的活动，则将活动1加入B中将产生E的一个解B，它包含比A更多的活动。这与A的最优性矛盾。,活动安排问题-最优子结构性质,33,因此，每一步所作的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题（b） 。 综合a和b，对贪心选择的次数用数学归纳法即知，贪心算法GreedySelector最终产生原问题的一个最优解。,活动安排问题-最优子结构性质,34,贪心算法与

14、动态规划算法的差异,贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。 但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解? 是否能用动态规划算法求解的问题也能用贪心算法求解? 下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。,35,0-1背包和一般背包问题,36,0-1背包和一般背包问题,0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?,在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品

15、i装入背包多次，也不能只装入部分的物品i。,37,0-1背包和一般背包问题,一般背包问题（简称背包问题）：,38,0-1背包和一般背包问题,一般背包问题（简称背包问题）： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。 这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。,39,0-1背包和一般背包问题,一般背包问题（简称背包问题）：,40,0-1背包和一般背包问题,贪心选择的策略有哪些呢？ 每次从剩余的物品中，选出可以装入背包的价值最大的物品。 从剩下的物品中选择可装入

16、背包的重量最小的物品。 从剩余物品中选择可装入包的vi /wi 值（性价比效益值）最大的物品。,41,0-1背包和一般背包问题,42,0-1背包和一般背包问题,43,0-1背包和一般背包问题,44,0-1背包和一般背包问题,45,0-1背包和一般背包问题,用贪心算法解背包问题的基本步骤： 首先，计算每种物品单位重量的价值Vi/Wi ； 然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。 若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去，直到背包装满为止。,46,public static floa

17、t knapsack(float c,float w, float v,float x) int n=v.length; Element d = new Element n; for (int i = 0; i c) break; xdi.i=1; opt+=di.v; c-=di.w; if (in) xdi.i=c/di.w; opt+=xdi.i*di.v; return opt; ,算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为 O（nlogn）。 当然，为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。,47,0-1

18、背包和一般背包问题,实例：背包容量50千克； 物品1重10千克，价值60元； 物品2重20千克，价值100元； 物品3重30千克，价值120元。 若该实例为背包问题，则可用贪心算法求得最优解240； 若该实例为0-1背包问题，则用贪心算法求得解为160，而最优解实为220(由动态规划法求得)。,48,0-1背包和一般背包问题,对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。,49,0-1背包和一般背包问题,虽然使用贪心选择不能保证得到0-1背包的最优解，但它是一个直觉上近似的解。 在600个随机产生

19、的0-1背包问题中，用这种启发式贪婪算法来解有239题可得到最优解，所有600个答案与最优解之差全在25%以内。,50,0-1背包和一般背包问题,事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。,51,贪心算法的局限性,52,贪心算法的特点,53,哈夫曼编码描述,哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。 哈夫曼编码算法用字符在文件中出现的频率表来建立一个用

20、0,1串表示各字符的最优表示方式。 给出现频率高的字符以较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。,54,哈夫曼编码回忆,55,哈夫曼编码回忆,56,哈夫曼编码回忆,解决的问题: 通讯过程中需将传输的信息转换为二进制码。由于英文字母使用频率不同,若频率高的字母对应短的编码,频率低的字母对应长的编码,传输的数据总量就会降低。要求找到一个编码方案,使传输的数据量最少。,57,哈夫曼编码前缀码,哈夫曼编码是一种前缀码。 1、前缀码 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。,58,哈夫曼编码前缀码,非前缀码 如：a

21、 b c d 0 10 101 11 试译出：1010 结果会有两种：bb 或 ca 原因在于：b的代码是c的代码的前缀。 哈夫曼编码是一种前缀码，可以避免以上情况。,59,哈夫曼编码前缀码,编码的前缀性质使译码方法非常简单。 001011101 (P96表4.1) 0 0 101 1101 a a b e,60,哈夫曼编码前缀码,用二叉树作为前缀编码的数据结构（why?） 表示最优前缀码的二叉树总是一棵完全二叉树（定义有什么问题？） 树中任一结点都有2个儿子结点。 每个叶子对应字符集中的一个字符。,61,哈夫曼编码前缀码,定义：f(c)是字符集C中字符c的出现频率，dT(c)是叶子结点c在树

22、中的深度（此时根的深度应该是多少？）。 则：平均码长定义为： 使平均码长达到最小的前缀码编码方案称为字符集C的一个最优前缀码。,62,哈夫曼编码构造,2、构造哈夫曼编码 德国数学家哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。,63,哈夫曼编码构造,贪心准则： 每次找出具有最小频率的两棵树合并,64,哈夫曼编码构造,算法思路： 1)以n个字母为结点构成n棵仅含一个点的二叉树集合,字母的频率即为结点的权 2)每次从二叉树集合中找出两个权

23、最小者合并为一棵二叉树：增加一个根结点将这两棵树作为左右子树，新树的权为两棵子树的权之和 3)反复进行步骤2)直到只剩一棵树为止,设在1000个字母的文章中各字母出现的频率为: a:83, b:14, c:28, d:38, e:131, f:29, g:20, h:53.,14 20 28 29 38 53 83 131,34 28 29 38 53 83 131,34 57 38 53 83 131,57 72 53 83 131,72 110 83 131,110 155 131,155 241,396,396,155,241,110,131,53,57,72,83,34,38,28,2

24、9,14,20,1,0,1,0,1,0,1,0,1,0,1,0,1,0,最佳编码: a:10 ; b:1111; c:0101; d:110; e:00; f:0100; g:1110; h:011,1)将权从小到大排序 2)每次选取最小权合并,66,哈夫曼编码构造,哈夫曼算法构造哈夫曼树的具体过程： 一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。,template BinaryTreeHuffmanTree(T f, int n) /根据权f1:n构造哈夫曼树 /创建一个单节

25、点树的数组 Huffman *W=new Huffman n+1；/构造n个Huffman对象W BinaryTree z,zero；/初始化空树 for(int i=1；i Q(1)； Q.Initialize(w,n,n)；,哈夫曼树算法,/将堆中的树不断合并 Huffman x, y for(i=1;in;i+) /从Q中取出具有最小频率的两棵树x和y Q.DeleteMin(x)； Q.DeleteMin(y)； /将x和y合并为一棵新树z z.MakeTree(0, x.tree, y.tree)； /z的频率是x和y的频率之和 x.weight+=y.weight；x.tree=z

26、； Q.Insert(x)； Q. DeleteMin(x)；/最后的树 Q. Deactivate()； delete w； return x.tree；,哈夫曼树算法,69,哈夫曼编码构造,算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。,70,哈夫曼树算法,算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间; 最小堆的DeleteMin和Insert运算均需O(logn)时间,n1次的合并总共需要O(nlogn)计算时间。 因此，关于n个字符的哈夫曼

27、算法的计算时间为O(nlogn) 。,71,哈夫曼编码正确性,3、哈夫曼算法的正确性 要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。,最优子结构: 设T为带权w1w2. wt的最优树,若将以带权w1和w2的树叶为儿子的分枝点改为带权w1+w2的树叶,得到一棵新树T, 则T也是最优树。,贪心选择性 : 设T为带权w1w2. wt的最优树, a).带权w1和w2的树叶vw1和vw2是兄弟. b).以vw1和vw2为儿子的分枝点,其通路长度最长.,算法分析,HuffmanTree初始化优先队列Q需要O(n) DeleteMin和Insert需O(logn). n-

28、1次的合并总共需要O(nlogn) 所以n个字符的哈夫曼算法的计算时间为O(nlogn),哈夫曼树算法,哈夫曼编码正确性,73,单源最短路径描述,单源最短路径问题: 给定带权有向图G =(V,E)，其中每条边的权是非负实数。 给定V中的一个顶点，称为源。 计算从源到所有其它各顶点的最短路长度。这里路的长度是指路径上各边权之和。,74,单源最短路径基本思想,Dijkstra(迪杰斯特拉 )算法是解单源最短路径问题的贪心算法。基本思想: 一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 设置顶点集合S并不断地作贪心选择（是什么？）来扩充这个集合。,75,单源最短路径基本思想,贪心策略：

29、每次都从V-S中找出具有最短特殊路长的顶点u加入S。,76,单源最短路径基本思想,算法思路： 初始时，S中仅含有源。 设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。,77,单源最短路径基本思想,算法思路： Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。 一旦S包含了V中所有顶点，dist就记录了从源到其它所有顶点之间的最短路径长度。,78,单源最短路径示例,例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其他顶点间最短路

30、径的过程列在下页的表中。,79,单源最短路径示例,Dijkstra算法的迭代过程：,80,单源最短路径算法描述,Template Void Dijkstra(int n,int v,Type dist,int prev,Type *c) /单源最短路径问题的Dijkstra算法 /初始化 bool smaxint; /顶点集合s，maxint是大整数 for(int i=1;i=n;i+) /n个顶点 disti=cvi; /cvi表示边(v,i)的权邻接矩阵 /disti表示从源v到i的最短路长 si=false; if(disti=maxint) previ=0; else previ=v

31、; /previ表示从源到i的路径上i之前的那个点 ,81,单源最短路径算法描述,/初始s中仅含源v distv=0; sv=true; /迭代n-1次，把所有点加入s for(int i=1; in; i+) /找到具有最短特殊路长度的顶点u int temp=maxint; int u=v; for(int j=1; j=n; j+) if(!sj),82,单源最短路径算法描述,/对数组dist作必要的修改 for(int j=1; j=n; j+) if(!sj) ,83,单源最短路径分析,算法的正确性和计算复杂性 (1)贪心选择性质 (2)最优子结构性质 (3)计算复杂性 对于具有n个

32、顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要 时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。,84,最小生成树描述,设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。 如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费。 在G的所有生成树中，耗费最小的生成树称为G的最小生成树。,85,最小生成树描述,网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城

33、市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。,86,最小生成树描述,用贪心算法设计策略可以设计出构造最小生成树的有效算法。 本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。 尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质。,87,最小生成树性质,1、最小生成树性质 设G=(V,E)是连通带权图，U是V的真子集。如果(i,j)E，且iU，jV-U，且在所有这样的边中，(i,j)的权cij最小，那么必存在一棵包含边(i,j)的最小生成树。这个性质也称为MST（Minimum Spanning Tree）性质。,88,最小生成树Prim算法,2、