1、精選優(yōu)質(zhì)文檔-傾情為你奉上問題描述：一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=  x1, x2, xm，則另一序列Z= z1, z2, zk是X的子序列是指存在一個嚴格遞增的下標序列 i1, i2, ik，使得對于所有j=1,2,k有 Xij=Zj。例如，序列Z=B,C,D,B是序列X=A,B,C,B,D,A,B的子序列，相應(yīng)的遞增下標序列為2,3,5,7。給定兩個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如，若X=  A, B, C, B, D, A, B和Y= B, D, C

2、, A, B, A，則序列B,C,A是X和Y的一個公共子序列，序列B,C,B,A也是X和Y的一個公共子序列。而且，后者是X和Y的一個最長公共子序列，因為X和Y沒有長度大于4的公共子序列。給定兩個序列X= x1, x2, , xm和Y= y1, y2, , yn，要求找出X和Y的一個最長公共子序列。     問題解析：設(shè)X= A, B, C, B, D, A, B,Y= B, D, C, A, B, A。求X，Y的最長公共子序列最容易想到的方法是窮舉法。對X的多有子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列。由集合的性質(zhì)知

3、，元素為m的集合共有2m個不同子序列，因此，窮舉法需要指數(shù)級別的運算時間。進一步分解問題特性，最長公共子序列問題實際上具有最優(yōu)子結(jié)構(gòu)性質(zhì)。      設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk。則有：      (1)若xm=yn,則zk=xm=yn,且zk-1是Xm-1和Yn-1的最長公共子序列。      (2)若xm!=yn且zk!=xm，則Z是Xm-1和Y的最長公共子序列。  

4、;    (3)若xm!=yn且zk!=yn，則Z是X和Yn-1的最長公共子序列。      其中，Xm-1=x1,x2xm-1，Yn-1=y1,y2yn-1,Zk-1=z1,z2zk-1。     遞推關(guān)系：用cij記錄序列Xi和Yj的最長公共子序列的長度。其中，Xi=x1,x2xi，Yj=y1,y2yj。當(dāng)i=0或j=0時，空序列是xi和yj的最長公共子序列。此時，cij=0；當(dāng)i,j>0，xi=yj時，cij=ci-1j-1+1；當(dāng)i,j>0，xi!=yj時，cij=

5、maxcij-1,ci-1j，由此建立遞推關(guān)系如下：          構(gòu)造最優(yōu)解：由以上分析可知，要找出X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列,可以按一下方式遞歸進行：當(dāng)xm=yn時，找出xm-1和yn-1的最長公共子序列，然后在尾部加上xm(=yn)即可得X和Y的最長公共子序列。當(dāng)Xm!=Yn時，必須解兩個子問題，即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者為X和Y的最長公共子序列。設(shè)數(shù)組bij記錄cij的值由哪一個子

6、問題的解得到的，從bmn開始，依其值在數(shù)組b中搜索，當(dāng)bij=1時，表示Xi和Yj的最長公共子序列是由Xi-1和Yj-1的最長公共子序列在尾部加上xi所得到的子序列。當(dāng)bij=2時，表示Xi和Yj的最長公共子序列與Xi-1和Yj-1的最長公共子序列相同。當(dāng)bij=3時，表示Xi和Yj的最長公共子序列與Xi和Yj-1的最長公共子序列相同。     代碼如下：cpp  1. /3d3-1 最長公共子序列問題  2. #include "stdafx.h"  3

7、. #include <iostream>   4. using namespace std;   5.   6. const int M = 7;  7. const int N = 6;  8.   9. void output(char *s,int n);  10. void&#

8、160;LCSLength(int m,int n,char *x,char *y,int *c,int *b);  11. void LCS(int i,int j,char *x,int *b);  12.   13. int main()  14.   15.     /X=A,B,C,B,D,A,B  16.

9、    /Y=B,D,C,A,B,A  17.     char x = ' ','A','B','C','B','D','A','B'  18.     char y = ' ','B','

10、D','C','A','B','A'  19.   20.     int *c = new int *M+1;  21.     int *b = new int *M+1;  22.     for(int i=0

