`
liyiwen007
  • 浏览: 105343 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

《算法导论》笔记--动态规划解活动选择问题

阅读更多

  假设某大学有一个活动室,我是这个活动管理员。某天,有6个社团都提出了使用活动室的要求,并告知了他们希望使用活动室的时间段(他们之间相互不知道对方的要求,因此时间安排是没有相互商量过的,可能有重叠)。活动室不能同时被两个以上社团使用。作为管理员,我无法每次都满足所有人的要求,但我想尽量提高活动室的使用率,那么,我如何选取某几项活动,使得活动室的使用时间最长呢?

活动列表

  如上图,假设上图是某一次这些社团的要求(假设0是正午12点),各颜色条分别是各个社团的使用时间计划。那么,我应该如何分配活动室呢?显然,如果给了社团5,其它社团就不能再使用该活动室了,这时活动室的使用时间是从2点到8点,共使用了6个小时。但这不是最长的使用时间组合。如果将活动室分配给1、3、4、6,那么除了4点到5点之间活动室是空的之外,其它时间活动室都被使用了,一共使用时间是8个小时。

(其实在《算法导论》一书的第16章第一节中,也提到一个活动选择问题。这里说的活动选择问题与书中的不一样。这两个问题要求不一样。那个问题将在贪婪算法相关的内容中讨论)

 

  使用蛮力法,不会是一种好的方法。这一点就不过多论证了。

 

  这是个最优化问题。我们探索下,会发现这个问题的最优解,是有可能表示成子问题最优解的递归解的。假设Tij是一个从i点到j点的时间段,这个时间段内,最长的使用时间是Sij。Sij的计算中用到的活动,必须是要求整个活动时间被包括在Tij中的,不能越过这个时间限。我们就称Vij是这样一个集合,其中包含了所有时间范围被完全包含在Tij范围内的活动。

假设对于i点到j点Tij,如果i=j,那么很显然Sij就是0。如果i不等于j,那么最长使用使用时间Sij可能是j-i个小时,也就是有一个活动从i点一直搞到j点,那么挺好,就选择这个活动就行了。但如果不存在这么长时间的活动,那么,我们可以试着把这个时间分成两个部分Tik和Tkj,它们分别最长的使用时间是Sik和Skj。令S'=Sik+Skj,我们知道,当k从i到j依次取值时,可以得到各组不同的Sik和SkjSij肯定是S'中取最大的那个值。为什么呢?因为如果没有一个在Tij时间内段的活动能充满整个Tij时间段的话,那么Vij内的任何一个活动单独放到Tij时间段内,那么在这个时间段的前端和后端,至少会出现一个空白的没被使用的时间,如下图:

区间内的活动

  所以,直感上看,就可以把空白的时间段取出来,看这个时间段内还能不能再按排一些活动。只要没有一个活动可以填满整个时间段,那么最大使用时间就是Vij内多个活动时间拼接成的。那么对于从i到j内的每一个时间点k,这个点左右两边Tik和Tkj内会分别安排一些活动(因为每个活动都是从整点开始到整点结束,而且各活动使用活动室的时间也不能重叠。但可能Vik或Vkj会为空),就分别能得到Sik和Skj。只要对每一个可能的k值进行检查,那么最大时间肯定就是其中的一个。

因此,我们可以得出Sij的计算方法:

  1. 如果i=j,则 Sij=0
  2. 否则,如果存在一个活动的时候长度恰好为Tij则Sij=j-i
  3. 否则,Sij=max{Sik+Sij} ,其中、k从i到j依次取值。

 

  现在,我们已经得到了这个问题最优解的一个递归形式的解。递归式中包含了子问题的最优解。(关于子问题是否是最优解,可以用《算法导论》中的"剪切粘贴法"来考虑)。这是能用动态规划来解决的问题的第一个特征。

然后再看,如果我们根据这个递归直接翻译写出递归程序,那么,对于会出现很多重复的计算。比如,当我们计算S09时,会用到S01、S02、S03、S04、......、S07、S08,再计算S08时,又会用到S01、S02、S03、S04、......、S07以此类推,这个表达式中存在非常多的重复计算,计算量很大。嗯,有很多重叠的子问题,这是能用动态规划来解决的问题的第二个特征。

  那么,根据动态规划的方法,就应该用从底向上的方法来解决这个问题,先计算小区间的值,并存储起来,然后再利用已经得到的小区间的值来计算大区间的值。最终得到原问题的最优解。如下图 

动态表

  格子[i,j]表示从i点到j点,最大利用时间值是多少。灰掉的部分是无效值,因为此时i值大于j值,没有实际意思。这个表,我们从左到右计算每一列的值,就是用的从底向上的方法,最终可以地推出结果[0,9]的值是8.

  在计算最大时间的过程中,将每次使得Sij最大时的K值记录下来,存储到K[i][j]中去,Sij得出来之后,就可以到出一个K[i][j]的表,根据这个表,可以得到如何不断地将时间划分成最优的两段,直至时间段内有活动充满该时间段,或是时间段内不存在任何活动。有了这个时间划分,我们就可以从这些时间段中分别相应的活动,这样,问题就最终得到了解决。

 

 (代码等续:))

分享到:
评论
2 楼 liyiwen007 2009-06-26  
canofy 写道
3. 否则,Sij=max{Sik+Sij} ,其中、k从i到j依次取值。

这里应该是Sij=max{Sik+Skj} ,应该是笔误吧~


确实确实~!!
没想到会有人看得这么细。想来应该是高手~!


谢谢你!
1 楼 canofy 2009-06-24  
3. 否则,Sij=max{Sik+Sij} ,其中、k从i到j依次取值。

这里应该是Sij=max{Sik+Skj} ,应该是笔误吧~

相关推荐

Global site tag (gtag.js) - Google Analytics