【算法导论】动态规划之最长公共子序列-阿里云开发者社区

开发者社区> 大数据> 正文
登录阅读全文

【算法导论】动态规划之最长公共子序列

简介:         子序列:一个给定序列的子序列就是该给定序列去掉零个或者多个元素后的序列。例如:Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一个子序列。

        子序列:一个给定序列的子序列就是该给定序列去掉零个或者多个元素后的序列。例如:Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一个子序列。注意顺序不能改变

        公共子序列:既是序列X的子序列,又是序列Y的子序列。例如:X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},则序列{B,C,A}是X和Y的一个公共子序列,长度为4;序列{B,C,B,A}是X和Y的一个最长公共子序列(LCS),长度为4.

        当然,我们可以查用穷举法来解决问题,但是,对于一个长度为n的序列,其子序列为2^n,因此时间复杂度为指数形式,当n很大时,显然不合实际。由观察和推导可知,最长公共子序列具有最优子结构性质和重叠子问题性质。因此我们可以通过动态规划算法来找到最长公共子序列,其时间复杂度为O(mn+m+n)。(m,n分别为两个序列的元素个数)

        在下面的程序实现中,我假设两个序列为上面提到的X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},数组b对应于在计算c[i][j]时所选择的最优子问题的解,数组c[i][j]为Xi和Yj的一个LCS的长度,Xi为序列的前i个元素组成的序列,Yj为序列的前j个元素组成的序列.

具体程序如下:

#include<stdio.h>

void Lcs_Length(char *X,char *Y,int n1,int n2,int b[][7],int c[][7]);
void Print_Lcs(char *X,int b[][7],int i,int j);

void main()
{
	char X[]={'A','B','C','B','D','A','B'};
	char Y[]={'B','D','C','A','B','A'};
	int n1=sizeof(X)/sizeof(char);
	int n2=sizeof(Y)/sizeof(char);
	
	int b[8][7]={0};//b[i][j]对应于在计算c[i][j]时所选择的最优子问题的解
	int c[8][7]={0};//c[i][j]为Xi和Yi的一个LCS的长度
	
	Lcs_Length(X,Y,n1,n2,b,c);
	printf("最长公共子序列为:");
    Print_Lcs(X,b,n1,n2);
    printf("\n");
}
/*******************************************************************\
函数功能:计算最长公共子序列的长度,并将结果存储在数组c中
输入:    两个序列X、Y 待存储的数组b,c
输出:    无
\*******************************************************************/
void Lcs_Length(char *X,char *Y,int n1,int n2,int b[][7],int c[][7])
{
	
	for(int i=0;i<n1;i++)
		c[i][0]=0;
	for(int i=0;i<n2;i++)
		c[0][i]=0;
	for(int i=1;i<=n1;i++)
		for(int j=1;j<=n2;j++)
		{
			if(X[i-1]==Y[j-1])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;//b用于做标记,便于打印
			}
			else if(c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]=2;
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]=3;
			}
		}
}


/*******************************************************************\
函数功能:打印最长公共子序列
输入:    原始序列X、已存储的数组b,i j表示是求X的前i个元素和Y的前j个元素的LCS
输出:    无
\*******************************************************************/
void Print_Lcs(char *X,int b[][7],int i,int j)
{
	if(i==0||j==0)
		return;
	if(b[i][j]==1)
	{
		Print_Lcs(X,b,i-1,j-1);//递归打印
		printf("%c ",X[i-1]);
	}
	else if(b[i][j]==2)
        Print_Lcs(X,b,i-1,j);
	else
		Print_Lcs(X,b,i,j-1);
	
}

上面程序得到的结果数组c和b如下图:

上表中的数字代表长度,例如c[7][6]=4代表序列X的前7个元素组成的序列和序列Y前6个元素组成的序列的最长公共子序列的长度为4.

在程序中为了方便起见,b数组用数字1,2,3分别代表↖,↑,←。


原文:http://blog.csdn.net/tengweitw/article/details/16950673

作者:nineheadedbird



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
大数据
使用钉钉扫一扫加入圈子
+ 订阅

大数据计算实践乐园,近距离学习前沿技术

其他文章
最新文章
相关文章