《贪心算法解决活动安排问题报告(共4页)》由会员分享，可在线阅读，更多相关《贪心算法解决活动安排问题报告(共4页)（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，且starti<endi。如选择了活动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|0i<n,ai=true算法开始选择活动0，并将j初始化为0.然后依次检查活动i是否与当前已选择的所有活动相容。如相容则安排活动i，否则不安排活动i，再继续检查下一活动与所有已选择活动的相容性。由于k是当前已选择活动的最大结束时间，故活动i与当前所有选
8、择活动相容的充分且必要条件是其开始时间starti不早于最近选择的活动j的结束时间endj，即starti endj。若活动i满足此条件，则活动i被选择，因而取代活动j的位置。由于活动是以其完成时间的非减序排列的，所以算法每次总是选择具有最早完成时间的相容活动i。这种方法选择相容活动就使剩余活动留下尽可能多的时间。也就是该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。3.2 活动安排实例设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011Starti130535688212Endi4567891011121314算法的
9、计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合的活动，而空白长条表示的活动是当前正在检查相容性的活动。若被检查的活动i的开始时间starti小于最近选择的活动j的结束时间endj，则不选择活动i，否则选择活动i加入集合中。3.3 活动安排问题证明贪心算法获得整体最优解贪心算法并不总能求得问题的整体最优解，但对于活动安排问题，可以证明贪心算法能求得的整体最优解，下面将给与证明：设E=0，1，2，n-1为所给的活动集合。由于E中活动安排安结束时间的非减序排列，所以活动0具有最早完成时间。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动0.设a是
10、所给的活动安排问题的一个最优解，且a中活动也按结束时间非减序排列，a中的第一个活动是活动k。如k=0，则a就是一个以贪心选择开始的最优解。若k>0，则我们设b=a-k0。由于end0 endk,且a中活动是互为相容的，故b中的活动也是互为相容的。又由于b中的活动个数与a中活动个数相同，且a是最优的，故b也是最优的。也就是说b是一个以贪心选择活动0开始的最优活动安排。因此，证明了总存在一个以贪心选择开始的最优活动安排方案，也就是算法具有贪心选择性质。4.贪心算法解决活动安排问题的好处运用该算法解决活动安排问题的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。5.几种经典的贪心算法1.库鲁斯卡尔（Kruskal）算法2.普林（Prim）算法3.戴克斯德拉（Dijkstra）算法6.结束语 贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法，本文通过活动安排问题这一经典案例对贪心算法进行简要分析，利用图表给出较直观实例，得到了贪心算法是一种高效算法的结论。7参考文献数据结构与算法（c+版） 清华大学出版社 唐宁九 游洪跃等主编专心-专注-专业
贪心算法解决活动安排问题报告(共4页)
