算法课件资料第4章贪心算法.pptVIP

第4章 贪心算法 学习要点 贪心算法的基本思想 贪心算法的基本要素 （1）最优子结构性质 （2）贪心选择性质 贪心算法与动态规划算法的差异 正确性的证明 范例学习贪心设计策略 （1）活动安排问题； （4）单源最短路径； （2）最优装载问题； （5）最小生成树； （3）哈夫曼编码； （6）多机调度问题。 【渴婴】 有一个非常渴的、但很聪明的小婴儿。她可能得到的东西包括：一杯水、一小罐牛奶、多罐其它不同种类的果汁……。即婴儿可能得到n种不同口味的饮料。 根据以前对这n种饮料的不同体验，这个婴儿知道其中某种饮料更适合自己的胃口，因此婴儿采用如下方法为每一种饮料赋予一个满意度值，即Si作为满意度赋予第i种饮料。 通常，这个婴儿都会尽量饮用具有最大满意度的饮料来最大限度地满足她解渴地需要，但不幸地是：她最满意地饮料有时并没有足够地量来满足这个婴儿解渴地需要。 【渴婴】 问题模型定义：设ai为第i种饮料的总量（假设以毫升为单位），而婴儿需要t毫升的饮料来解渴，那么需要饮用n种不同的饮料各多少才能满足婴儿解渴的需求呢？ 设各种饮料的满意度Si已知，令xi为将要饮用的第i种饮料的量，那么需要解决的问题是：求解一组实数向量xi（1≤i≤n），使得： 最大，并满足： 不过，若 ，则不可能找到问题的求解方案，因为即使喝光了所有的饮料也不能使婴儿解渴。 【找零钱】 一个小孩买糖，付了1美元，假设需要找给小孩67美分。而提供了如下数目不限的面值钱币：25美分(Quarters)、10美分(Dimes)、5美分(Nickels)及1美分(Pennies)。现在问题就是：保证找回67美分，且希望用最少数目的钱币找给小孩。 解：售货员每次加入一种钱币，并采用的贪婪准则是：每次选择的某种钱币面值尽可能大，所需张数尽可能少，但同时需保证解法的可行性（即，所给的零钱等于要找的零钱数，不多给不少给）。 贪心算法 形象模型 顾名思义，贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 4.1 活动安排问题 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。 4.1 活动安排问题 4.1 活动安排问题 4.1 活动安排问题 templateclass Type void GreedySelector(int n, Type s[], Type f[], bool A[]) { A[1]=true; int j=1; for (int i=2;i=n;i++) { if (s[i]=f[j]) { A[i]=true; j=i; } else A[i]=false; } } 4.1 活动安排问题 由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。 4.1 活动安排问题 例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下： 4.1 活动安排问题 算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。 阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。 4.1 活动安排问题 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最