注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

坤少的博客

静以修身,勤以补拙

 
 
 

日志

 
 
关于我

我是一个年轻的硕士生,我是一个有理想的IT人

文章分类
网易考拉推荐

活动选择问题(动态规划算法和贪心算法)  

2012-03-01 10:51:39|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题描述:

        有一个需要使用每个资源的n个活动组成的集合S= {a1,a2,···,an },资源每次只能由一个活动使用。每个活动a都有一个开始时间和结束时间,且 0<= s < f < 。一旦被选择后,活动a就占据半开时间区间[s,f]。如果[s,f]和[s,f]互不重叠,则称两个活动是兼容的。该问题就是要找出一个由互相兼容的活动组成的最大子集。

动态规划:

一、

        定义子集合Sij = { ak  S : f i <= sk < f k <= s j}, 即每个活动都在ai结束之后开始,在aj开始之前结束,亦即Sij包含了所有和ai和aj兼容的活动。 

假设S中的活动已按照结束时间递增的顺序排列,则Sij具有如下的性质:

1.当i <= j时,Sij 为空,

2.假设ak属于Sij,那么ak将把Sij分解成两个子问题,Sij包含的活动集合就等于Sik中的活动+ak+Skj中的活动。从这里就可以看出Sij的最优子结构性质:Sij的最优解包含了子问题Sik和Skj的最优解。假设Sij的最大兼容活动子集为Aij,那么有Aij = Aik U  ak U Akj。整个活动选择问题的最优解也是S0,n+1的解。

假设c[i,j]为Sij中最大兼容子集中的活动数。则有如下递归式:

      C[i,j] =         0                       如果 Sij 为空

                       max{c[i,k] + c[k,j] +1 }  i < k < j & ak  Sij  如果Sij 不为空

根据这个递归式,可以得到一个动态规划解法。

  1. void activity_selection( const int starts[], const int finished[], int counts[][activityNum+2],int partition[][activityNum+2], const int actNum )//counts[i,j]就是C[i,j],partition[i,j]表示Sij使用哪个活动划分可以得到最大兼容活动集合  
  2. {  
  3.     int i,j,k;  
  4.   
  5.     for( i = 0; i < activityNum+2; ++i )  
  6.         for( j = 0; j < activityNum+2; ++j )  
  7.         {  
  8.                 counts[i][j] = 0;  
  9.                 partition[i][j] = 0;  
  10.         }  
  11.   
  12.     for( i = activityNum; i >=0; --i )  
  13.     {  
  14.         for( j = i+1; j < activityNum+2; ++j )  
  15.         {  
  16.                 for( k = i+1; k < j; ++k )  
  17.                 {  
  18.                     if( starts[k] >= finished[i] && finished[k] <= starts[j] )//s【i,j】不为空  
  19.                     {  
  20.                         if( counts[i][j] <= (counts[i][k] + 1 + counts[k][j]) )                                           {  
  21.                             counts[i][j] = (counts[i][k] + 1 + counts[k][j]);  
  22.                             partition[i][j] = k;  
  23.                         }  
  24.                     }  
  25.                 }  
  26.         }  
  27.     }//for  
  28. }  

算法的时间复杂度为O(n3)。

二、

除了上面的思路外,我们还可以参照最长单调递增子序列LIS的解法,得到另外一个动态规划方法。

我们定义一个数组maxCompatibleSet,元素maxCompatibleSet[i]表示S0i中最大兼容活动子集中的活动数目,那么整个集合的最大兼容活动子集的大小就是maxCompatibleSet[n+1]。为了确定最大兼容活动子集中的活动,我们可以定义一个数组trace,

Trace[i]表示在求解maxCompatibleSet[i]时使用哪个活动对集合S0i进行划分可以得到最大的maxCompatibleSet[i]。

  1. //类似于LIS  
  2. void activitySelection( const int started[], const int finished[], int maxSetNum[], int trace[], const int activityNum )  
  3. {  
  4.     int i, j;  
  5.     for( i = 0; i < activityNum+2; ++i )  
  6.     {  
  7.         maxSetNum[i] = 1;  
  8.         trace[i] = -1;  
  9.     }  
  10.     for( i = 1; i < activityNum+2; ++i )  
  11.     {  
  12.         for( j = 1; j < i; ++j )  
  13.         {  
  14.             if( finished[j] < started[i] && maxSetNum[i] <= maxSetNum[j] )            {  
  15.                 maxSetNum[i] = maxSetNum[j]+1;   
  16.                 trace[i] = j;  
  17.             }  
  18.         }  
  19.     }  
  20. }  

该算法的时间复杂度为O(n2)。

贪心算法:

贪心算法的主要思想就是对问题求解时,总是做出在当前看来是最好的选择,产生一个局部最优解。

在活动选择问题中,每次的贪心解就是选择Sij结束时间最早的活动,这样就给后面的活动留下了目前看来最多的时间。假设活动已经按照结束时间递增的顺序进行排序,那么我们只需要遍历一次所有活动就可以得到最大兼容活动子集了。

递归版本:

  1. void recursive_activity_selector( const int started[], const int finished[],vector<int>& result, int i,int j)  
  2. {  
  3.     if( i >= j )  
  4.         return;  
  5.     int l;  
  6.     for( l = i+1; l < j; ++l )  
  7.     {  
  8.         if( started[l] >= finished[i] && finished[l] <= started[j] )   
  9.         {  
  10.             result.push_back(l);  
  11.             break;  
  12.         }  
  13.     }  
  14.     recursive_activity_selector( started, finished, result, l, j );  
  15. }  

 

迭代版本:

  1. void greedy_activity_selector( const int started[], const int finished[], vector<int>& result, int i, int j )  
  2. {  
  3.     int l;  
  4.     for( l = i+1; l < j; ++l )  
  5.     {  
  6.         if( started[l] >= finished[i] && finished[l] <= started[j] )  
  7.         {  
  8.             result.push_back(l);  
  9.             i = l;  
  10.         }  
  11.     }  
  12. }  


 
  评论这张
 
阅读(6158)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017