活动安排问题—贪心算法经典例子

活动安排问题是解决需要共享公共资源的一系列活动的高效安排问题，以在限定资源的前提下尽可能多地开展活动。该问题的分析在运筹学、管理学，以及诸多社会实践中均有实际意义并被广泛应用。

1. 问题描述

学校的礼堂经常开展各类活动，这些活动的开始和结束时间各异，且可能出现重叠，为了开展尽可能多的活动，要怎么安排？例如，最近，学校有开学典礼、课外讲座、话剧演出、音乐会、芭蕾舞演出和教职工会议等一系列活动需要在礼堂举行，具体活动信息如表 1 所示，怎样安排才能使尽可能多的活动得以开展呢？

表1：活动信息
活动	开学典礼	课外讲座	话剧演岀	音乐会	芭蕾舞演出	教职工会议
开始时间(s)	1	3	0	5	3	7
结束时间(f)	3	4	4	7	6	8

为了解决上述问题，我们可以考虑使用贪心算法。目标是在固定的教室中尽量多地安排活动，可以考虑的贪心策略有总是选择最早开始的、总是选择时间最短的、总是选择与其他活动冲突最少的、总是选择结束时间最早的。

在这里，我们用总是选择结束时间最早的活动这一选择方案作为解题的贪心策略，后面的证明部分会验证该策略符合贪心选择性质和最优子结构性质。感兴趣的读者可以尝试验证其他可选的贪心策略是否符合贪心选择性质和最优子结构性质，提前告诉大家，这里面有的方案是不能得到最优解的，自己来探寻答案吧。

言归正传，我们来验证总是选择结束时间最早的活动作为贪心策略的贪心选择性质和最优子结构性质。

设 S_ij为包含所有待安排活动的一个集合，其中的活动开始时间均晚于时间节点 i，结束时间均早于时间节点 j。定义最大兼容活动子集 A_ij为包含 S_ij中相容（互不冲突）的活动数量最多的集合，且用 a 来表示 S_ij中的活动，用 |A| 表示集合 A 中的元素数量。

1) 首先证明最优子结构性质

要证明贪心策略满足最优子结构性质，即需证明若 A_ij为 S_ij的最大兼容活动子集，存在 A_ij中的活动 a_k，将 A_ij分解为 A_ik、a_k和 A_kj三部分，使 A_ij包含 S_ik和 S_kj的最优解。

用反证法证明。假设存在 S_kj的兼容活动子集 A_kj'，满足 |A_kj'|>|A_kj|，即 A_kj' 中包含的活动数量多于 A_kj，则可将 A_kj' 作为 S_kj的最优解，成为 S_ij最优解的一部分，则满足 |A_ik|+|A_kj'|>|A_ik|+|A_kj|，即存在比 A_ij更优的最大兼容活动子集，这与条件相矛盾，因此假设不成立。

2) 接着证明贪心选择性质

根据每次优先选择最早结束活动的贪心策略，只要证明通过该策略获得的局部最优解可以构造出全局最优解，即可说明该贪心策略有效，具备贪心选择性质。

3) 在此，我们证明若 a_m为 S_k中结束最早的活动，则 a_m一定在 S_k的某个最大兼容活动子集中

设 A_k为 S_k的一个最大兼容活动子集，a_k为 A_k中结束时间最早的活动，则若 a_k=a_m，a_m在 S_k的最大兼容活动子集 A_k中，原命题成立。否则，因为 a_m为 S_k中结束最早的活动，可以设 A_k'=A_k-{a_k}+{a_m}，即 A_k' 为在 A_k集合中用 a_m 替换 a_k所得到的新集合。

由于 a_m是 S_k中结束时间最早的活动，因此在 A_k' 中不会存在与 a_m发生冲突的活动，即 A_k' 也是 S_k的一个最大兼容活动子集。综上， a_m一定在 S_k的某个最大兼容活动子集中，原命题得证。

证明了总是优先选择最早结束的活动这一贪心策略同时具备最优子结构性质和贪心选择性质，说明应用该策略进行贪心选择，可以获得活动安排问题的全局最优解。

2. 参考实现

通过比较下一个活动的开始时间与上一个活动的结束时间的大小关系，确定这两个活动是否是相容的，如果开始时间大于结束时间则相容，反之不相容。

代码如下：

# 对结束时间进行排序，同时得到对应的开始时间的list
def bubble_sort(s,f):
    for i in range(len(f)):
        for j in range(0,len(f)-i-1):
            if f[j] > f[j+1]:
                f[j], f[j+1] = f[j+1],f[j]
                s[j],s[j+1] = s[j+1],s[j]
    return s,f
def greedy_activity(s,f,n):
    a = [True for x in range(n)]
    #初始选择第一个活动
    j = 0
    for i in range(1,n):
        #如果下一个活动的开始时间大于等于上个活动的结束时间
        if s[i] >= f[j]:
        a[i] = True
        j = i
    else:
        a[i] = False
    return a
#通过输入多组起始时间进行验证
n=int(input("输入活动数量和起始时间（数量和活动用回车分隔，活动之间用空格分隔）。例如：5（回车）(1,5) (2,6) (2,8) (3,9) (5,10)："))
arr = input().split()
s = []
f = []
    for ar in arr:
        ar = ar[1:-1]
        start = int(ar.split(',')[0])
        end = int(ar.split(',')[1])
        s.append(start)
        f.append(end)
s,f = bubble_sort(s,f)
G = greedy_activity(s,f,n)
res = []
for t in range(len(G)):
    if G[t]:
        res.append('({},{})'.format(s[t],f[t]))
print(' '.join(res))

运行代码：

输入活动数量和起始时间（数量和活动用回车分隔，活动之间用空格分隔）。例如：5（回车）(1,5) (2,6) (2,8) (3,9) (5,10)：
5
(1,5) (2,6) (2,8) (3,9) (5,10)

输出：

(1,5) (5,10)

活动安排问题—贪心算法经典例子

1. 问题描述

2. 参考实现

相关文章