動的計画:最長共通サブシーケンスLCS

最長共通サブシーケンスの問題は、次のように記述できます.
2つのシーケンスX[0,・・m]とY[0,・・n]を与え,XとYの最大長の共通サブシーケンスS,すなわち最長共通サブシーケンス問題(longest common sequence)を探し出す.
分析:
Z[0,・・・k]がXとYのLCSであると仮定すると、以下の法則が存在する.
1.X[m]==Y[n]==Z[k]の場合、Z[0,・・k-1]はX[0・・m-1]とY[0・・n-1]のLCSである.
2.X[m]!=Y[n],Z[k]!=X[m]はZ[0・・・k]がX[0・・m-1]とY[0・・・n]のLCSであることを意味する.
3.X[m]!=Y[n],Z[k]!=Y[n]は、Z[0・・・k]がX[0・・m]およびY[0・・n−1]のLCSであることを意味する.
以上の3つから,最長共通サブシーケンスは最適サブ構造(すなわち,1つの問題の最適解がサブ問題の最適解を含む)を有し,最適サブ構造も動的計画の基本要素であることが分かる.
上記の3つの法則によれば、X=(x 1,x 2,・・,xm)とY=(y 1,y 2,・・,yn)の1つのLCSが要求される場合、次の2つのケースを考慮することが分かる.
1.xm==ynの場合、次にXm-1とYn-1のLCSを要求し、Xmを加算するとXとYのLCSを構成する.
2.xm!=ynは、Xm−1およびYの1つのLCS、およびXmおよびYn−1の1つのLCS、すなわちXおよびYの1つのLCSを得ることが要求される.
ここからも,この問題のオーバーラップサブ問題の性質(異なるサブ問題は共通のサブ問題を含む)が見られ,これも動的計画の第2の要素である.
以上の解析から,LCSが動的計画によって解くことができることを決定できた.
LCSの最適サブ構造から以下の再帰方程式が得られる.
0 i=0またはj=0の場合
C[i,j]=c[i-1,j-1]i,j>0,xi==yj
Max(c[i-1,j],c[i,j-1])i,j>0の場合、xi!= yj
上記の再帰方程式によれば,関数を書き出してLCSの長さを計算することができる.LCSを求めるために、補助的な2次元配列actionを維持し、列挙タイプenum Action{both_erase,x_erase,y_erase}を定義することができる.
プロセスは次のとおりです.

void lcs( char seq1[], char seq2[], int len[][length2+1], Action action[][length2], int len1, int len2 )
{
	int i, j;
	for( i = 0; i <= length1; ++i )
		len[i][0] = 0;
	for( j = 0; j <= length2; ++j )
		len[0][j] = 0;
	for( i = 0; i < length1; ++i )
		for( j = 0; j < length2; ++j )
		{
			if( seq1[i] == seq2[j] )
			{
				len[i+1][j+1] = len[i][j] + 1;
				action[i][j] = both_erase;
			}else
			{
				len[i+1][j+1] = len[i+1][j] >= len[i][j+1] ? len[i+1][j] : len[i][j+1];
				if( len[i+1][j+1] == len[i][j+1] ).
					action[i][j] = x_erase;
				else
					action[i][j] = y_erase;
			}
		}
}

len[i][j]はseq 1[0・・i-1]とseq 2[0・・・j-1]の2つのシーケンス間のlcsの長さを表し、action[i][j]はseq 1[0・・・i]とseq 2[0・・j]の2つのシーケンスのlcsを出力する際に取るべき動作を表し、後でactionに基づいてLCSを印刷できるようにする.
印刷関数は次のとおりです.

void print( char seq1[], Action action[][length2], int len1, int i, int j )
{
	if( i >= 0 && j >= 0 )
	{
		if( action[i][j] == both_erase )
		{
			print( seq1, action, len1, i-1, j-1 );
			cout << seq1[i];
		}
		else if( action[i][j] == x_erase )
			print( seq1, action, len1, i-1, j );
		else
			print( seq1, action, len1, i, j-1 );
	}
}

補助配列アクションを必要としない印刷関数は、次のとおりです.

void print_without_ancillary_space( char seq1[], int len[][length2+1], int i , int j )
{
	if( i > 0 && j > 0 )
	{
		if( len[i][j] == len[i-1][j] )
		{
			print_without_ancillary_space( seq1, len, i-1, j );
		}else if ( len[i][j] == len[i][j-1] )
		{
			print_without_ancillary_space( seq1, len, i, j-1 );
		}else if( len[i][j] == len[i-1][j-1] + 1 )
		{
			print_without_ancillary_space( seq1, len, i-1, j-1 );
			cout << seq1[i-1];
		}
	}
}

いくつかの問題が発生しました.
1.lcs関数における最初のelse分岐ではactionの値を得るためには、len[i+1][j+1]とlen[i][j+1]の関係を先に判断する必要がある.len[i+1][j+1]とlen[i+1][j]の関係を先に判断すると、プログラムがエラーになり、原因はまだはっきりしていない.
2.c++のすべての文字列のフォント値には、コンパイラが末尾に空の文字を自動的に追加します.
プログラムファイルが必要な場合は、こちらをクリックしてください