Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1003537
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-12-07 23:24:59

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等价。
 
由以上推理,如果我们每次选取最后一个开始,且与之前选中的活动兼容的活动,那么最终一定构成某个最佳解中。
这个贪心算法是成立的。
 
阅读(3038) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~