活动安排问题.pptVIP

问题描述 设有n个活动的集合E={1,2，……，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且sifi。如果选择了活动i，则它在时间区间[si,fi]内占用资源。若区间[si,fi]与区间[sj,fj]不相交，则称活动i与活动j是相容的。也就是说，当si=fj或者sj=fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。 在VC 6.0环境下测试贪心算法的性能 。实验过程如下： * * * * 运用贪心算法解决活动安排问题 Using the greedy algorithm to solve the problem of activity arrangement 1 内容提要 2 3 实验及结果 4 实验总结 算法思想及分析 问题描述 问题描述 返回 贪心算法 算法思想及分析 活动安排运用贪心算法的思路为，尽可能多的使更多的事件得到资源的安排。按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。实现方法是在满足相容的条件下，使结束时间靠前的活动得到资源，这样就为后续时间留下更多的安排时间，以使更多的活动得到安排。 贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。 算法思想及分析 由于贪心算法解决安排问题要考虑么个活动的结束时间，所以先将活动按照结束时间长短进行递增排序。本贪心算法在处理非减序排列活动队列时可以达到极高的效率。 待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下： 贪心算法实现 表1 安排活动非减序时间表 算法思想及分析 贪心算法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。 贪心算法实现 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。 图-1 贪心算法的计算过程图 实验仿真过程 实验及其结果 表-2 实验输入输出参数设置 图-2 运行结果 O(n) 贪心算法 O(nlogn) 减序算法 O(n2) 末减序排列算法 时间复杂度 比较项 算法名称 实验结果分析 * * * *