vlambda博客
学习文章列表

活动安排问题来源于实际，无论任何与时间分配有关的问题都要考虑：如何安排来达到占用公共资源最少且花费时间最短的要求。

活动安排问题：设有n个活动的集合C={1,2,…,n}，其中每个活动都要求使用同一个资源(如会议室)，而在同一时间内只能有一个活动使用该资源。每个活动i都有要求使用该资源的起始时间si和结束时间fi，且s_i<f_i。如果选择了活动i使用会议室，那么它在半开区间［s_i, f_i)内占用该资源。如果［s_i, f_i)与［s_j,f_j)不相交，那么活动i与活动j是相容的。也就是说，当s_i≥f_j或s_j≥f_i时，活动i与活动j相容。活动安排问题要求在所给的活动集合中选出最大的相容活动子集，也即尽可能选择更多的活动来使用资源。

仔细审阅活动安排问题的已知条件和目标要求，我们得知： 

(1) n个活动的集合C={1,2,…,n}，即由活动编号组成的集合C。

(2) 活动i(i=1,2,…,n)的开始时间s_i。

(3) 活动i(i=1,2,…,n)的结束时间f_i。

(4) 活动i(i=1,2,…,n)使用资源的时间f_i-s_i。

(5) 活动i和活动j相容使用资源的条件：s_i≥f_j或s_j≥f_i，如图2-1所示。

■ 图2-1 活动i和活动j相容示意

6) 满足相容条件的活动子集都是活动安排问题的解，含有活动个数最多的子集就是最优解。

(7) 问题目标：找集合C的最大相容子集，即最优解。

由此，要想实现问题的目标，在满足相容的条件下，我们讨论以下三种贪心策略： 

(1) 开始时间早的活动优先安排。

(2) 结束时间早的活动优先安排。

(3) 使用时间短的活动优先安排。

那么，上述三种贪心策略哪个是最优的策略呢？我们看下面一个例子。

4个班级活动争用教室A，它们使用教室A的开始时间和结束时间如表2-1所示。

要求安排尽可能多的班级相容地使用教室A，该如何安排？

按照第一种贪心策略来安排，则1班使用教室A。

按照第二种贪心策略来安排，则2班先使用教室A，然后4班使用教室A。

按照第三种贪心策略来安排，则3班使用教室A。

通过简单对比，我们发现第二种贪心策略：结束时间早的活动优先安排是最佳策略。实际上，通过它们之间的关系：“结束时间=开始时间+使用时间”，我们可以推断：“开始时间越早，使用时间越短，则结束时间越早。”所以，结束时间早的活动优先安排的策略是最好的贪心策略。

设有10个活动等待安排，这些活动的开始时间和结束时间如表2-2所示，用贪心算法找出满足目标要求的活动集合。

第二步，在开始时间大于或等于4的活动集合中贪心选择，选3号活动，如表2-4所示，结束时间为7。

第三步，在开始时间大于或等于7的活动集合中贪心选择，选7号活动，如表2-5所示，结束时间为11。

第四步，在开始时间大于或等于11的活动集合中贪心选择，选10号活动，如表2-6所示，结束时间为14。此时，10号活动是最后一个位置的活动，算法结束。

该实例的解为(0,1,1,0,0,0,1,0,0,1)，即安排的活动集合为{2,3,7,10}。

参考书籍

精彩推荐