南邮算法分析与设计实验2 动态规划法

动态规划法

实验目的：

加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。                             

实验内容：

用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。

掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。

实验原理及内容（包括操作过程、结果分析等）

1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,xm}和Z={z1,z2,……,zk}，要求找出X和Y的一个最长公共子序列。

 例如：X={a,b,c,b,d,a,b},Z={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。

通过“穷举法”列出所有X的所有子序列，检查其是否为Z的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。

2、分析LCS问题特征可知，设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且xm≠zk，则Z是Xm-1和Y的最长公共子序列；

（3）若xm≠yn且zk≠yn，则Z是X和Y的最长公共子序列。

这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题：

若xm=ym，则进一步分解为求解两个（前缀）子字符序列Xm-1和Yn-1的最长公共子序列问题；

若xm≠yn，则原问题转化为求解两个子问题，即找出Xm-1和Y的最长公共子序列与找出X和Yn-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。

由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。

3、令c[i][j]保存字符序列Xi={x1,x2,……,xi}和Yj={y1,y2,……,yj}的最长公共子序列的长度，由上述分析可得如下递推式：
             0                                i=0或j=0

c[i][j]=   c[i-1][j-1]+1                 i,j>0且xi=yj

            max{c[i][j-1],c[i-1][j]}    i,j>0且xi≠yj

 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，这样可以避免重复计算子问题，在多项式时间内完成计算。

4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。

代码：

#include <iostream>
#include <string>
using namespace std;
int const MaxLen = 50;

class LCS
{

public:
    LCS(int nx, int ny, char *x, char *y) 
    {
        m = nx;
        n = ny;
        a = new char[m + 2];
        b = new char[n + 2];
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for(int i = 0; i < nx + 2; i++)
            a[i + 1] = x[i];
        for(int i = 0; i < ny + 2; i++)
            b[i + 1] = y[i];
        c = new int[MaxLen][MaxLen];
        s = new int[MaxLen][MaxLen];
        memset(c, 0, sizeof(c));
        memset(s, 0, sizeof(s));
  }
  int LCSLength();

  void CLCS()
  {
    CLCS(m, n);
  }

private:
    void CLCS(int i, int j);
    int (*c)[MaxLen], (*s)[MaxLen];
    int m, n;
    char *a, *b;
};

int LCS::LCSLength()
{
    for(int i = 1; i <= m; i++) 
        c[i][0] = 0;
    for(int j = 1; j <= n; j++) 
        c[0][j] = 0;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(a[i] == b[j])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                s[i][j] = 1;
            }
            else if(c[i - 1][j] >= c[i][j - 1])
            {
                c[i][j] = c[i - 1][j];
                s[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i][j - 1];
                s[i][j] = 3;
            }
        }
    }
    return c[m][n];  
}

void LCS::CLCS(int i, int j)
{
    if(i == 0 || j == 0) 
        return;
    if(s[i][j] == 1)
    {
        CLCS(i - 1, j - 1);
        cout << a[i];
    }
    else if(s[i][j] == 2) 
        CLCS(i - 1, j);
    else  
        CLCS(i, j - 1);
}

int main()
{
    int nx, ny;
    char *x = new char[MaxLen], *y = new char[MaxLen];
    cout << "请输入X (不含空格)" << endl;
    scanf("%s", x);
    nx = strlen(x);
    cout << "请输入Y (不含空格)" << endl;
    scanf("%s", y);
    ny = strlen(y);
    LCS lcs(nx, ny, x, y);
    cout << "X和Y最长公共子序列的长度为：" << lcs.LCSLength() << endl;
    cout << "该序列为" << endl;
    lcs.CLCS();
    cout << endl;
    delete []x;
    delete []y;
    return 0;
}

复杂度分析：

int LCSLength()的平均时间复杂度为O()；

void CLCS()的平均时间复杂度为O(nlogn)。

思考题：

1、备忘录方法是动态规划法的一个变种，它采用分治法思想，自顶向下直接递归求最优解。但与分治法不同的是，备忘录方法为每个已经计算的子问题建立备忘录，即保存子问题的计算结果以备需要时应用，从而避免子问题的重复求解。

