贪心算法解决活动安排问题报告

《贪心算法解决活动安排问题报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、贪心算法解决活动安排问题金潇UsethegreedyalgorithmtosolvethearrangementforactivitiesJinxiao摘要：贪心算法在当前来看是最好的选择。是用利用启发式策略，在不从整体最优上加以考虑的情况下，来做出局部最优选择的一种算法。本文通过贪心算法的经典案例—活动安排问题入手，描述了贪心算法的基本思想和可能产生的问题，并简述该算法的好处和特点，最后给出几种经典的贪心算法。关键字：贪心算法、局部最优选择Abstract:Agreedyalgorithmisanyalgorithmthatfollowstheproblemsolvingheur

2、isticofmakingthelocallyoptimalchoiceateachstagewiththehopeoffindingtheglobaloptimum.Thisarticlethroughthegreedyalgorithmoftheclassiccase--activitiesproblems,describesthegreedyalgorithmthebasicideasandpossibleproblems,andbrieflyintroducestheadvantagesandcharacteristicsofthealgorithm,andfinallyg

3、ivesseveralclassicthegreedyalgorithm.Keywords：greedyalgorithm、thelocallyoptimalchoice1.引言：贪心法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进行，每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。其实，从"贪心"一词我们便可以看出，贪心算法总是做出在当前看来是最优的选择

4、，也就是说贪心算法并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心算法可以得到最优解或较优解。 许多可以用贪心算法求解的问题一般具有贪心选择性质和最优子结构，贪心选择性质是指所求问题的整体最优解包含着局部最优的选择，对于一个具体问题，关键是证明或验证每一步所作的贪心选择最终将导致问题的一个整体最优解。2.贪心算法的基本思想及存在问题2.1贪心法的基本思想：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。1.建立数学模型来描述问题。　　2.把求解的问题分

5、成若干个子问题。　　3.对每一子问题求解，得到子问题的局部最优解。　　4.把子问题的解局部最优解合成原来解问题的一个解。2.2该算法存在问题：1.不能保证求得的最后解是最佳的；2.不能用来求最大或最小解问题；3.只能求满足某些约束条件的可行解的范围。3.活动安排问题：3.1贪心算法解决活动安排问题活动安排问题是用贪心算法有效求解的一个很好例子。活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可提供一个简单、漂亮的方法，使尽可能多的活动能兼容的使用公共资源。设有n个活动的集合｛0，1，2，…，n-1｝，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能

6、使用这一资源。每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi，且starti

7、]≤end[1]≤…≤end[n-1]。算法中用集合a来存储所选择的活动。活动i被选择当且仅当a[i]的值为true。变量j记录最近一次选择的活动。设j是当前最近选择的活动，也就是所选择的活动中编号最大的活动，即：j=max{i

8、0≤i