活动安排问题—贪心算法经典例子
活动安排问题是解决需要共享公共资源的一系列活动的高效安排问题,以在限定资源的前提下尽可能多地开展活动。该问题的分析在运筹学、管理学,以及诸多社会实践中均有实际意义并被广泛应用。
为了解决上述问题,我们可以考虑使用贪心算法。目标是在固定的教室中尽量多地安排活动,可以考虑的贪心策略有总是选择最早开始的、总是选择时间最短的、总是选择与其他活动冲突最少的、总是选择结束时间最早的。
在这里,我们用总是选择结束时间最早的活动这一选择方案作为解题的贪心策略,后面的证明部分会验证该策略符合贪心选择性质和最优子结构性质。感兴趣的读者可以尝试验证其他可选的贪心策略是否符合贪心选择性质和最优子结构性质,提前告诉大家,这里面有的方案是不能得到最优解的,自己来探寻答案吧。
言归正传,我们来验证总是选择结束时间最早的活动作为贪心策略的贪心选择性质和最优子结构性质。
设 Sij 为包含所有待安排活动的一个集合,其中的活动开始时间均晚于时间节点 i,结束时间均早于时间节点 j。定义最大兼容活动子集 Aij 为包含 Sij 中相容(互不冲突)的活动数量最多的集合,且用 a 来表示 Sij 中的活动,用 |A| 表示集合 A 中的元素数量。
1) 首先证明最优子结构性质
要证明贪心策略满足最优子结构性质,即需证明若 Aij 为 Sij 的最大兼容活动子集,存在 Aij 中的活动 ak,将 Aij 分解为 Aik、ak 和 Akj 三部分,使 Aij 包含 Sik 和 Skj 的最优解。
用反证法证明。假设存在 Skj 的兼容活动子集 Akj',满足 |Akj'|>|Akj|,即 Akj' 中包含的活动数量多于 Akj,则可将 Akj' 作为 Skj 的最优解,成为 Sij 最优解的一部分,则满足 |Aik|+|Akj'|>|Aik|+|Akj|,即存在比 Aij 更优的最大兼容活动子集,这与条件相矛盾,因此假设不成立。
2) 接着证明贪心选择性质
根据每次优先选择最早结束活动的贪心策略,只要证明通过该策略获得的局部最优解可以构造出全局最优解,即可说明该贪心策略有效,具备贪心选择性质。
3) 在此,我们证明若 am 为 Sk 中结束最早的活动,则 am 一定在 Sk 的某个最大兼容活动子集中
设 Ak 为 Sk 的一个最大兼容活动子集,ak 为 Ak 中结束时间最早的活动,则若 ak=am,am 在 Sk 的最大兼容活动子集 Ak 中,原命题成立。否则,因为 am 为 Sk 中结束最早的活动,可以设 Ak'=Ak-{ak}+{am},即 Ak' 为在 Ak 集合中用 am 替换 ak 所得到的新集合。
由于 am 是 Sk 中结束时间最早的活动,因此在 Ak' 中不会存在与 am 发生冲突的活动,即 Ak' 也是 Sk 的一个最大兼容活动子集。综上, am 一定在 Sk 的某个最大兼容活动子集中,原命题得证。
证明了总是优先选择最早结束的活动这一贪心策略同时具备最优子结构性质和贪心选择性质,说明应用该策略进行贪心选择,可以获得活动安排问题的全局最优解。
代码如下:
1. 问题描述
学校的礼堂经常开展各类活动,这些活动的开始和结束时间各异,且可能出现重叠,为了开展尽可能多的活动,要怎么安排?例如,最近,学校有开学典礼、课外讲座、话剧演出、音乐会、芭蕾舞演出和教职工会议等一系列活动需要在礼堂举行,具体活动信息如表 1 所示,怎样安排才能使尽可能多的活动得以开展呢?活动 | 开学典礼 | 课外讲座 | 话剧演岀 | 音乐会 | 芭蕾舞演出 | 教职工会议 |
---|---|---|---|---|---|---|
开始时间(s) | 1 | 3 | 0 | 5 | 3 | 7 |
结束时间(f) | 3 | 4 | 4 | 7 | 6 | 8 |
为了解决上述问题,我们可以考虑使用贪心算法。目标是在固定的教室中尽量多地安排活动,可以考虑的贪心策略有总是选择最早开始的、总是选择时间最短的、总是选择与其他活动冲突最少的、总是选择结束时间最早的。
在这里,我们用总是选择结束时间最早的活动这一选择方案作为解题的贪心策略,后面的证明部分会验证该策略符合贪心选择性质和最优子结构性质。感兴趣的读者可以尝试验证其他可选的贪心策略是否符合贪心选择性质和最优子结构性质,提前告诉大家,这里面有的方案是不能得到最优解的,自己来探寻答案吧。
言归正传,我们来验证总是选择结束时间最早的活动作为贪心策略的贪心选择性质和最优子结构性质。
设 Sij 为包含所有待安排活动的一个集合,其中的活动开始时间均晚于时间节点 i,结束时间均早于时间节点 j。定义最大兼容活动子集 Aij 为包含 Sij 中相容(互不冲突)的活动数量最多的集合,且用 a 来表示 Sij 中的活动,用 |A| 表示集合 A 中的元素数量。
1) 首先证明最优子结构性质
要证明贪心策略满足最优子结构性质,即需证明若 Aij 为 Sij 的最大兼容活动子集,存在 Aij 中的活动 ak,将 Aij 分解为 Aik、ak 和 Akj 三部分,使 Aij 包含 Sik 和 Skj 的最优解。
用反证法证明。假设存在 Skj 的兼容活动子集 Akj',满足 |Akj'|>|Akj|,即 Akj' 中包含的活动数量多于 Akj,则可将 Akj' 作为 Skj 的最优解,成为 Sij 最优解的一部分,则满足 |Aik|+|Akj'|>|Aik|+|Akj|,即存在比 Aij 更优的最大兼容活动子集,这与条件相矛盾,因此假设不成立。
2) 接着证明贪心选择性质
根据每次优先选择最早结束活动的贪心策略,只要证明通过该策略获得的局部最优解可以构造出全局最优解,即可说明该贪心策略有效,具备贪心选择性质。
3) 在此,我们证明若 am 为 Sk 中结束最早的活动,则 am 一定在 Sk 的某个最大兼容活动子集中
设 Ak 为 Sk 的一个最大兼容活动子集,ak 为 Ak 中结束时间最早的活动,则若 ak=am,am 在 Sk 的最大兼容活动子集 Ak 中,原命题成立。否则,因为 am 为 Sk 中结束最早的活动,可以设 Ak'=Ak-{ak}+{am},即 Ak' 为在 Ak 集合中用 am 替换 ak 所得到的新集合。
由于 am 是 Sk 中结束时间最早的活动,因此在 Ak' 中不会存在与 am 发生冲突的活动,即 Ak' 也是 Sk 的一个最大兼容活动子集。综上, am 一定在 Sk 的某个最大兼容活动子集中,原命题得证。
证明了总是优先选择最早结束的活动这一贪心策略同时具备最优子结构性质和贪心选择性质,说明应用该策略进行贪心选择,可以获得活动安排问题的全局最优解。
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)