int LCS::LCSLength(int i, int j)
{
    if(i == 0 || j == 0) 
        return 0;
    if(c[i][j] != 0) 
        return c[i][j];
    else
    {
        if(a[i] == b[j])
        {
            c[i][j] + LCSLength(i - 1, j - 1) + 1;
            s[i][j] = 1;
        }
        else if(LCSLength(i - 1, j) >= LCSLength(i, j - 1))
        {
            c[i][j] = LCSLength(i - 1, j);
            s[i][j] = 2;
        }
        else
        {
          c[i][j] = LCSLength(i, j - 1);
          s[i][j] = 3;
        }
    }
    return c[i][j];
}

2、若省去原程序中的二维数组s，是否还能求的最长公共子序列问题的最优解？请编写一个类似的CLCS算法实现：不借助二维数组s在O(m+n)的时间内构造最长公共子序列的功能。（提示：此时可在当前c[i][j]处比较a[i]和b[j]。如果相等，则调用CLCS(i-1,j-1)，输出a[i]（或b[j]）。如果不相等，则比较c[i-1][j]和c[i][j-1]。若c[i-1][j]≥c[i][j-1],则递归调用CLCS（i-1，j）；否则，递归调用CLCS(i,j-1)。）

void LCS::CLCS(int i, int j)
{
    if(i == 0 || j == 0) 
        return;
    if(a[i] == b[j])
    {
        CLCS(i - 1, j - 1);
        cout << a[i];
    }
    else
    {
        if(c[i - 1][j] >= c[i][j - 1]) 
            CLCS(i - 1, j);
        else 
            CLCS(i, j - 1);
    }
} 

3、如果只需计算最长公共子序列的长度，而无须构造最优解，则如何改进原有程序可以使得算法的空间需求大大减少？请改写原程序，使算法的空间复杂度减少为O(min{m,n})。（提示：计算c[i][j]仅用到第i行和第i-1行元素，因此，只需两行元素空间就可以计算最长公共子序列的长度，并且选用序列长度较短的一个作为y序列，可以缩短每行元素的个数，从而进一步减少空间复杂度。）

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define MAX 50
class LCS
{
public:
    LCS(int nx, int ny, char *x, char *y)
    {
        m = nx;
        n = ny;
        a = new char[m + 1];
        b = new char[n + 1];
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for(int i = 0; i < nx; i++)
            a[i + 1] = x[i];
        for(int i = 0; i < ny; i++)
            b[i + 1] = y[i];
        if(m > n)
        { 
            l = m;
            s = n;
        }
        else
        {
            char *t;
            swap(x, y);
            s = m;
            l = n;
        }
        c1 = new int[s + 1];
        c2 = new int[s + 1];
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));
    }
    int LCSLength();
private:
    int m, n;
    int *c1, *c2;
    int l, s;
    char *a, *b;
};

int LCS::LCSLength()
{
    for(int i = 0; i < s; i++) 
        c1[i] = 0;
    for(int i = 1; i <= l; i++)
    {
        for(int j = 1; j <= s; j++)
        {
            if(a[i] == b[j])
                c2[j] = c1[j - 1] + 1;
            else if(c1[j] >= c2[j - 1])
                c2[j] = c1[j];
            else
                c2[j] = c2[j - 1];
        }
        for(int j = 0; j < s; j++)
            c1[j] = c2[j];
    }
    return c2[s];
}

int main()
{
    int nx, ny;
    char *x, *y;
    x = new char[MAX];
    y = new char[MAX];
    cout << "请输入X (不含空格)" << endl;
    cin >> x;
    nx = strlen(x);
    cout << "请输入Y (不含空格)" << endl;
    cin >> y;
    ny = strlen(y);
    LCS lcs(nx, ny, x, y);
    cout << "X和Y最长公共子序列的长度为：" << lcs.LCSLength() << endl;
    delete []x;
    delete []y;
    return 0;
}

