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

今日1つの招待状を見て、原文は以下の通りです
2つの列の最長共通サブシーケンス(サブ列ではなく、サブシーケンスが不連続であってもよい)を求めるには、以下のアルゴリズム(lcs、ダイナミックプランニングを使用しています)最長共通サブシーケンスを求めることができます.badbです.長さは4です.しかし、この2つの列bacdbdとdbcbadbの最長共通サブシーケンスは3つあります.それぞれbadb、bcbd、bcdbです.長さは4です.どうやって求めますか.
Java code
import
java.io.
*
;
public
class
ys {
static
int
length
=
0
;
//
最長共通サブシーケンスの長さを保存
   
static
String  str_same
=
""
; 
//
最長共通サブシーケンスの保存
   
static
int
k
=
0
;   
public
static
void
main(String args[])    {       
char
x[],y[];        String str_x
=
"
bacdbd
"
,str_y
=
"
dbcbadb
"
;
//
元の比較の2つの列
       
try
{            str_x
=
"
"
+
str_x;                    str_y
=
"
"
+
str_y;        }
catch
(Exception e){            e.printStackTrace();        }        x
=
str_x.toCharArray();        y
=
str_y.toCharArray();       
int
b[][]
=
new
int
[x.length][y.length]; lcsLength(x,y,b); lcs(x.length
-
1
,y.length
-
1
,x,b);        System.out.println(
"
length:
"
+
length);        System.out.println(
"
str_same:
"
+
str_same);        System.out.print(
"
/n
"
);    }   
public
 
static
void
lcsLength(
char
[]x,
char
[]y,
int
[][]b)    {       
int
xMaxIndex
=
x.length
-
1
;       
int
yMaxIndex
=
y.length
-
1
;       
int
count[][]
=
new
int
[xMaxIndex
+
1
][yMaxIndex
+
1
];       
for
(
int
i
=
0
;i
<=
xMaxIndex;i
++
)        {            count[i][
1
]
=
0
;        }       
for
(
int
i
=
0
;i
<=
yMaxIndex;i
++
)        {            count[
0
][i]
=
0
;        }       
for
(
int
i
=
1
;i
<=
xMaxIndex;i
++
)       
for
(
int
j
=
1
;j
<=
yMaxIndex;j
++
)        {           
if
(x[i]
==
y[j])
//
等しい場合は対角線に1を加算
            {                count[i][j]
=
count[i
-
1
][j
-
1
]
+
1
;                b[i][j]
=
1
;            }           
//
等しくない場合は、上と左を比較して最大値をとります
           
else
if
(count[i
-
1
][j]
>=
count[i][j
-
1
])             {                count[i][j]
=
count[i
-
1
][j];                b[i][j]
=
2
;            }           
else
            {                count[i][j]
=
count[i][j
-
1
];                b[i][j]
=
3
;            }                    }    }   
public
static
void
lcs(
int
i,
int
j,
char
[]x,
int
[][]b)    {       
if
(i
==
0
||
j
==
0
)        {           
return
;        }       
if
(b[i][j]
==
1
)        {            length
++
;                       lcs(i
-
1
,j
-
1
,x,b);            str_same
+=
x[i];        }       
else
if
(b[i][j]
==
2
)        {                        lcs(i
-
1
,j,x,b);                    }       
else
if
(b[i][j]
==
3
)        {            lcs(i,j
-
1
,x,b);        }    }}

 
  
 
   分析后解答如下 
  
 
  
 
   import java.io.*; 
public class Ys 
{ 
    static int length = 0; //保存最长公共子序列的长度 
    static int maxLength = 0;//记录最长子序列长度 
    static int count = 0; 
     