11、;i<=M;i+)    23.         24.         ci = new intN+1;  25.         bi = new intN+1;  26.    

12、    27.       28.     cout<<"序列X："<<endl;  29.     output(x,M);  30.     cout<<"序列Y："<<endl;  31.    

13、 output(y,N);  32.   33.     LCSLength(M,N,x,y,c,b);  34.   35.     cout<<"序列X、Y最長公共子序列長度為："<<cMN<<endl;  36.     cout<<"序列X、Y最長公共子序列為："<&

14、lt;endl;  37.     LCS(M,N,x,b);  38.     cout<<endl;  39.   40.   41. void output(char *s,int n)  42.   43.     for(int i=1; i<=n; 

15、i+)  44.       45.         cout<<si<<" "  46.       47.     cout<<endl;  48.   49.   50. void

16、0;LCSLength(int m,int n,char *x,char *y,int *c,int *b)  51.   52.     int i,j;  53.   54.     for(i=1; i<=m; i+)  55.        &#

17、160;ci0 = 0;  56.     for(i=1; i<=n; i+)  57.         c0i = 0;  58.   59.     for(i=1; i<=m; i+)  60.    

18、0;  61.         for(j=1; j<=n; j+)  62.           63.             if(xi=yj)  64.     &#

19、160;         65.                 cij=ci-1j-1+1;  66.                 bij=1; 

20、0;67.               68.             else if(ci-1j>=cij-1)  69.               70. &

21、#160;               cij=ci-1j;  71.                 bij=2;  72.           &

22、#160;   73.             else  74.               75.                

23、60; cij=cij-1;  76.                  bij=3;  77.               78.          

24、; 79.       80.   81.   82. void LCS(int i,int j,char *x,int *b)  83.   84.     if(i=0 | j=0)  85.       86.    

25、60;    return;  87.       88.     if(bij=1)  89.       90.         LCS(i-1,j-1,x,b);  91.       

26、0; cout<<xi<<" "  92.       93.     else if(bij=2)  94.       95.         LCS(i-1,j,x,b);  96.    

27、   97.     else  98.       99.         LCS(i,j-1,x,b);  100.       101.             &

28、#160; LCSLength函數(shù)在計算最優(yōu)值時，分別迭代X，Y構(gòu)造數(shù)組b,c。設(shè)數(shù)組每個元素單元計算耗費時間O(1)，則易得LCSLength的時間復(fù)雜度為O(mn)。在算法LCS中，依據(jù)數(shù)組b的值回溯構(gòu)造最優(yōu)解，每一次遞歸調(diào)用使i，或j減小1。從而算法的計算時間為O(m+n)。LCS的回溯構(gòu)造最優(yōu)解過程如下圖所示:            算法的改進：對于一個具體問題，按照一般的算法設(shè)計策略設(shè)計出的算法，往往在算法的時間和空間需求上還可以改進。這種改進，通常是利用

29、具體問題的一些特殊性。例如，在算法LCS_length和LCS中，可進一步將數(shù)組b省去。事實上，數(shù)組元素ci,j的值僅由ci-1j-1，ci-1j和cij-1三個值之一確定，而數(shù)組元素bij也只是用來指示cij究竟由哪個值確定。因此，在算法LCS中，我們可以不借助于數(shù)組b而借助于數(shù)組c本身臨時判斷cij的值是由ci-1j-1，ci-1j和cij-1中哪一個數(shù)值元素所確定，代價是(1)時間。既然b對于算法LCS不是必要的，那么算法LCS_length便不必保存它。這一來，可節(jié)省(mn)的空間，而LCS_length和LCS所需要的時間分別仍然是(mn)和(m+n)。另外，如果只需要計算最長公共子

30、序列的長度，則算法的空間需求還可大大減少。事實上，在計算cij時，只用到數(shù)組c的第i行和第i-1行。因此，只要用2行的數(shù)組空間就可以計算出最長公共子序列的長度。更進一步的分析還可將空間需求減至min(m, n)。cpp  1. /3d3-2 最長公共子序列問題  2. #include "stdafx.h"  3. #include <iostream>   4. using namespace std; 