4、思考：若要求输出所有可能的最长公共子序列，该如何修改LCS算法？

   原CLCS函数if (c[i-1][j]>=c[i][j-1])……语句中没有区分c[i-1][j]>c[i][j-1]和c[i-1][j]=c[i][j-1]这两种不同的情况。因此要找出所有LCS，就必须在a[i]!=b[j]且c[i-1][j]==c[i][j-1]的时候，分别沿着c[i-1][j]向上和c[i][j-1]向左两个搜索方向分别构造最优解，才能据此找出所有的LCS。实现时可采用一个solution[]数组来记录最优解向量。）

动态规划法实例：BracketsSequence

Description

Letus define a regular brackets sequence in the following way:

1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.

For example, all of the following sequences of characters are regular bracketssequences:

(), [], (()), ([]), ()[], ()[()]

And all of the following character sequences are not:

(, [, ), )(, ([)], ([(]

Some sequence of characters ‘(‘, ‘)‘, ‘[‘, and ‘]‘ is given. You are to findthe shortest possible regular brackets sequence, that contains the givencharacter sequence as a subsequence. Here, a string a1 a2 ... an is called asubsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 <i2 < ... < in = m, that aj = bij for all 1 = j = n.

Input

Theinput file contains at most 100 brackets (characters ‘(‘, ‘)‘, ‘[‘ and ‘]‘)that are situated on a single line without any other characters among them.

Output

Writeto the output file a single line that contains some regular brackets sequencethat has the minimal possible length and contains the given sequence as asubsequence.

Sample Input

([(]

Sample Output

()[()]

题目大意：给一些括号，求让它们合法最少要加上多少括号，并输出加上后的结果，合法的定义：
1.空串是合法的
2.若S是合法的，则［S］和（S）均是合法的
3.若A和B是合法的，则AB是合法的

题目分析：令dp[i][j]表示使子序列从i到j合法要加的最小括号数
当子序列长度为1时，dp[i][i]= 1
当子序列长度不为1时两个方案：
1）dp[i] == ‘(‘&& dp[j] == ‘)‘或者dp[i]== ‘[‘ && dp[j] == ‘]‘说明最外侧已合法，则要加的括号数由里面的子序列决定即dp[i][j] = dp[i + 1][j - 1]
2）枚举分割点，即i <= k < j，dp[i][j] = min(dp[i][k]，dp[k + 1][j])
这样要添加的最少数量就能得到即dp[0][len - 1]，但是题目要输出序列，因此我们还要记录路径，若s[i] == s[j]则path[i][j] = -1，否则path[i][j] = k(分割点)，输出的时候采用递归的方法，类似LCS的输出方式

#include <cstdio>  
#include <cstring>  
int const INF = 0xfffffff;  
int const MAX = 105;  
int dp[MAX][MAX], path[MAX][MAX];  
char s[MAX];  
      
void Print(int i, int j)  
{ 
    if(i > j) 
        return;  
    if(i == j)  
    {  
        if(s[i] == '(' || s[i] == ')')  
            printf("()");  
        else  
            printf("[]");  
    }  
    else if(path[i][j] == -1) 
    {  
        printf("%c", s[i]);  
        Print(i + 1, j - 1);  
        printf("%c", s[j]);  
    }  
    else  
    {  
        Print(i, path[i][j]);  
        Print(path[i][j] + 1, j);  
    }  
}  
      
int main()  
{  
    while(gets(s))  
    {  
        int n = strlen(s);  
        if(n == 0)  
        {  
            printf("\n");  
            continue;  
        }  
        memset(dp, 0, sizeof(dp));  
        for(int i = 0; i < n; i++)  
            dp[i][i] = 1;  
        for(int l = 1; l < n; l++)  
        {  
            for(int i = 0; i < n - l; i++)  
            {  
                int j = i + l;  
                dp[i][j] = INF;  
                if((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']'))  
                {  
                    dp[i][j] = dp[i + 1][j - 1];  
                    path[i][j] = -1;  
                }  
                for(int k = i; k < j; k++)  
                {  
                    if(dp[i][j] > dp[i][k] + dp[k + 1][j])  
                    {  
                        dp[i][j] = dp[i][k] + dp[k + 1][j];  
                        path[i][j] = k;  
                    }  
                }  
            }  
        }  
        Print(0, n - 1);  
        printf("\n");  
    }  
}