802      阿裏雲  技術社區[雲棲]

算法知識之最長公共子序列問題(動態規劃)

最近朋友讓幫做個關於動態規劃的最長公共子序列的問題,翻看以前的筆記並完成該題後,順便寫這樣一篇文章,希望對大家有所幫助,同時也幫助自己回顧該知識點.

一.最長公共子序列的定義

子序列:若給定序列X={x1,x2,…,xm},則另一序列Z={z1,z2,…,zk},是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對於所有j=1,2,…,k有:zj=xij.
公共子序列:給定2個序列X和Y,當另一序列Z既是X的子序列又是Y的子序列時,稱Z是序列X和Y的公共子序列.
最長公共子序列:給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最長公共子序列.
如：序列ABCDEF和ADFGH的最長公共子序列為ADF

注意:最長公共子串(Longest Common Substirng)和最長公共子序列(Longest Common Subsequence,簡稱LCS)的區別為是最長公共子串的串是一個連續的部分,而最長公共子序列則是從不改變序列的順序,而從序列中去掉任意的元素而獲得新的序列;通俗的說就是子串中字符的位置必須是連續的而子序列則可以不必連續.

二.最優子結構性質

設序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk} ,則
    (1)若xm=yn,則zk=xm=yn,且z1,z2,…, zk-1是否為x1,x2,…,xm-1和y1,y2,…,yn-1的最長公共子序列.
    (2)若xm≠yn且zk≠xm,則Z是x1,x2,…,xm-1和Y的最長公共子序列.
    (3)若xm≠yn且zk≠yn,則Z是X和y1,y2,…,yn-1的最長公共子序列.

由此可見,2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列.因此,最長公共子序列問題具有最優子結構性質.當問題具有最優子結構性質和子問題重疊性質時就可以用動態規劃算法解決該問題.

三.動態規劃方法分析

由最長公共子序列問題的最優子結構性質建立子問題最優值的遞歸關係.用c[i][j]記錄序列和的最長公共子序列的長度.其中,Xi={x1,x2,…,xi},Yj={y1,y2,…,yj}.當i=0或j=0時,空序列是Xi和Yj的最長公共子序列.故此時C[i][j]=0.其它情況下,由最優子結構性質可建立遞歸關係如下:

其對應的核心代碼如下:

//參數:x字符串長度為m y字符串長度為n
void LCSLength(char x[], char y[],int m，int n)
{  
       /* 計算最長公共子序列的長度 */
       int L[m][n],i，j;
       for (i = 0; i <= m; i++) L[i][0] = 0;
       for (i = 0; i <= n; i++) L[0][i] = 0;
       for (i = 1; i <= m; i++)
       {
          for (j = 1; j <= n; j++) 
	  {
             if (x[i]==y[j]) 
                  L[i][j]=L[i-1][j-1]+1;
             else if (L[i-1][j]>= L[i][j-1])
                  L[i][j]= L[i-1][j]; 
             else 
                  L[i][j]= L[i][j-1];
          }
       } 
       return L[m][n];
}

例如:輸入字符串“bdcaba”和"abcbdab",求它們的最長公共子序列長度.在《算法設計與分析》課程中我們老師講述的方法通常是使用動態規劃填充表格方法解決.初始時,X字符串的長度為m,Y字符串的長度為n.c[m,n]二位數組如上麵遞歸關係遞歸,最後的c[m,n]為最大數字即最長公共子序列的長度.

四.問題的提出與解決

1.問題

2.代碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int *pln1 , *pln2;
char a[10010] , b[10010];
int main()
{
	int i , j , lena , lenb ;
	gets(a);
	gets(b);
	lena = strlen(a);
	lenb = strlen(b);
	pln1 = (int*)calloc( lenb + 1 , sizeof(int) );
	memset( pln1 , 0 , sizeof(pln1) );
	pln2 = (int*)calloc( lenb + 1 , sizeof(int) );
	memset( pln2 , 0 , sizeof(pln2) );
	for( i = 1 ; i <= lena ; i++ )
	{
		for( j = 1 ; j <= lenb ; j++ )
		{
			if( a[i-1] == b[j-1] )
			{
				pln2[j] = pln1[j-1] + 1;
			}
			else
			if( pln1[j] >= pln2[j-1] )
			{
				pln2[j] = pln1[j];
			}
			else
			{
				pln2[j] = pln2[j-1];
			}
		}
		free(pln1);
		pln1 = pln2;
		pln2 = (int*)calloc( lenb + 1 , sizeof(int) );
		memset( pln2 , 0 , sizeof(pln2) );
	}
	printf( "%d\n" , pln1[lenb] );
	return 0;
}

五.問題的升華與解決

1.升華問題

