算法笔记 12_最长公共子序列问题(动态规划算法)


一、问题描述:

   最长公共子序列问题: 给定两个序列 X = {x1, x2,x3,....,xm} 和 Y = {y1,y2,y3,....,yn} ,找出 X 和 Y 的最长公共子序列。

二、动态规划算法思想:

   求解LCS问题,不能使用暴力搜索方法。一个长度为n的序列拥有 2的n次方个子序列,它的时间复杂度是指数阶,太恐怖了。解决LCS问题,需要借助动态规划的思想。
   动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。

三、问题分析

1、此时我们不妨设 A=“a0,a1,…,am”,B=“b0,b1,…,bn”,并且设 Z=“z0,z1,…,zk”为它们的最长公共子序列。那么很简单的可以想到如下两种情况: 
① 假如 A 的最后一个元素与 B 的最后一个元素相同,那么 A 和 B 的 LCS(最长公共子序列)就等于:{序列 A 去掉最后一个元素} 与 {序列 B 去掉最后一个元素} 的 LCS 再加上 A 和 B 的最后一个相同的元素。 
② 假如 A 的最后一个元素与 B 的最后一个元素不同,那么 A 和 B 的 LCS 就等于:{序列 A 去掉最后一个元素} 与序列 B 的 LCS, {序列 B 去掉最后一个元素} 与序列 A 的 LCS,这俩当中最大的那个序列就是最长公共子序列。

2、① 在程序中我们引进一个二维数组 c[][] 来记录序列 A 与序列 B 的 LCS 的长度,再引进一个 b[i][j] 记录 c[i][j] 是通过哪一个子问题的值求得的,以决定搜索的方向。 
② 我们是自底向上进行递推计算,那么在计算 c[i,j] 之前,c[i-1][j-1],c[i-1][j] 与 c[i][j-1] 均已计算出来。此时我们根据 A[i] = B[j] 还是 A[i] != B[j],就可以计算出 c[i][j] 。 
③ 此问题递归公式: 
happysneaker.com

四、C++实现

#include<iostream>
using namespace std;

#define MAXLEN 50

//参数c[][]用来存储最长公共子序列,b[][]用来存储c[][]的值究竟是由哪种情况得到的
//此函数的作用就是计算出b[][]的值,然后在PrintLCS()函数中作为参数来进行情况选择计算
void LCSLength(char *A, char *B, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
    int i, j;    
    
    //公式中第一种情况
    for(i = 1; i <= m; i++) c[i][0] = 0;    
    for(j = 1; j <= n; j++) c[0][j] = 0;    
    
    for(i = 1; i <= m; i++)
    {
        for(j = 1; j <= n; j++)
        {   
            //公式中第二种情况
            if(A[i-1] == B[j-1]) //如果俩序列最后一个元素相同
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1; //此时设为情况1
            }            //公式中第三种情况
            else if(c[i-1][j] >= c[i][j-1])
            {
                c[i][j] = c[i-1][j]; //两者中选择较大的那个,下同
                b[i][j] = 2; //此时设为情况2
            }            else
            {
                c[i][j] = c[i][j-1];
                b[i][j] = 3; //此时设为情况3
            }
        }
    }
}
        
        
//打印结果函数(此函数内部不断调用自己本身,从最后一个元素A[i-1]最终会调用到第一个元素,每一次使 i或j 减1,因此时间复杂度为O(m+n),即俩序列的长度之和)
//因此实际的运行过程并不是一次直接打印出结果,而是一个一个地输出符合条件的值,即递归调用
void PrintLCS(int b[][MAXLEN], char *A, int i, int j)
{
    //如果序列 A 和 B 的长度为0,也就是无输入的话
    if(i == 0 || j == 0) return;    
    
    //如果是第一种情况
    if(b[i][j] == 1)
    {
        PrintLCS(b, A, i-1, j-1);        
        cout << A[i-1];
    }    
        
    //如果是第二种情况,此种情况运行为什么没有cout输出呢,因为这里是找相同的元素,所以不断向前找,直到找到符合情况1的值,才会有输出
    else if(b[i][j] == 2) PrintLCS(b, A, i-1, j);    
    
    //如果是第三种情况
    else PrintLCS(b, A, i, j-1);
}
    
//主函数int main()
{
    while(1){
        int i, m, n;        
        char A[MAXLEN];        
        char B[MAXLEN];        
        
        //读取用户输入的序列 A 和 B 的内容
        cout << "Please input each elements of sequence A: " << endl; 
        cin >> A;        
        cout << "Please input each elements of sequence B: " << endl;            
        cin >> B;        
        
        int b[MAXLEN][MAXLEN];        
        int c[MAXLEN][MAXLEN];        
        
        //分别读取俩序列 x 和 y 的长度
        m = strlen(A);
        n = strlen(B);

        LCSLength(A, B, m, n, c, b);        
        cout << "The LCS is: ";
        PrintLCS(b, A, m, n);        
        cout << endl;        
        cout << "-----------------------------------------------------------" << endl;
    }  

    return 0;
}


happysneaker.com

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论