贪心算法在活动安排中的应用研究

刘雷 张永康

摘 要：本文对活动安排问题进行了讨论，提出了不同的活动安排策略，并证明了贪心算法在解决该问题的优越性，并通过具体的例子进行了验证，并给出该算法及对应的时间复杂度分析，从而为相关问题的解决给出了一种策略参考。

关键词：活动安排问题；贪心算法；局部最优解

1 引言

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，该问题要求高效地安排一系列争用某一公共资源的活动。尽管如今计算机计算速度已经十分的快，但是对于近年来指数级增长的需要处理的数据，计算机计算速度的增长还显得远远不够。因此高效的算法对于大数据的处理显得格外重要。而贪心算法本身的特点为解决活动安排问题提供了一种优秀的解决方案。

2 方法

2.1 贪心算法及其特点介绍

贪心算法（又称贪婪算法）是指从当前看来的角度进行分析，只是做出对当前来说最好的决策，但并不会考虑过去的决策以及对未来的影响，是否当前的决策会导致未来得到最优解，这样通过每次得到当前的最优解，最终求得最终的解决方案，但是该方案不一定是全局的最优解决方案，但是一定是比较接近最优解。

贪心算法的求解过程：1）从某个初始的解出发进行问题求解。2）采用循环的方法，每次向最终的求解方向前进一步，不断求出当前的最优解，直到最终的状态。3）新的解建立在原来的解基础上，最终得到最终解。

2.2 活动安排问题求解策略

活动安排问题可以描述为有n个活动申请使用同一个礼堂，每个活动都有自己的开始活动时间和最终的结束时间。希望都够得到一种安排方案使得尽可能多的活动被安排，但是彼此不会发生冲突，即每次礼堂只能有一个活动被安排。

假设m={1，2，...，s}表示被安排的活动集合，其中Bi表示活动i的开始时间，而Di表示活动i的结束时间，要保证任意两个活动i，j相容，即保证DiDj，列出一下三种策略对问题进行求解：

策略一：尽早占用的活动先安排。

把所有活动的开始时间进行排序，数值小的先安排，并且保证被安排的活动彼此之前是相容的，最终得到一个活动安排集合。

策略二：根据时间占用多少来安排活动。

每个活动都有自己的时长，根据它的时长来进行安排。先对时长进行排序，时长小的活动先安排，按照这种策略不断挑选活动，同时保证活动之前彼此是相容的，最终得到一个活动安排集合。

策略三：根据活动结束时间来安排。

每个活动都有自己的结束时间，因此根据结束时间来进行排序，结束时间早的优先安排，都是保证彼此之间的相容性，最终得到一个活动安排集合。

以上三种策略可作为活动安排问题的求解方案，但是前两种在某些情况具有较大的局限性，策略一反例：S={1， 2， 3}，a1=<0， 20>， a2=<2， 5>，a3=<8， 15>。

策略二反例S={1， 2， 3}，a1=<0， 8>， a2=<7， 9>， a3=<8， 15>。但策略三因输入的活动以其完成时间的非减序排列，该方案可以使得每次都是最早结束的活动被安排，使得每次用来安排其他活动的剩余时间最长。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

2.3 算法实现

该算法的核心代码如下：

template

void GreedySelector（int n， Type s[]， Type f[]， bool A[]） {

A[1] = true；

int j = 1；

for （int i=2；i<=n；i++） {

if （s[i]>=f[j]） {

A[i]=true；

j=i；

}

else A[i]=false；

}

}

整个算法的时间复杂度为O（n），预排序时间复杂度为O（nlogn） ，因此该算法具有较低的时间复杂度。低复杂度为大数据计算提供了算法保障。

3 案例应用

设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：

i 1 2 3 4 5 6 7 8 9 10 11

S[i] 1 3 0 5 3 5 6 6 8 2 12

F[i] 4 5 6 7 8 9 10 11 12 13 14

按照策略一可以安排第3，7，11三個活动，策略二可以安排2，4，11四个活动，策略三可以安排1，4，8，11，可见如果贪心的选择结束时间早的活动先安排，可以使安排的相容活动个数最多。

4 总结

本文对活动安排问题进行了探讨，论证了贪心算法在求解该问题的优越性，低复杂度为求解数据较大的问题提供了算法支持。但贪心算法并不能对所有问题都得到整体最优解，因此对于不同的问题，贪心算法是否能取得最优解还需进一步探讨。

参考文献

[1]苏方方，张金玲.贪心算法解决活动安排问题研究[J].软件导刊，2011，10（12）：43-44.

[2]刘文强，周波，马海峰， 等.算法分析与设计课程中活动安排问题的教学探讨[J].高教学刊，2018，（20）：96-98.

[3]王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2007.