《算法导论》贪心法:习题16.1-2

16.1-2

假设不再总是选择第一个结束的活动，而是选择最后一个开始、且与之前选入活动兼容的活动。试说明这种方式如何成为一个贪心算法，并证明它能得到一个最优解。

 

定义所有的活动全集为集合A = {a0, a1 ... an},并假设集合中的每个活动，按照开始时间降序排列。

定义S(i,j)为这样一个集合的集合：S(i,j)中的每个集合描述了从时刻i开始到时刻j结束，可安排的兼容活动的最多活动。
显然S(i,j)可能有多个元素，每个元素都是一互相等价的，即他们可安排的活动的数量是相同的。
数学表述为：
S(i,j) = { {a1,a2 .. ak}, {a2,a3 ... am} ... }
为了直观，暂且称每个S(i,j)中的元素为元素集合。

 

设am是S(i,j)中所有元素集合中，最后一个开始的活动,f(am)表示其开始的时间
    f(am) = max{f(ak): ak∈S(i,j)}

选择am后，S(i,j)将划分为两部分S(i,m)和S(m,j)
1.显然，子问题S(m,j)为空，问题会缩减为S(i,m)
  假设S(m,j)不为空集，那么存在一个活动ak,其开始时间f(ak)>f(am)，且ak是S(m,j)的元素，这与题设am是S(i,j)中最后一个开始的活动相矛盾。
2.活动am在某个S(i,j)等价的子集中存在
  设活动ak是所有活动集合A中最后一个开始的活动。那么如果am = ak,则说明ak确实在S(i,j)中的某个元素集合中出现。
  如果am!=ak,那么对于包含ak的那个元素集合，假设为Sk = {... ... ak} 

  因为f(am)>f(ak)，即am的开始时间晚，那么我们显然可以用am替换ak,这样得到的新集合Sm = {... ... am}，仍然是兼容的，即是S(i,j)的元素子集,与Sk等价。

 

由以上推理，如果我们每次选取最后一个开始，且与之前选中的活动兼容的活动，那么最终一定构成某个最佳解中。
这个贪心算法是成立的。