首页资源分类其它科学普及 > 最长公共子序列问题

最长公共子序列问题

已有 445023个资源

下载专区

文档信息举报收藏

标    签:最长公共子序列

分    享:

文档简介

最长公共子序列问题详解,用VC++编写,含源码

文档预览

 最长公共子序列 一、问题概述 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切的说,若给定序列X={x1, x2, … , xm},则另一个序列Z={z1, z2, … , zk},是X的子序列是指存在一个严格递增下标序列{i1, i2, … , ik}使得对于所有j=1, 2, …, k有:zj=xij。 给定两个序列X= { x1, x2, …, xm}和Y= {y1, y2, … , yn},要求找出X和Y的一个最长公共子序列。 二、具体分析 既然说是动态规划,那我们首先要考虑的就是怎么划分子问题,一般对于前面讲到的街道问题和数塔问题涉及走向的,考虑子问题时当然是想上一步是什么?但这个问题没有涉及走向,也没有所谓的上一步,该怎么办呢? 既然是求公共子序列,也就有第一个序列的第i个字符和第二个序列的第j个字符相等的情况。 那么我们枚举第一个序列(X)的字符,和第二个序列(Y)的字符。 显然如果X[i]=Y[j]那么起点是1(下面说的子序列都是起点为1的),长度为i的子序列和长度为j的子序列的最长公共子序列就是长度为i-1和长度为j-1 的子序列中最长的公共子序列加上X[i]或Y[j]。 那要是不相等呢? 如果不相等,也就是说第一个序列长度为I的子序列和第二个序列中长度为j的子序列的公共子序列中X[i]和Y[j]不同时出现。也就是说第一个序列长度为i的子序列和第二个序列中长度为j的子序列的公共子序列是第一个序列长度为i的子序列和第二个序列中长度为j-1的子序列或第一个序列长度为i-1的子序列和第二个序列中长度为j的子序列的公共子序列中一个更长的。 给定两个序列 X = { x1 , x2 , ... , xm } Y = { y1 , y2 , ... , yn } 求X和Y的一个最长公共子序列 举例: X = { I,A,D,G,J,K } Y = { K,A,S,D,F,G,H,J,K,L } 最长公共子序列为 LSC = { A,D,G,J,K } 分析: 最长公共子序列问题具有最优子结构性质 设: X = { x1 , ... , xm } Y = { y1 , ... , yn } 及它们的最长子序列 Z = { z1 , ... , zk } 则 1、若 xm = yn , 则 zk = xm = yn,且Z[k-1] 是 X[m-1] 和 Y[n-1] 的最长公共子序列; 2、若 xm != yn ,且 zk != xm , 则 Z 是 X[m-1] 和 Y 的最长公共子序列; 3、若 xm != yn , 且 zk != yn , 则 Z 是 Y[n-1] 和 X 的最长公共子序列。 由性质导出子问题的递归结构 当 i = 0 , j = 0 时 , c[i][j] = 0; 当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1; 当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }。 三、算法实现 1、计算最长公共子序列长度的动态规划算法LCSLength以序列X={x1, x2, … , xm}和Y={y1, y2, … ,yn}作为输入,输出二维数组c和一位数组b。其中c[i][j]存储Xi和Yj的最长公共子序列的长度,b[k]记录c[i][j]的值是由哪一个子问题的解得到的,这个构造最长公共子序列时要用到。问题的最优值,即X和Y的最长公共子序列的长度记录于total(c[m][n]=total)中。 void LCSLength( int m , int n , char *x , char *y , char *b ) { int i , j , k; int c[max][max]; memset(c,0,sizeof(c));//数组c初始化为0; for( i = 1 ; i <= m ; i++ ) { for( j = 1 ; j <= n ; j++ ) { if( x[i-1] == y[j-1] ) { c[i][j] = c[i-1][j-1] + 1; k = i * ( n + 1 ) + j; b[k] = '\\'; } else if( c[i-1][j] >= c[i][j-1] ) { c[i][j] = c[i-1][j]; k = i * ( n + 1 ) + j; b[k] = '|'; } else { c[i][j] = c[i][j-1]; k = i * ( n + 1 ) + j; b[k] = '-'; } } } } 2、由算法LCSLength计算得到的数组b可用于快速构造序列X={x1, x2, … , xm}和Y={y1, y2, … ,yn}的最长公共子序列。当在b[k] = '\\'是,表示Xi和Yi的最长公共子序列是由Xi-1和Yj-1的最长公共子序列在尾部加上xi所得到的子序列。当b[k] = '|'时,表示Xi和Yi的最长公共子序列与Xi-1和Yj的最长公共子序列相同。当b[k] = '-'时,表示Xi和Yi的最长公共子序列与Xi和Yj-1的最长公共子序列相同。 void LCS( int i , int j , char *x , char *b , int width ) { if( i == 0 || j == 0 ) return; int k = i * ( width + 1 ) + j; if( b[k] == '\\' ) { LCS( i - 1 , j - 1 , x , b , width ); fout<= c[i][j-1] ) { c[i][j] = c[i-1][j]; } else { c[i][j] = c[i][j-1]; } } } } 2、算法LCS的改进 void LCS( int i , int j , char *x , int c[max][max] ) { if( i == 0 || j == 0 ) return; if(c[i][j] == c[i-1][j-1] + 1 ) { LCS( i - 1 , j - 1 , x , c ); fout<= c[i][j-1] ) { LCS( i - 1 , j , x , c ); } else { LCS( i , j - 1 , x ,c); } } 附录 #include #include #include using namespace std; #define max 100 ifstream fin("LCSIN.txt"); ofstream fout("LCSOUT.txt"); int total=0; void LCSLength( int m , int n , char *x , char *y , char *b ) { int i , j , k; int c[max][max]; memset(c,0,sizeof(c));//数组c初始化为0; for( i = 1 ; i <= m ; i++ ) { for( j = 1 ; j <= n ; j++ ) { if( x[i-1] == y[j-1] ) { c[i][j] = c[i-1][j-1] + 1; k = i * ( n + 1 ) + j; b[k] = '\\'; } else if( c[i-1][j] >= c[i][j-1] ) { c[i][j] = c[i-1][j]; k = i * ( n + 1 ) + j; b[k] = '|'; } else { c[i][j] = c[i][j-1]; k = i * ( n + 1 ) + j; b[k] = '-'; } } } } void LCS( int i , int j , char *x , char *b , int width ) { if( i == 0 || j == 0 ) return; int k = i * ( width + 1 ) + j; if( b[k] == '\\' ) { LCS( i - 1 , j - 1 , x , b , width ); fout<>x>>y; int m,n; m = strlen(x); n = strlen(y); char b[max]; memset(b,'0',sizeof(b)); LCSLength( m , n , x , y , b ); LCS( m , n , x , b , n ); cout<

Top_arrow
回到顶部
EEWORLD下载中心所有资源均来自网友分享,如有侵权,请发送举报邮件到客服邮箱bbs_service@eeworld.com.cn 或通过站内短信息或QQ:273568022联系管理员 高员外,我们会尽快处理。