贪心算法之活动选择问题

vlambda
2021-07-20

贪心算法之活动选择问题

"贪心算法之活动选择问题"

今天咱们开始贪心算法的讲解了, 对比动态规划, 贪心算法相对容易.

概述

求解最优化问题的算法通常需要经过一系列的步骤, 在每个步骤都面临多种选择. 对于许多最优化问题, 用动态规划算法有些"大材小用"了, 可以用更简单、更高效的贪心算法求解. 贪心算法每一步都做出当前看起来最佳的选择即总是做出局部最优的选择. 希望这样的选择能导致全局最优解.

贪心算法并不保证得到最优解, 但有些问题可以求出最优解.

活动选择问题

活动选择问题: 假定有一个n个活动的集合S={a1, a2,...,an}, 这些活动使用同一个资源(如一个阶梯教室), 而这个资源在某个时刻只能供一个活动使用. 每个活动ai都有一个开始时间si和一个结束时间fi, 0<=si<fi<∞. 若被选中, 任务ai发生在半开时间区间[si, fi). 若活动ai和aj满足[si, fi)和[sj, fj)不重叠, 则称它们是兼容的. 活动选择问题中, 我们希望选出一个最大兼容活动集. 假定活动已按结束时间的单调递增顺序排序:

f1 <= f2 <= f3 <=...<= f(n-1) <= fn. 比如有下面活动集合S:

i	1	2	3	4	5	6	7	8	9	10	11
si	1	3	0	5	3	5	6	8	8	2	12
fi	4	5	6	7	9	9	10	11	12	14	16

对于这个例子, 子集{a3, a9, a11}由相互兼容的活动组成. 但它不是一个最大集, 因为子集{a1, a4, a8, a11}更大, 为一个最大兼容活动子集, 另一个最大子集是{a2, a4, a9, a11}.

下面我们分几步来解决这个问题.

活动选择问题的最优子结构

我们容易验证活动选择问题具有最优子结构性质. 令S(ij)表示在ai结束之后开始的, 且在aj开始之前结束的那些活动的集合. 假定我们希望求Sij的一个最大的相互兼容的活动子集, 进一步假定A(ij)就是这样的子集, 包含活动ak. 由于最优解包含活动ak, 我们得到两个子问题: 寻找S(ik)中的兼容活动(在ai结束之后开始并且ak开始之前结束的那些活动)以及寻找S(kj)中的兼容活动(在ak结束之后开始且在aj开始之前结束的那些活动). 令A(ik) = A(ij)∩S(ik), 这样A(ik)包含A(ij)中那些在ak开始之前结束的活动. A(kj)包含A(ij)中那些在ak结束之后开始的活动.

因此我们有A(ij) = A(ik)∪{ak}∪A(kj), 而且S(ij)中最大兼容任务子集A(ij)包含

|A(ij)| = |A(ik)| + |A(kj)| + 1个活动.

这样刻画活动选择问题的最优子结构, 意味着我们可以用动态规划方法解决此问题. 如果用c[i, j]表示集合S(ij)的最优解的大小, 可得递归式:

c[i, j] = c[i, k] + c[k, j] + 1

如果不知道S(ij)的最优解包含活动ak, 就需要考查S(ij)中所有活动, 寻找哪个活动可获得最优解, 于是:

c[i, j] = {0|S(ij)=∅} or {max{c[i, k] + c[k, j] + 1} | S(ij)≠∅}

接下来就是设计带备忘机制的递归算法或自底向上的算法了.

贪心选择

对于活动选择问题, 我们只需要考虑一个选择: 贪心选择. 为什么呢? 直观上, 我们应该选择这样的活动, 选出它后剩下的资源应能被尽量多的其他任务所用. 现在考虑可选的活动, 其中必然有一个最先结束. 所以直觉告诉我们, 应该选择S中最早结束的活动, 因为之后的资源可供后面的活动尽量多的使用. 若最早活动结束有多个, 可以选择其中一个. 也就是说活动已按结束时间单调递增的顺序排序, 贪心选择就是活动a1.

做出贪心选择后, 下一个问题就是寻找a1结束后开始的活动. 剩下的S1是唯一需要求解的子问题. 最优子结构性质告诉我们, 若a1在最优解中, 则原问题的最优解由活动a1及子问题S1中所有活动组成.

贪心算法通常都是自顶向下的设计: 做出一个选择, 然后求解剩下的那个子问题, 而不是自底向上地求解出很多子问题, 然后在做出选择.

递归贪心算法

直接上代码:

# coding=utf-8

def Recursive_activity_selector(s, f, k, n): m = k + 1 while m <= n and s[m] < f[k]: m = m + 1 if m <= n: return str(m) + " " + str(Recursive_activity_selector(s, f, m, n)) else: return " "

if __name__ == "__main__": s = [0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12] f = [0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16] n = 11 k = 0 print(Recursive_activity_selector(s, f, k, n))

说明, 看图:

虚拟活动a0于时刻0结束, 所以第一次调用Recursive_activity_selector(s, f, 0, 11)会选择活动a1. 每次递归调用中, 被选中的活动用蓝色表示, 透明方框表示正在处理的活动. 若活动的开始时间早于最近选中的活动的结束时间, 将被丢弃.

迭代贪心算法

尾递归: 以一个对自身的递归调用在接一次并集操作的结尾, 如上面的return str(m) + " " + str(Recursive_activity_selector(s, f, m, n))我们就称为尾递归. 尾递归在数据量大的时候是很慢的. 下面我们改成迭代方法.

# coding=utf-8

def Greedy_activity_selector(s, f): n = len(s) - 1 A = str(s[1]) k = 1 for m in range(2, n + 1): if s[m] >= f[k]: A = A + " " + str(m) k = m return A

if __name__ == "__main__": s = [0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12] f = [0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16] print(Greedy_activity_selector(s, f))