活动安排问题

2014-09-02

这个问题一般使用贪心算法来解决。那么什么是贪心算法?下面是我从某篇文章中找到的一个解释:

贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的。

下面是对贪心的更通俗的解释:

所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

下面是贪心算法的流程:

Greedy(C)  //C是问题的输入集合即候选集合
{
    S={ };  //初始解集合为空集
    while (not solution(S))  //集合S没有构成问题的一个解
    {
       x=select(C);    //在候选集合C中做贪心选择
       if feasible(S, x)  //判断集合S中加入x后的解是否可行
       {
          S=S+{x};
          C=C-{x};
       }
    }
   return S;
}

对于这个流程笔者不做解释,因为可以依靠下面的活动安排问题来理解。


好了,下面描述一下活动安排问题:

一个会场可以承办活动,任意两个活动的所占用的时间段不能够重叠,即若活动A比活动B先开始,那么活动A必须在活动B开始之前结束(小于的关系),这样的两个活动也可以叫做是相容的。假设现在又很多人申请在同一天里使用该会场举行活动(这些人会给出使用的开始时间和结束时间),会场拥有者该如何选择才能使得这一天能够举行的活动最多?

下表中一共有12个活动这些活动按照结束时间的先后进行排序,第1行表示活动的编号,第2行表示活动的开始时间,第3行表示活动的结束时间。

表1 ↘

<!–i 1 2 3 4 5 6 7 8 9 10 11
s[i] 1 3 0 5 3 5 6 8 8 2 12
f[i] 4 5 6 7 8 9 10 11 12 13 14–>















































i1234567891011
s[i]130535688212
f[i]4567891011121314

实际上,贪心算法的主要工作是在证明上,即证明某个解决方法是合理的。现在我们要证明的是:对于一组按照结束时间的先后进行排序的活动集合A,其相容的最大子活动集合B的第一个活动可以是集合A的第一个活动。

证明很简单,假如在表1中我们找到的相容的最大子活动集合为

活动2,活动7,活动11

很明显,活动1的结束时间小于活动2的结束时间,所以

活动1,活动7,活动11

也是相容的最大子活动集合。在实际操作中,更倾向于选择活动1而非活动2,因为选择活动1后剩下的活动时间留下更多一些。

既然如此,我们选择活动1。从表1中去掉活动1,由于活动2、3和活动1的时间有交集,也去掉。现在剩下活动4~11,基于上面的证明,认为活动4是最好的选择(贪心选择),依次类推。

参考

五大常用算法之三:贪心算法
0021算法笔记——【贪心算法】贪心算法与活动安排问题

( 完 )