更多疑问请点击这里哦
点击加载更多...
没有更多内容了
正在加载...
本周排行榜
问答探路者
问答探路者
问答探路者
问答探路者
问答探路者
问答探路者，目的地玩家　　前言：贪心算法也是用来解决最优化问题，将一个问题分成子问题，在现在子问题最优解的时，选择当前看起来是最优的解，期望通过所做的局部最优选择来产生一个全局最优解。书中先从活动选择问题来引入贪心算法，分别采用动态规划方法和贪心算法进行分析。本篇笔记给出活动选择问题的详细分析过程，并给出详细的实现代码进行测试验证。关于贪心算法的详细分析过程，下次在讨论。
1、活动选择问题描述
　　& 有一个需要使用每个资源的n个活动组成的集合S=&{a1，a2，&&&，an&}，资源每次只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi，且&0&si&fi&& 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，则称ai和aj两个活动是兼容的。该问题就是要找出一个由互相兼容的活动组成的最大子集。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。
从图中可以看出S***有11个活动，最大的相互兼容的活动子集为:{a1，a4，a8，a11，}和{a2，a4，a9，a11}。
2、动态规划解决过程
（1）活动选择问题的最优子结构
定义子问题解空间Sij是S的子集，其中的每个获得都是互相兼容的。即每个活动都是在ai结束之后开始，且在aj开始之前结束。
为了方便讨论和后面的计算，添加两个虚构活动a0和an+1，其中f0=0，sn+1=&。
结论：当i&j时，Sij为空集。
如果活动按照结束时间单调递增排序，子问题空间被用来从Sij中选择最大兼容活动子集，其中0&i＜j&n+1，所以其他的Sij都是空集。
最优子结构为：假设Sij的最优解Aij包含活动ak，则对Sik的解Aik和Skj的解Akj必定是最优的。
通过一个活动ak将问题分成两个子问题，下面的公式可以计算出Sij的解Aij。
（2）一个递归解
　　设c[i][j]为Sij中最大兼容子集中的活动数目，当Sij为空集时，c[i][j]=0；当Sij非空时，若ak在Sij的最大兼容子集中被使用，则则问题Sik和Skj的最大兼容子集也被使用，故可得到c[i][j] = c[i][k]+c[k][j]+1。
当i&j时，Sij必定为空集，否则Sij则需要根据上面提供的公式进行计算，如果找到一个ak，则Sij非空（此时满足fi&sk且fk&sj），找不到这样的ak，则Sij为空集。
c[i][j]的完整计算公式如下所示：
（3）最优解计算过程
　　根据递归公式，采用自底向下的策略进行计算c[i][j]，引入复杂数组ret[n][n]保存中间划分的k值。程序实现如下所示：
1 void dynamic_activity_selector(int *s,int *f,int c[N+1][N+1],int ret[N+1][N+1])
int i,j,k;
//当i&=j时候，子问题的解为空，即c[i][j]=0
for(j=1;j&=N;j++)
for(i=j;i&=N;i++)
c[i][j] = 0;
//当i&j时，需要寻找子问题的最优解，找到一个k使得将问题分成两部分
for(j=2;j&=N;j++)
for(i=1;i&j;i++)
//寻找k，将问题分成两个子问题c[i][k]、c[k][j]
for(k=i+1;k&j;k++)
if(s[k] &= f[i] && f[k] &= s[j])
//判断k活动是否满足兼容性
temp = c[i][k]+c[k][j]+1;
if(c[i][j] & temp)
ret[i][j] =
&（4）构造一个最优解集合
　　根据第三保存的ret中的k值，递归调用输出获得集合。采用动态规划方法解决上面的例子，完整程序如下所示：
1 #include &stdio.h&
2 #include &stdlib.h&
4 #define N 11
6 void dynamic_activity_selector(int *s,int *f,int c[N+1][N+1],int ret[N+1][N+1]);
7 void trace_route(int ret[N+1][N+1],int i,int j);
9 int main()
int s[N+1] = {-1,1,3,0,5,3,5,6,8,8,2,12};
int f[N+1] = {-1,4,5,6,7,8,9,10,11,12,13,14};
int c[N+1][N+1]={0};
int ret[N+1][N+1]={0};
dynamic_activity_selector(s,f,c,ret);
printf("c[i][j]的值如下所示：\n");
for(i=1;i&=N;i++)
for(j=1;j&=N;j++)
printf("%d ",c[i][j]);
printf("\n");
//包括第一个和最后一个元素
printf("最大子集的个数为: %d\n",c[1][N]+2);
printf("ret[i][j]的值如下所示：\n");
for(i=1;i&=N;i++)
for(j=1;j&=N;j++)
printf("%d ",ret[i][j]);
printf("\n");
printf("最大子集为:{ a1 ");
trace_route(ret,1,N);
printf("a%d}\n",N);
system("pause");
40 void dynamic_activity_selector(int *s,int *f,int c[N+1][N+1],int ret[N+1][N+1])
int i,j,k;
//当i&=j时候，子问题的解为空，即c[i][j]=0
for(j=1;j&=N;j++)
for(i=j;i&=N;i++)
c[i][j] = 0;
//当i&j时，需要寻找子问题的最优解，找到一个k使得将问题分成两部分
for(j=2;j&=N;j++)
for(i=1;i&j;i++)
//寻找k，将问题分成两个子问题c[i][k]、c[k][j]
for(k=i+1;k&j;k++)
if(s[k] &= f[i] && f[k] &= s[j])
//判断k活动是否满足兼容性
temp = c[i][k]+c[k][j]+1;
if(c[i][j] & temp)
ret[i][j] =
66 void trace_route(int ret[N+1][N+1],int i,int j)
trace_route(ret,i,ret[i][j]);
if(ret[i][j] != 0 )
printf("a%d ", ret[i][j]);
程序测试结果如下所示：
3、贪心算法解决过程
针对活动选择问题，认真分析可以得出以下定理：对于任意非空子问题Sij，设am是Sij中具有最早结束时间的活动，那么：
（1）活动am在Sij中的某最大兼容活动子集中被使用。
（2）子问题Sim为空，所以选择am将使子问题Smj为唯一可能非空的子问题。
有这个定理，就简化了问题，使得最优解中只使用一个子问题，在解决子问题Sij时，在Sij中选择最早结束时间的那个活动。
贪心算法自顶向下地解决每个问题，解决子问题Sij，先找到Sij中最早结束的活动am，然后将am添加到最优解活动集合中，再来解决子问题Smj。
基于这种思想可以采用递归和迭代进行实现。递归实现过程如下所示：
1 void recursive_activity_selector(int *s,int* f,int i,int n,int *ret)
int *ptmp =
int m = i+1;
//在Sin中寻找第一个结束的活动
while(m&=n && s[m] & f[i])
//添加到结果中
recursive_activity_selector(s,f,m,n,ptmp);
迭代实现过程如下：
1 void greedy_activity_selector(int *s,int *f,int *ret)
*ret++ = 1;
for(m=2;m&=N;m++)
if(s[m] &= f[i])
采用贪心算法实现上面的例子，完整代码如下所示：
1 #include &stdio.h&
2 #include &stdlib.h&
4 #define N 11
6 void recursive_activity_selector(int *s,int* f,int i,int n,int *ret);
8 void greedy_activity_selector(int *s,int *f,int *ret);
10 int main()
int s[N+1] = {-1,1,3,0,5,3,5,6,8,8,2,12};
int f[N+1] = {-1,4,5,6,7,8,9,10,11,12,13,14};
int c[N+1][N+1]={0};
int ret[N]={0};
//recursive_activity_selector(s,f,0,N,ret);
greedy_activity_selector(s,f,ret);
printf("最大子集为:{ ");
for(i=0;i&N;i++)
if(ret[i] != 0)
printf("a%d ",ret[i]);
printf(" }\n");
system("pause");
30 void recursive_activity_selector(int *s,int* f,int i,int n,int *ret)
int *ptmp =
int m = i+1;
//在i和n中寻找第一个结束的活动
while(m&=n && s[m] & f[i])
//添加到结果中
recursive_activity_selector(s,f,m,n,ptmp);
44 void greedy_activity_selector(int *s,int *f,int *ret)
*ret++ = 1;
for(m=2;m&=N;m++)
if(s[m] &= f[i])
程序测试结果如下所示：
　　活动选择问题分别采用动态规划和贪心算法进行分析并实现。动态规划的运行时间为O(n^3)，贪心算法的运行时间为O(n)。动态规划解决问题时全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。贪心算法的主要思想就是对问题求解时，总是做出在当前看来是最好的选择，产生一个局部最优解。
阅读(...) 评论()