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

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

2、blem 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 introduces the a

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

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

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

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

7、，不失一般性，假设结束时间安非递减排列：end0 Wend1 WW endn-1。算法中用集合a来存储所选择的活动。活动i被选择当且仅当ai的值为true。 变量j记录最近一次选择的活动。设j是当前最近选择的活动，也就是所选择的活动中编号 最大的活动，即：j=maxi|0Wi0，则我们设b=a-kU0。由于end0 Wendk，且a中活动是互为相容的， 故b中的活动也是互为相容的。又由于b中的活动个数与a中活动个数相同，且a是最优的， 故b也是最优的。也就是说b是一个以贪心选择活动0开始的最优活动安排。因此，证明了 总存在一个以贪心选择开始的最优活动安排方案，也就是算法具有贪心选择性质。4贪心算法解决活动安排问题的好处运用该算法解决活动安排问题的效率极高。当输入的活动已按结束时间的非减序排列，算法 只需O（n）的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动 未按非减序排列，可以用O（nlogn）的时间重排。几种经典的贪心算法库鲁斯卡尔（Kruskal）算法普林（Prim）算法戴克斯德拉（Dijkstra）算法结束语贪心策略是指从问题的初始状态出发，通过若干次