31、0; 5.   6. const int M = 7;  7. const int N = 6;  8.   9. void output(char *s,int n);  10. void LCSLength(int m,int n,char *x,char *y,int *c);  11. vo

32、id LCS(int i,int j,char *x,int *c);  12.   13. int main()  14.   15.     /X=A,B,C,B,D,A,B  16.     /Y=B,D,C,A,B,A  17.     char x = 

33、9; ','A','B','C','B','D','A','B'  18.     char y = ' ','B','D','C','A','B','A'  19.   20.    &

34、#160;int *c = new int *M+1;  21.     for(int i=0;i<=M;i+)    22.         23.         ci = new intN+1;  24.  

35、;      25.       26.     cout<<"序列X："<<endl;  27.     output(x,M);  28.     cout<<"序列Y："<<endl;  29.  

36、;   output(y,N);  30.   31.     LCSLength(M,N,x,y,c);  32.   33.     cout<<"序列X、Y最長公共子序列長度為："<<cMN<<endl;  34.     cout<<"序列X、Y最長公共子序列為：

37、"<<endl;  35.     LCS(M,N,x,c);  36.     cout<<endl;  37.   38.   39. void output(char *s,int n)  40.   41.     for(int i=1; i&l

38、t;=n; i+)  42.       43.         cout<<si<<" "  44.       45.     cout<<endl;  46.   47.   4

39、8. void LCSLength(int m,int n,char *x,char *y,int *c)  49.   50.     int i,j;  51.   52.     for(i=1; i<=m; i+)  53.        

40、60;ci0 = 0;  54.     for(i=1; i<=n; i+)  55.         c0i = 0;  56.   57.     for(i=1; i<=m; i+)  58.     

41、;  59.         for(j=1; j<=n; j+)  60.           61.             if(xi=yj)  62.     

42、60;         63.                 cij=ci-1j-1+1;  64.               65.     &

43、#160;       else if(ci-1j>=cij-1)  66.               67.                 cij=ci-1j;  68

44、.               69.             else  70.               71.      

45、            cij=cij-1;  72.               73.           74.       75.  

46、0;76.   77. void LCS(int i,int j,char *x,int *c)  78.   79.     if(i=0 | j=0)  80.       81.         return;  82.   

47、;    83.     if(cij=ci-1j-1+1)  84.       85.         LCS(i-1,j-1,x,c);  86.         cout<<xi<<" " 

48、; 87.       88.     else if(ci-1j>=cij-1)  89.       90.         LCS(i-1,j,x,c);  91.       92.    

49、60;else  93.       94.         LCS(i,j-1,x,c);  95.       96.            運行結(jié)果如下：        &#

50、160;     從運行結(jié)果中可以看出，算法LCS回溯算法僅僅打印了其中一條最大公共子序列，如果存在多條公共子序列的情況下。怎么解決？對bij二維數(shù)組的取值添加一種可能，等于4，這代表了我們說的這種多支情況，那么回溯的時候可以根據(jù)這個信息打印更多可能的選擇。你從（7,6)點開始按bij的值指示的方向回溯，把所有的路徑遍歷一遍，如果是能達到起點（1,1)的路徑，就是LCS了，有多少條打印多少條?？墒?，在回溯路徑的時候，如果采用一般的全搜索，會進行了很多無用功。即重復(fù)了很多，且會遍歷了一些無效路徑，因為這些路徑最終不會到達終點(1,1)，因此加大算法復(fù)雜度和

51、時間消耗。      博文給出了一種"矩行搜索"的解決辦法降低了算法的復(fù)雜度。算法主要是利用兩個棧store,print，一個用來儲存節(jié)點，一個用來打印節(jié)點。      棧的實現(xiàn)代碼如下(文件Stack.h)：cpp  1. /*  2.   頭文件-head file  3.  */    4.   5.

52、template <class T>  6. class StackNode  7.     public:  8.         T data;  9.         StackNode *next;  10. ; 

53、60;11.   12. template <class T>  13. class Stack  14.     public:  15.         Stack(void):top(NULL)  16.         bool IsEmp

54、ty(void) const return top=NULL;  17.         void Push(const T data);  18.         bool Pop(T *data);  19.        &