    static int k = 0; 
    public static void main(String args[]) 
    { 
     String  str_same = "";  //保存最长公共子序列 
        char x[],y[]; 
        String str_x="bacdbd",str_y="dbcbadb"; //原始比较的两个串 
        try{ 
            str_x=" "+str_x;         
            str_y=" "+str_y; 
        } catch(Exception e){ 
            e.printStackTrace(); 
        } 
        x=str_x.toCharArray(); 
        y=str_y.toCharArray(); 
        int b[][]=new int[x.length][y.length]; 
        lcsLength(x,y,b); 
        lcs(x.length-1,y.length-1,x,b,""); 
    } 
    public  static void lcsLength(char []x,char []y,int [][]b) 
    { 
        int xMaxIndex=x.length-1; 
        int yMaxIndex=y.length-1; 
        int count[][]=new int[xMaxIndex+1][yMaxIndex+1]; 
        for(int i=0;i <=xMaxIndex;i++) 
        { 
            count[i][1]=0; 
        } 
        for(int i=0;i <=yMaxIndex;i++) 
        { 
            count[0][i]=0; 
        } 
        for(int i=1;i <=xMaxIndex;i++) 
        for(int j=1;j <=yMaxIndex;j++) 
        { 
            if(x[i]==y[j]) //如果相等 则对角线加一 
            { 
                count[i][j]=count[i-1][j-1]+1; 
                maxLength = Math.max(maxLength,count[i][j]); 
                b[i][j]=1; 
            } 
            //如果不等,则比较上方和左方,取最大值 
            else if(count[i-1][j]>count[i][j-1])  
            { 
                count[i][j]=count[i-1][j]; 
                maxLength = Math.max(maxLength,count[i][j]); 
                b[i][j]=2; 
            }  
  
 
  
 
    else if (count[i-1][j]             { 
  
 
  
 
                   count[i][j]=count[i][j-1]; 
                maxLength = Math.max(maxLength,count[i][j]); 
                b[i][j]=3; 
             
             }
            else  
            {  
  
 
  
 
                   count[i][j]=count[i-1][j]; 
                maxLength = Math.max(maxLength,count[i][j]); 
                b[i][j]=4; 

            } 

        } 
    } 
    public static void lcs(int i,int j,char []x,int [][]b,String strResult) 
    { 
        if(i==0 ¦ ¦j==0) 
        { 
            return; 
        } 
        if(b[i][j]==1) 
        { 
         strResult = x[i] + strResult; 
         if (strResult.length() == maxLength) { 
         System.out.println(strResult.length()); 
         System.out.println(strResult); 
         } 

            length ++;            
            lcs(i-1,j-1,x,b,strResult); 

        } 
        else if(b[i][j]==2) 
        { 
             
            lcs(i-1,j,x,b,strResult); 
             
        } 
        else if(b[i][j]==3) 
        { 
            lcs(i,j-1,x,b,strResult); 
        } 
        else if(b[i][j]==4)
        {
            lcs(i-1,j,x,b,strResult); 
            lcs(i,j-1,x,b,strResult); 
        }      
  
 
  
 
    } 
}  
  
 
   
  
//        ，       ，    
  
関連知識は以下の通りです.
問題の説明
1つの所与のシーケンスのサブシーケンスは、そのシーケンスからいくつかの要素を削除したシーケンスである.正確には、所与のシーケンスX=である場合、他のシーケンスZ=がXであるサブシーケンスは、すべてのj=1,2に対して、...kにXij=Zjがあるように、厳密に増加する下付きシーケンスが存在することを意味する.
例えば、シーケンスZ=は、シーケンスX=のサブシーケンスであり、対応する増分下付きシーケンスは<2,3,5,7>である。
2つのシーケンスXおよびYが与えられ、別のシーケンスZがXのサブシーケンスであり、Yのサブシーケンスである場合、ZはシーケンスXおよびYの共通のサブシーケンスである。たとえば、X=とY=、シーケンスはXとYの共通のサブシーケンスであり、シーケンスもXとYの共通のサブシーケンスである。さらに、後者は、XおよびYが4より長い共通サブシーケンスを持たないため、XおよびYの最も長い共通サブシーケンスである。
最長共通サブシーケンス(LCS)問題:2つのシーケンスX=とY=が与えられ、XとYの最長共通サブシーケンスを見つける必要がある。
最長共通サブシーケンス問題LCS
問題の説明
参考解答
ダイナミックプランニングアルゴリズムは、この問題を効果的に解決します。次に,動的計画アルゴリズム設計の各ステップに従って,この問題を解く有効なアルゴリズムを設計する.
1.最長共通サブシーケンスの構成
最長共通サブシーケンス問題を解く際に最も容易に考えられるアルゴリズムは,Xの各サブシーケンスに対してYのサブシーケンスであるか否かを検査し,XとYの共通サブシーケンスであるか否かを決定し,検査中に最長の共通サブシーケンスを選択する窮挙探索法である.Xのすべてのサブシーケンスを検査した後,XとYの最長共通サブシーケンスを求めることができる.Xの1つのサブシーケンスは、下付きシーケンス{1,2,...,m}の1つのサブシーケンスに対応するため、Xは2 mの異なるサブシーケンスを共有し、探索法を窮挙するには指数時間がかかる。
実際,最長共通サブシーケンス問題にも最適サブ構造特性がある。なぜなら,我々には以下の定理があるからである。
定理:LCSの最適サブ構造特性
シーケンスX=とY=の最長共通サブシーケンスZ=を設定すると、次のようになります。
xm=ynの場合、zk=xm=ynであり、Zk−1はXm−1およびYn−1の最長共通サブシーケンスである。
xm≠ynかつzk≠xmの場合、ZはXm−1およびYの最長共通サブシーケンスである。
xm≠ynかつzk≠ynの場合、ZはXおよびYn−1の最長共通サブシーケンスである。
ここでXm−1＝，Yn−1＝，Zk−1＝である。
アテステーション
反証法を用いる。zk≠xmであれば、XとYの長さがk十1の共通サブシーケンスである。これはZがXとYの最も長い共通サブシーケンスであることと矛盾している。したがって、必ずzk=xm=ynがあります。このことから、Zk−1は、Xm−1およびYn−1の長さk−1の共通サブシーケンスであることが分かる。Xm−1およびYn−1の長さがk−1より大きい共通サブシーケンスWがある場合、xmをその末尾に加算すると、XおよびYの長さがkより大きい共通サブシーケンスが生成される。これは矛盾です。従って、Zk−1はXm−1およびYn−1の最も長い共通サブシーケンスである。
zk≠xmのため、ZはXm−1およびYの共通のサブシーケンスである。Xm−1およびYの長さがkより大きい共通サブシーケンスWがある場合、WもXおよびYの長さがkより大きい共通サブシーケンスである。これはZがXとYの最も長い共通サブシーケンスであることと矛盾している。これにより、ZはXm−1およびYの最も長い共通サブシーケンスであることが分かる。
と2.類似しています。
この定理は,2つのシーケンスの最長共通サブシーケンスが,この2つのシーケンスの接頭辞の最長共通サブシーケンスを含むことを示す。従って,最長共通サブシーケンス問題は最適サブ構造特性を有する。
2.サブ問題の再帰構造
最長共通サブシーケンス問題の最適サブ構造特性から分かるように、X=およびY=の最長共通サブシーケンスを探し出すには、xm=ynの場合、Xm−1およびYn−1の最長共通サブシーケンスを探し出し、その後、その末尾にxm(=yn)を加えることでXおよびYの最長共通サブシーケンスを得ることができる。xm≠ynの場合,Xm−1とYの最長共通サブシーケンスとXとYn−1の最長共通サブシーケンスを見つけるという2つのサブ問題を解く必要がある。この2つの共通サブシーケンスのうち、長者はXおよびYの最も長い共通サブシーケンスである。
これにより,再帰構造は,最長共通サブシーケンス問題がサブ問題の重なり特性を有することを容易に見ることができる。例えば、XおよびYの最長共通サブシーケンスを計算する場合、XおよびYn−1およびXm−1およびYの最長共通サブシーケンスを計算することができる。この2つのサブ問題は、Xm−1およびYn−1の最長共通サブシーケンスを計算する共通サブ問題を含む。
行列連積最適計算順序問題と同様に,サブ問題の最適値の再帰関係を確立した。シーケンスXiおよびYjの最長共通サブシーケンスの長さをc[i,j]で記録する。ここでXi=,Yj=である.i=0またはj=0の場合、空のシーケンスはXiおよびYjの最長共通サブシーケンスであるため、c[i,j]=0となる。その他の場合、定理によって再帰関係を確立できるのは以下の通りである。
3.最適値の計算
(2.2)式を直接利用すると,c[i,j]を計算する再帰アルゴリズムが容易に書けるが,その計算時間は入力長指数とともに増加する.考慮したサブ問題空間では,全部でθ(m*n)個の異なるサブ問題であるため,動的計画アルゴリズムを用いて最適値を底から上へ計算することでアルゴリズムの効率を向上させることができる.
最長共通サブシーケンス長を計算する動的計画アルゴリズムLCS_LENGTH(X,Y)はシーケンスX=とY=を入力とする.2つの配列c[0..m,0..n]とb[1..m,1..n]を出力する。ここで、c[i,j]は、XiとYjの最長共通サブシーケンスの長さを格納し、b[i,j]レコードは、c[i,j]の値がどのサブ問題の解によって達成されるかを示し、これは、最長共通サブシーケンスを構築する際に用いられる。最後に,XとYの最長共通サブシーケンスの長さをc[m,n]に記録した。
Procedure LCS_LENGTH(X,Y);begin m:=length[X]; n:=length[Y]; for i:=1 to m do c[i,j]:=0; for j:=1 to n do c[0,j]:=0; for i:=1 to m do for j:=1 to n do if x[i]=y[j] then begin c[i,j]:=c[i-1,j-1]+1; b[i,j]:="↖"; end else if c[i-1,j]≥c[i,j-1] then begin c[i,j]:=c[i-1,j]; b[i,j]:="↑"; end else begin c[i,j]:=c[i,j-1]; b[i,j]:="←" end; return(c,b);end; 
各配列単位の計算にかかるΟ(1)時間,アルゴリズムLCS_LENGTH消費時間Ο(mn)。 
4.最長共通サブシーケンスの構築
アルゴリズムLCS_LENGTH計算により得られた配列bは、シーケンスX=およびY=の最長共通サブシーケンスを迅速に構築するために使用することができる。まずb[m,n]から始まり,その中の矢印が指す方向に沿って配列bを探索する.b[i,j]で「↖」の場合、XiとYjを表す最長共通サブシーケンスは、Xi−1とYj−1の最長共通サブシーケンスに末尾にxiを加えたサブシーケンスであり、b[i,j]で「↑」に遭遇した場合、XiとYjの最長共通サブシーケンスとXi−1とYjの最長共通サブシーケンスが同一であることを示し、b[i,j]で「←」に遭遇した場合、XiとYjの最長共通サブシーケンスとXiとYj−1の最長共通サブシーケンスが同一であることを示す。
以下のアルゴリズムLCS(b,X,i,j)は、bの内容に従ってXiとYjの最長共通サブシーケンスを印刷することを実現する。アルゴリズムの呼び出しLCS(b,X,length[X],length[Y])により、シーケンスXとYの最長共通サブシーケンスを印刷することができる。
Procedure LCS(b,X,i,j);begin if i=0 or j=0 then return; if b[i,j]="↖"then begin LCS(b,X,i-1,j-1);print(x[i];{印刷x[i]}end else if b[i,j]="↑"then LCS(b,X,i-1,j)
else LCS(b,X,i,j-1);end; 
アルゴリズムLCSでは、再帰呼び出し毎にiまたはjが1だけ減算されるので、アルゴリズムの計算時間はO(m+n)となる。
例えば、与えられた2つのシーケンスをX=とするとY=です。アルゴリズムLCS_LENGTHとLCSで算出した結果を図2に示す。
　 
j 0 1 2 3 4 5 6 
i yj B D C A B A 
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ 
0 xi │ 0 0 0 0 0 0 │ 
│ ↑ ↑ ↑ ↖ ↖ │ 
1 A │ 0 0 0 0 1 ← 1 1 │ 
│ ↖ ↑ ↖ │ 
2 B │ 0 1 ← 1 ← 1 1 2 ← 2 │ 
│ ↑ ↑ ↖ ↑ ↑ │ 
3 C │ 0 1 1 2 ← 2 2 2 │ 
│ ↖ ↑ ↑ ↑ ↖ │ 
4 B │ 0 1 1 2 2 3 ← 3 │ 
│ ↑ ↖ ↑ ↑ ↑ ↑ │ 
5 D │ 0 1 2 2 2 3 3 │ 
│ ↑ ↑ ↑ ↖ ↑ ↖ │ 
6 A │ 0 1 2 2 3 3 4 │ 
│ ↖ ↑ ↑ ↑ ↖ ↑ │ 
7 B │ 0 1 2 2 3 4 5 │ 
└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ 
図2アルゴリズムLCSの計算結果
5.アルゴリズムの改善
1つの具体的な問題に対して、一般的なアルゴリズム設計戦略に従って設計されたアルゴリズムは、アルゴリズムの時間と空間の需要において改善されることが多い。このような改善は、通常、具体的な問題のいくつかの特殊性を利用する。
例えば、アルゴリズムLCS_LENGTHおよびLCSでは、配列bをさらに省くことができる。実際、配列要素c[i,j]の値は、c[i−1,j−1],c[i−1,j]およびc[i,j−1]の3つの値の1つのみによって決定され、配列要素b[i,j]も、c[i,j]がどの値によって決定されるかを示すためにのみ使用される。したがって、アルゴリズムLCSでは、配列bを用いずに、配列c自体を用いてc[i,j]の値がc[i−1,j−1],c[i−1,j]およびc[i,j−1]のいずれの数値要素によって決定されるかを一時的に判断することができる。Ο(1)時間。bがアルゴリズムLCSに必要でない以上、アルゴリズムLCS_LENGTHは保存する必要はありません。これで節約できるθ(mn)のスペースで、LCS_LENGTHとLCSに必要な時間はそれぞれΟ(mn)とΟ(m+n)。ただし、配列cはまだ必要であるΟ(mn)の空間,従ってここで行った改良は,空間複雑性の定数因子上の改良にすぎない。
さらに、最長共通サブシーケンスの長さを計算するだけであれば、アルゴリズムの空間的要件を大幅に低減することができる。実際,c[i,j]を計算する際には,配列cのi行目とi−1行目にのみ用いられる.したがって,2行の配列空間であれば最長共通サブシーケンスの長さを算出できる.さらにさらなる分析は、空間的要件をmin(m,n)に減らすこともできる。
上記の内容は以下のとおりです。http://blog.sina.com.cn/s/blog_48969478010007hn.html 
  
 である