輸入:輸入文件中的第1行是一個正整數T(0<T<=10),表示有T組測試數據.接下來是每組測試數據的描述,每組測試數據有3行.測試數據的第1行有2個正整數m、n,中間用一個空格隔開(0<m，n<50);第2、3行是長度分別為m、n的2個序列X和Y,每個序列的元素間用一個空格隔開.序列中每個元素由字母、數字等構成.輸入直到文件結束

輸出:對輸入中的每組測試數據,先輸出Case #表示第幾組數據,在輸出最長公共子序列,輸出所有的最長公共子序列,並輸出動態規劃表格c表和b表.(測試用例見結果圖)

2.代碼

第一個LSCLength函數是求最長公共子序列長度的函數,並在該函數中填充c[m][n]和b[m][n].

//函數：計算最優值
//參數：m字符串X長 n字符串Y長 X字符串 Y字符串 b標誌數組尋找所有字符串用
int LSCLength( int m, int n, char *X, char *Y, int b[][100] )
{
	/*計算最長公共子序列的長度*/
	int num[100][100];
	int i,j;
	int sum;
	
	/*清零*/
	for( i=0 ; i<=m ; i++ )
	{
		for( j=0 ; j<=n ; j++ )
		{
			num[i][j]=0;
			b[i][j]=0;
		}
	} 
	
	/* 遞歸結構-動態規劃並輸出 */
	for( i=1 ; i<=m ; i++ )
	{		
		for( j=1 ; j<=n ; j++ )
		{
			if( X[i]==Y[j] ) {
				num[i][j]=num[i-1][j-1]+1;
				b[i][j]=1;
			}
			
			else if( num[i-1][j]>num[i][j-1] ) {
				num[i][j]=num[i-1][j];
				b[i][j]=2;
			}
			
			else if( num[i-1][j]<num[i][j-1] ){
				num[i][j]=num[i][j-1];
				b[i][j]=3;
			}
			else {
				num[i][j]=num[i][j-1];
				b[i][j]=4;
			}
		}	
	}
	
	sum = num[m][n];
	printf("最長公共子序列的長度：%d\n",sum);
		
	//輸出c[m][n]表
	printf("\n");
	for(i=0;i<=m;i++)
	{
		for(j=0;j<=n;j++)
		{
			printf("%d ",num[i][j]);
		}
		printf("\n");
	}
	//輸出b[m][n]表
	printf("\n");
	for(i=0;i<=m;i++)
	{
		for(j=0;j<=n;j++)
		{
			printf("%d ",b[i][j]);
		}
		printf("\n");
	}
	
	return sum;
}

第二個DisplayLSC函數是通過b[m][n]遞歸計算所有最長公共子序列,並存儲至result數組中.

//定義全局變量用於保存結果result 結果個數保存為count
char result[100];
int count=0;

//函數：計算所有最長公共子序列
//參數：m字符串X的長度 n字符串Y的長度 b標誌數組 current_len當前長度 max_len最長公共子序列長度
void DisplayLSC(int i,int j,char *X,int b[][100],int current_len,int max_len)
{
	int s;

	//采用遞歸的算法求解所有長度
	if(i==0 || j==0)                 //為0時輸出結果並返回
	{
		for(s=0;s<max_len;s++)
		{
			printf("%c ",result[s]);
		}
		printf("\n");
		count++;
		return;
	}

	if(b[i][j]==1)
	{
		current_len--;
		result[current_len]=X[i];
		DisplayLSC(i-1,j-1,X,b,current_len,max_len);
	}
	else
	{
		if(b[i][j]==2)
		{
			DisplayLSC(i-1,j,X,b,current_len,max_len);
		}
		else
		{
			if(b[i][j]==3)
			{
				DisplayLSC(i,j-1,X,b,current_len,max_len);
			}
			else
			{
				DisplayLSC(i,j-1,X,b,current_len,max_len);
				DisplayLSC(i-1,j,X,b,current_len,max_len);
			}
		}
	}
}

3.結果

最後輸出的結果如下圖所示:

希望該文章對大家有所幫組,同時該文章參考了王曉東的《計算機算法設計與分析》,並引用了自己學校的PPT動態規劃內容.同時感謝夢醒瀟湘love博主的文章,希望大家也可以去見解該文章.
https://blog.chinaunix.net/uid-26548237-id-3374211.html
文章主要是對自己以前學過的知識的鞏固以記錄,如果有錯誤或不足之處,希望大家海涵.
(By:Eastmount 2013-11-5 中午3點https://blog.csdn.net/eastmount/)

最後更新：2017-04-03 14:54:03

  上一篇： 大創1-Hadoop安裝筆記

  下一篇： Hadoop2.0 Namenode HA實現方案介紹及匯總