贪心算法解决活动安排问题报告(共4页).doc

《贪心算法解决活动安排问题报告(共4页).doc》由会员分享，可在线阅读，更多相关《贪心算法解决活动安排问题报告(共4页).doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上贪心算法解决活动安排问题金 潇Use the greedy algorithm to solve the arrangement for activities Jinxiao摘要：贪心算法在当前来看是最好的选择。是用利用启发式策略，在不从整体最优上加以考虑的情况下，来做出局部最优选择的一种算法。本文通过贪心算法的经典案例活动安排问题入手，描述了贪心算法的基本思想和可能产生的问题，并简述该算法的好处和特点，最后给出几种经典的贪心算法。关键字：贪心算法、局部最优选择Abstract:A greedy algorithm is any algorithm that foll

2、ows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum. This article through the greedy algorithm of the classic case-activities problems, describes the greedy algorithm the basic ideas and possible problems, and briefly intro

3、duces the advantages and characteristics of the algorithm, and finally gives several classic the greedy algorithm. Keywords：greedy algorithm、the locally optimal choice 1.引言： 贪心法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进行，每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完

4、，或者不能再添加为止。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。其实，从贪心一词我们便可以看出，贪心算法总是做出在当前看来是最优的选择，也就是说贪心算法并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心算法可以得到最优解或较优解。许多可以用贪心算法求解的问题一般具有贪心选择性质和最优子结构，贪心选择性质是指所求问题的整体最优解包含着局部最优的选择，对于一个具体问题，关键是证明或验证每一步所作的贪心选择最终将导致问题的一个整体最优解。2.贪心算法的基本思想及存在问题2.1 贪心法的基本思想：从问题的某一个初始解出发逐步逼近

5、给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。2.2 该算法存在问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。3.活动安排问题：3.1 贪心算法解决活动安排问题活动安排问题是用贪心算法有效求解的一个很好例子。活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可提供一个简单、漂亮的方法，使尽可能多的活动能兼容

6、的使用公共资源。设有n个活动的集合0，1，2，n-1，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi，且startiendi。如选择了活动i，则它在半开时间区间starti,endi）内占用资源。若区间starti,endi)与区间startj,endj)不相交，称活动i与活动j是相容的。也就是说，当startjendi或startiendj时，活动i与活动j相容。活动安排问题就是在所给的活动集合中选出最大的相容子活动集合。在下面所给出的解活动安排问题的贪心算法中，设各活动的起始时

7、间和结束时间存储于数组start和end中，不失一般性，假设结束时间安非递减排列：end0end1 endn-1。算法中用集合a来存储所选择的活动。活动i被选择当且仅当ai的值为true。变量j记录最近一次选择的活动。设j是当前最近选择的活动，也就是所选择的活动中编号最大的活动，即：j=maxi|0i0，则我们设b=a-k0。由于end0 endk,且a中活动是互为相容的，故b中的活动也是互为相容的。又由于b中的活动个数与a中活动个数相同，且a是最优的，故b也是最优的。也就是说b是一个以贪心选择活动0开始的最优活动安排。因此，证明了总存在一个以贪心选择开始的最优活动安排方案，也就是算法具有贪心

8、选择性质。4.贪心算法解决活动安排问题的好处运用该算法解决活动安排问题的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。5.几种经典的贪心算法1.库鲁斯卡尔（Kruskal）算法2.普林（Prim）算法3.戴克斯德拉（Dijkstra）算法6.结束语贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法，本文通过活动安排问题这一经典案例对贪心算法进行简要分析，利用图表给出较直观实例，得到了贪心算法是一种高效算法的结论。7参考文献数据结构与算法（c+版） 清华大学出版社 唐宁九 游洪跃等主编专心-专注-专业