算法分析与设计-第四章 贪心算法课件.ppt

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

1、算法设计与分析第四章贪心算法本章主要知识点（8）：4.1活动安排问题4.2贪心算法的基本要素4.3最优装载4.4哈夫曼编码4.5单源最短路径4.6最小生成树4.7多机调度问题4.8贪心算法的理论基础2引言找零钱问题一出纳员支付一定数量的现金，假设他手中有各种面值的纸币和硬币，要求他用最少的货币数量支付规定的现金款。此问题的数学形式表述如下，设有n张（个）货币（包括纸币和硬币），用集合p表示，P={p1,p2,…,pn}，di是pi的货币单位。例如，如果pi是一角，则di=10。要数出一定数目的钱A，这就需要找出P的一个最小集合S，使得∑pidi=

2、A，S∈P，pi∈S。3引言4引言数钱的贪婪算法如下：出纳员并不是要真的要考虑各种数钱的方法，相反，他是按照货币单位从大到小的次序，数出需要支付的现金。例如，现在有10个硬币：5个1分，2个5分，2个角，1个两角。即{d1，d2，…，dn}={1，1，1，1，1，5，5，10，10，20}，要支付27美分。首先支付面值为20分的硬币，然后支付一个5分的硬币，最后支付2个1分的硬币，这就是贪婪策略。很显然，如果各种货币是按面值大小非升序排列的，则贪婪法求解的时间复杂度为O（n）。5引言贪婪算法一定能产生正确的解吗？答案是否定的。例如，在上题中引入一

3、个15分的硬币，去掉20分和两个5分的硬币，则{d1，d2，…，dn}={1，1，1，1，1，10，10，15}，现在要支付20分的现金。如果使用贪婪法求解，首先选择一个15分的硬币，然后选择5个1分的硬币。然而最优解为2个10分的硬币。由此可见，使用贪婪法求解问题，并不是每次都能得到最优解。6引言顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解

4、。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。74.1活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间f

5、i,且sivoidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=tr

6、ue;j=i;}elseA[i]=false;}}各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列9复杂性分析由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用

7、公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。10一个实例例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212f[i]456789101112131411图示算法greedySelector的计算过程如右图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。12说明若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合

8、A中。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确