55、#160;bool Peek(T *data) const;  20.         StackNode<T> * GetStackNode();  21.     private:  22.         StackNode<T> *top;

56、0; 23. ;  24.   25. template <class T>  26. StackNode<T> * Stack<T>:GetStackNode()  27.     return top;  28.   29.   30. template <class T> &

57、#160;31. void Stack<T>:Push(const T data)  32.     StackNode<T> *node = new StackNode<T>();  33.     node->data = data;  34.     node->next&#

58、160;= top;  35.     top = node;  36.   37.   38. template <class T>  39. bool Stack<T>:Peek(T *data) const  40.     if(IsEmpty() return fa

59、lse;  41.     *data = top->data;  42.     return true;  43.   44.   45. template <class T>  46. bool Stack<T>:Pop(T *data)  47.   

60、  if(IsEmpty() return false;  48.     *data = top->data;  49.     StackNode<T> *node = top;  50.     top = top->next;  51.  

61、0;  delete(node);  52.     return true;  53.         所有最長公共子序列問題LCS 矩陣搜索代碼如下：cpp  1. /3d3-3 所有最長公共子序列問題LCS 矩陣搜索  2. #include "stdafx.h"  3. #include&#

62、160;"stack.h"  4. #include <iostream>  5. using namespace std;  6.   7. typedef int *Matrix;  8. const int M = 7;  9. const int N = 6;  10.  

63、60;11. typedef struct _Element  12.   13.     int lcslen;/當(dāng)前節(jié)點的LCS長度  14.     int row;/當(dāng)前節(jié)點的行坐標  15.     int col;/當(dāng)前節(jié)點的列坐標  16. Element;  17.   1

64、8. void output(char *s,int n);  19.   20. Element CreateElement(int nlen, int row, int col);  21.   22. Matrix GreateMatrix(int row, int col);  23. void DeleteMatrix(Matrix p,

65、 int row);  24.   25. void PrintStack(Stack<Element> *ps, char *str, int len);  26. void SearchE(Matrix pb, int curposx, int curposy, int &eposx, int &eposy, int

66、 ntype);  27.   28. void LCSLength(int m,int n,char *x,char *y,Matrix pc,Matrix pb);  29. void LCS(char *x, Matrix pc, Matrix pb, int row, int col);/矩陣搜索回溯  30.  

67、60;31.   32. int main()  33.     char x = ' ','A','B','C','B','D','A','B'  34.     char y = ' ','B','

68、D','C','A','B','A'  35.   36.     Matrix b = GreateMatrix(M, N);  37.     Matrix c = GreateMatrix(M, N);  38.   39.    

69、 LCSLength(M,N,x,y,c,b);  40.   41.     cout<<"序列X："<<endl;  42.     output(x,M);  43.     cout<<"序列Y："<<endl;  44.     o

70、utput(y,N);  45.   46.     cout<<"序列X、Y最長公共子序列長度為："<<cMN<<endl;  47.     cout<<"序列X、Y最長公共子序列為："<<endl;  48.   49.     LCS(x,c,b,M,N); &

71、#160;50.   51.     DeleteMatrix(b,M);  52.     DeleteMatrix(c,M);  53.   54.     return 0;  55.   56.   57. void output(char *s,int n)  58.

72、  59.     for(int i=1; i<=n; i+)  60.       61.         cout<<si<<" "  62.       63.    &#

73、160;cout<<endl;  64.   65.   66. Element CreateElement(int nlen, int row, int col)  67.   68.     Element ele;  69.     ele.lcslen = nlen;  

74、;70.     ele.col = col;  71.     ele.row = row;  72.     return ele;  73.   74.   75. Matrix GreateMatrix(int row, int col)  76.  

75、 77.     Matrix p = new int *row+1;  78.     for(int i=0;i<=row;i+)    79.         80.         pi = ne

76、w intcol+1;  81.        82.     return p;  83.   84.   85. void DeleteMatrix(Matrix p, int row)  86.   87.     for(int i=0;i<=r

77、ow;i+)    88.         89.         delete pi;  90.       91.   92.     delete p;  93.   94.  

78、60;95. void PrintStack(Stack<Element> *s,char *str,int len)  96.   97.     if(s = NULL | str = NULL)  98.         return;  99.    

79、;   100.     StackNode<Element> *sn = s->GetStackNode();  101.   102.     while(sn!=NULL && sn->data.row<=len)  103.       104.  

80、60;      cout<<strsn->data.row<<" "  105.         sn = sn->next;  106.       107.   108.     cout<<en

81、dl;  109.   110.   111. void SearchE(Matrix pb, int curposx, int curposy, int &eposx, int &eposy, int ntype)  112.   113.     switch(pbcurposxcurposy)  

82、114.       115.     case 1:  116.         eposx = curposx;  117.         eposy = curposy;  118.    &

83、#160;    return;  119.     case 2:  120.         SearchE(pb, curposx-1, curposy, eposx, eposy, ntype);  121.         bre

84、ak;  122.     case 3:  123.         SearchE(pb, curposx, curposy-1, eposx, eposy, ntype);  124.         break;  125.   &

85、#160; case 4:  126.         if(ntype = 0)  127.             /搜索e1點，如過碰到分叉點，向上繼續(xù)搜索  128.           &#

86、160; SearchE(pb, curposx-1, curposy, eposx, eposy, ntype);  129.         else  130.             /搜索e2點，如過碰到分叉點，向左繼續(xù)搜索  131.   

87、0;         SearchE(pb, curposx, curposy-1, eposx, eposy, ntype);  132.         break;  133.       134.   135.   136. voi

88、d LCSLength(int m,int n,char *x,char *y,Matrix pc,Matrix pb)  137.   138.     int i,j;  139.   140.     for(i=1; i<=m; i+)  141.     

89、0;   pci0 = 0;  142.     for(i=1; i<=n; i+)  143.         pc0i = 0;  144.   145.     for(i=1; i<=m; i+)  146.

90、       147.         for(j=1; j<=n; j+)  148.           149.             if(xi=yj)  150.

91、               151.                 pcij=pci-1j-1+1;  152.              

92、60;  pbij=1;  153.               154.             else if(pci-1j>pcij-1)  155.          

93、;     156.                 pcij=pci-1j;  157.                 pbij=2;  158.    &

94、#160;          159.             else if(pci-1j<pcij-1)  160.               161.    

95、0;             pcij=pcij-1;  162.                  pbij=3;  163.            

96、;   164.             else  165.               166.                

97、0;pcij = pcij-1;/由左節(jié)點或上節(jié)點轉(zhuǎn)移而來  167.                 pbij = 4;/標記為4  168.               169.    

98、       170.       171.   172.   173. void LCS(char *x, Matrix pc, Matrix pb, int row, int col)  174.   175.     if(x =&#

99、160;NULL | pc = NULL | pb = NULL)  176.         return;  177.       178.     Stack<Element> store, print;/構(gòu)造兩個棧store，print  

100、179.     Element storetop;/store棧的棧頂節(jié)點  180.     Element element;/臨時變量  181.     Element virtualnode;/虛擬節(jié)點  182.     int ntoplen;/保存store棧頂節(jié)點的LCS長度  183.  

101、   int ex1,ey1,ex2,ey2;/矩形搜索的兩個節(jié)點的坐標  184.     int i,j;  185.   186.     virtualnode = CreateElement(pcrowcol+1, row+1, col+1);  187.   188.     

102、store.Push(virtualnode);/壓入虛擬節(jié)點到store  189.   190.     while(!store.IsEmpty()  191.       192.         store.Pop(&storetop);  193.       

103、;  if(storetop.row = 1 | storetop.col = 1)/如果是邊界節(jié)點  194.           195.             print.Push(storetop);  196.    

104、         PrintStack(&print, x, row);/打印print棧里面除虛擬節(jié)點之外的所有節(jié)點  197.             store.Peek(&element);  198.         

105、60;   ntoplen = element.lcslen;/當(dāng)前store的棧頂節(jié)點的LCS長度  199.   200.             /*彈出print棧中所有LCS長度小于等于ntoplen的節(jié)點*/  201.            &#

106、160;while(print.Peek(&element) && element.lcslen<=ntoplen)  202.               203.                 print.Pop(&element);  204.               205.           206.         else  207.