活动安排问题

#算法#

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 ↘

实际上，贪心算法的主要工作是在证明上，即证明某个解决方法是合理的。现在我们要证明的是：对于一组按照结束时间的先后进行排序的活动集合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算法笔记——【贪心算法】贪心算法与活动安排问题

( 本文完 )