【アルゴリズム】LCS最長共通サブシーケンス

LCS-Longest Common Subsequence
最大共通サブシーケンス1つのシーケンスは、2つ以上の既知のシーケンスのサブシーケンスであり、すべてのサブシーケンスの中で最も長い場合、最も長い共通のサブシーケンスである.

#include 
#include 
#include 

#define SIZE 100

int main()
{
	char A[SIZE],B[SIZE];
	int i,j,n;

	printf("     A:");
	char *p1 = &(A[1]);
	gets(p1);
	A[0] = '0';
	printf("     B:");
	char *p2 = &(B[1]);
	gets(p2);
	B[0] = '0';

	const int len_A = strlen(A)-1;
	const int len_B = strlen(B)-1;

/*  c    LCS   */
	int **c;
	c = (int **)malloc(sizeof(int*)*(len_A+1));
	for(i=0;i= c[i][j-1])
			{
				c[i][j] = c[i-1][j];
				b[i][j] = 'u';
			}
			else
			{
				c[i][j] = c[i][j-1];
				b[i][j] = 'l';
			}
		}

	for(i=0;i<=len_A;i++)
	{
		for(j=0;j<=len_B;j++)
			printf("%c  ",b[i][j]);
		printf("
");
	}

	i = len_A;
	j = len_B;
	n = 0;
	while(b[i][j] != '0')
	{
		switch (b[i][j])
		{
		case 'u':
			i--;
			break;
		case 'l':
			j--;
			break;
		case 'b':
			result[n++] = A[i];
			i--;
			j--;
			break;
		}
	}

	free(c);
	free(b);
	result[n] = '\0';
	for(i=n-1;i>=0;i--)
		printf("%c",result[i]);
}

アルゴリズム解析:
最適なサブ構造:X={x 1,x 2,…,xm}とY={y 1,y 2,...,yn}を2つのシーケンスに設定し、Z={z 1,z 2,…,zk}をXとYのいずれかのLCSに設定します.
1)xm=ynなら、zk=xm=yn、そしてZk-1はXm-1とYn-1のLCSです.
2)xm≠ynなら、zk≠xmはZがXm-1とYのLCSを含みます.
3)xm≠ynなら、zk≠ynはZがXとYn-1のLCSを含んでいます.
シーケンスXiとYjの一つのLCSの長さをc[i,j]で表す.では、
c[i,j]= 
case i=0,j=0:c[i,j]=0;
case i,j>0xi=yj: c[i,j]=c[i-1,j-1]+1;
case i,j>0xi. ≠yj: c[i,j]=max(c[i,j-1],c[i-1,j]
疑似コード:

LCS_LENGTH(X,Y)
m ← length[X]
n ← length[Y]
for i ← 1 to m
        do c[i,0] ← 0
for j ← 1 to n
        do c[0,j] ← 0
for i ← 1 to m
        do for j ← 1 to n
                     do if xi = yj
                                then c[i,j] ← c[i-1,j-1] + 1
                                         b[i,j] ← "↖"
                                else if c[i-1,j] ≥ c[i,j-1]
                                            then c[i,j] ← c[i-1,j]
                                                     b[i,j] ← "↑"
                                           else c[i,j] ← c[i,j-1]
                                                    b[i,j] ← "←"
return c and b

フローチャート:
配列cにおいて、c[i,j]はXiとYjの一つのLCSの長さを表し、先ほども述べたように、配列bは最適解を求める経路を表す.以下の例を示します
X={A,B,C,B,D,A,B}
Y={B,D,C,A,B,A}

m ← length[X]
n ← length[Y]
for i ← 1 to m
        do c[i,0] ← 0
for j ← 1 to n
        do c[0,j] ← 0

はcテーブルを初期化し、0を記入する.

for i ← 1 to m
        do for j ← 1 to n
                     do if xi = yj
                                then c[i,j] ← c[i-1,j-1] + 1
                                         b[i,j] ← "↖"
                                else if c[i-1,j] ≥ c[i,j-1]
                                            then c[i,j] ← c[i-1,j]
                                                     b[i,j] ← "↑"
                                           else c[i,j] ← c[i,j-1]
                                                    b[i,j] ← "←"

ここでは、2層のforサイクルがあり、外側の層はlength_を循環する.A回、内層レングスB回
逐次解析forサイクル:
このとき、テーブルは次のように更新されます.
i=2再循環
表c変化:
二つのjの循環によって、c[i,j]の値を記入するたびに、クエリの前に記入された、つまりチェックシートであり、元の値は修正されないことが分かります.サブ構造を最適化して最適値を得るということは、サブ構造が最適である場合には、cut-and-pasteを通じて最適解が得られます.これがダイナミック企画の思想です.
上記の2ステップを通して、jは2回しか取れませんでしたが、X={A,B}Y={B,D,C,A,B,A}のLCSを検証できます.
上の図に示すように、LCSはABであり、この結果は特別であり、XはYのサブセットであるが、動的計画が最適解されるという考え方が見られます.