内容发布更新时间 : 2024/12/23 5:07:12星期一 下面是文章的全部内容请认真阅读。
活动安排问题
问题：设有n个活动的集合E={1,2,...,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间Fi，且Si
证明：这个问题可以使用贪心算法进行求解。其实这个问题的关键并不是如何用贪心算法求解，而是如何证明这个问题可以用贪心算法求解。鉴于证明的复杂性，还是不在此讨论证明问题。其实贪心算法问题的证明无非都是用数学归纳法证明，不错就是那个传说中万能证明法，数学归纳法。还是直接讨论实现过程吧。
实现：首先将活动按照活动的结束时间非递减：F1<=F2<=...<=Fn排序。如果所给的活动未排序，则先将活动按此序排列，时间复杂度一般为O(nlogn)可解决。以下是解决问题的算法。
1 //贪心算法-活动安排的实现 2
3 #include \ 4 #include \ 5
6 template
7 void GreedySelector(int n,Type s[],Type f[],bool A[]) 8 {
9 A[0]=1; //第一个直接选取 10 int j=0;
11 for(int i=1;i 13 if(s[i]>=f[j]){A[i]=true;j=i;} //如果第i+1的活动的开始时间大于或等于第i个活动的结束时间，则标记该活动 14 else A[i]=false; 15 } 16 } 17 18 int _tmain(int argc, _TCHAR* argv[]) 19 { 20 //初始化数据 21 int n=3; 22 int s[3]={1,2,4}; //开始时间 23 int f[3]={3,3,5}; //结束时间 24 bool A[3]={0,0,0}; //数组A用于标记是否选择活动，1表示选择，0表示不选择 25 26 GreedySelector 29 printf(\30 } 31 } 该算法的贪心选择的意义是使剩余的可安排的时间段极大化，以便安排尽可能多的相容活动。也就是说，每次选择完了之后，保证这次的选择之后留下的时间是最多的。 时间复杂度：GreedySelector算法效率极高。当输入的数据是已经按照结束时间非递减排序好的时候，算法只需要O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。 总结 贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围。贪心算法所作的选择依赖于以往所作过的选择，但决不依赖于将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。对一个问题可以同时用几种方法解决，贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。与回溯法、动态规划法等比较，它的适用区域相对狭窄许多。总之，如果一个贪心解决方案存在，就可以使用它。 参考文献 [1] 严蔚敏,吴伟民.数据结构(c语言版)[M].北京:清华大学出版社,1997． [2] M.H.ALSUWAIYEL.算法设计技巧与分析[M].北京:电子工业出版社,2004． [3] 常友渠.贪心算法的探讨与研究[M].重庆电力高等专科学报,第13卷，第13期，2008.9. [4]龚雄兴,堆与贪心算法[M],湖北襄樊学院，2003. [5] 张洁,朱莉娟.贪心算法与动态规划的比较[M].新乡师范高等专科科学学报,第19卷，第五期，2005.9. [6] 殷建平.关于贪心算法的正确性证明[M].江西师范大学学报（自然科学版）,第22卷增刊,1998.10.