算法设计与分析第4章

《算法设计与分析第4章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章贪心算法1学习要点理解贪心算法的概念。掌握贪心算法的基本要素（1）最优子结构性质（2）贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论通过应用范例学习贪心设计策略。（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最小生成树；2假设有四种硬币，它们的面值分别为2.5角、1角、0.5角和0.1角。现在要找给某顾客6.3角。最优解：2个2.5角，1个1角以及3个0.1角。我们下意识地使用了这样的找硬币算法：1）首先选出一个面值不超过6.3角的最大硬币，即2.5角；2）

2、然后从6.3角中减去2.5角，剩下3.8角；再选出一个面值不超过三角八分的最大硬币，即又一个2.5角，如此一直做下去。这个找硬币的方法实际上就是贪心算法。31）贪心算法总是作出在当前看来最好的选择，所作出的选择只是在某种意义上的局部最优选择。它能产生整体最优解。如单源最短路经问题，最小生成树问题等。2）贪心算法希望得到的最终结果也是整体最优的。虽然贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。44.1活动安排问题设有n个活动要求使用同一资源。而在同一时间内只有一个活动能使用这一资源。1）每个活动i都有一个起

3、始时间si和一个结束时间fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。2）若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。3）活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。5要尽可能安排多的活动每次选择具有最早开始时间的活动？每次安排后剩下尽可能多的空余时间每次选择具有最早结束时间的活动？4.1活动安排问题例：设待安排的11个活动的开始时间和结束时间按结束时间的非

4、减序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。74.1活动安排问题templatevoidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;//所有活动按结束时间非减序intj=1;//j中存放最近加入集合A中的活动for(inti=2;i<=n;i++){//选择

5、最早完成的相容活动if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}下面给出解活动安排问题的贪心算法GreedySelector:8算法greedySelector的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。91）由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留

6、下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。2）算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。104.1活动安排问题正确性证明贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法总能求得最优解。数学归纳法证明思路：1）总存在一个最优解是以贪心选择策略开始（贪心选择性质）；2）

7、接下来，每一步都可利用贪心策略求得对应子问题的最优解（最优子结构性质）；11贪心算法的数学归纳证明1）首先证明：总存在一个最优解是以贪心选择开始。设A是该问题的一个最优解，A也是按活动结束时间非减序，A中第一个活动为k。A：当k==1,那么A就是一个以贪心选择开始的最优解B：当k>1，设B=(A-{k})U{1},由于A中活动是相容的，并且f1<=fk(活动非减序),因此，B也是相容的，所以B也是最优的。122）然后证明，在贪心选择之后，即选择了活动1之后的原问题最优解A，有A’=A-{1}则是剩余活动E’={si>f1

8、}安排子问题的最优解。反证法：如果子问题存在一个解B’比A’更优，即B’中安排的活动数目更多，那么B’+{1}则将优于原问题最优解A，所以矛盾。134.2贪心算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题