通过范例学习贪心算法设计策略- 第16章贪心算法

《通过范例学习贪心算法设计策略- 第16章贪心算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1166章贪心算法ò理解贪心算法的概念ò掌握贪心算法的基本要素ò理解贪心算法与动态规划算法的差异ò通过范例学习贪心算法设计策略1算法导论16116.1活动安排问题ò当一个问题具有最优子结构性质时，可用动态规划法求解，但有时用贪心算法求解会更加的简单有效。ò顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整

2、体最优解。如单源最短路经问题，最小生成树问题等。在在些情一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。2算法导论16116.1活动安排问题ò设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间s和一个结束时间f,且s

3、j是相容的。也就是说，jj当s≥f或s≥f时，活动i与活动j相容。ijjiò问题：选出最大的相容活动子集合。3算法导论16116.1活动安排问题（用动态规划方法）ò步骤1：分析最优解的结构特征—构造子问题空间:S={a∈S:f≤s

4、的最优解A中包含活ijij动a，则在S最优解中的针对S的解A和针对S的解A也必定是最优的。kijikikkjkj（反证法即可！）—证明可以根据子问题的最优解来构造出原问题的最优解。一个非空子问题S的任意解中必包含了某项活动a，而S的任一最优解中都包含了其子问题ijkij实例S和S的最优解（根据最优子结构性质！）。因此，可以构造出S的最ikkjij大兼容子集。4算法导论16116.1活动安排问题ò步骤2：递归地定义最优解的值设c[i,j]为S中最大兼容子集中的活动数。当S=φ时，c[i,j]=0。对

5、ijij于一个非空子集S，如果a在S的最大兼容子集中被使用，则子问题ijkijS和S的最大兼容子集也被使用。从而：ikkjc[i,j]=c[i,k]+c[k,j]+1由于S的最大子集一定使用了i到j中的某个值k，通过检查所有可能的ijk值，就可以找到最好的一个。因此，c[i,j]的完整递归定义为：⎧⎪0Sij=φc[i,j]=⎨max{c[i,k]+c[k,j]+1}ٛSij≠φ⎪⎩i

6、一个直观想法是直接选择k的值，使得一个子问题为空，从而加快计算速度！这就导致了贪心算法！5算法导论16116.1活动安排问题（用贪心算法）ò贪心策略：对输入的活动以其完成时间的非减序排列，算法每次总是选择具有最早完成时间的相容活动加入最优解集中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[

7、i]130535688212f[i]45678910111213146算法导论16116.1活动安排问题7算法导论16116.1活动安排问题Recursive-Activity-Selector(s,f,i,j){①m←i+1;②whilem

8、1）数组s和f表示活动的开始和结束时间，n个输入活动已经按照活动结束时间进行单调递增顺序排序；2）算法②‾③目的是寻找S中最早结束的第一个活动，即找到与a兼容的第iji一个活动a，利用a与S的最优子集的并集构成S的最优子集；mmmjij3）时间复杂度O(n)。8算法导论16116.1活动安排问题òRecursive-Activity-Selector属于递归性贪心算法，它以对自己的递归调用的并操作结束，几乎就是“尾递归调用”，因此可以转化为迭代形式：Greedy-Activity-