解析动态规划问题(1)

关于最长公共子序列(LCS)

最长公共子序列和最长公共子串是有区别的,之前我一直把它们混淆。

  1. 最长公共子串举例:假设S1={A,D,C,B,E,X,Q},S2={H,P,D,C,B,E,M,L}
    那么它们的最长公共子串就是{D,C,B,E}。这是我通常理解的东西。
    最长公共子序列。
  2. 最长公共子序列举例:假设S1={A,B,C,A,D,A,B},S2={B,A,C,D,B,A},那么它们的LCS就是{B,A,D,B}。

求解最长公共子序列

这是一个动态规划问题。如何求解最长公共子序列(以下用LCS代替)呢?我们假设已经知道Z={z1,z2,…zk}是X={x1,x2,…,xm}和Y={y1,y2,…,yn}的LCS,那么可以分以下三种情况讨论(具体每种情况证明不再累述):
1. xm=yn=zk:那么Zk-1是Xm-1和Yn-1的LCS。
2. xm≠yn,yn≠zk:我们可以把yn去掉,那么Zk是Xm和Yn-1的LCS。
3. xm≠yn,xm≠zk:我们可以把xm去掉,那么Zk是Xm-1和Yn的LCS。

基于以上情况,我们可以得到LCS递归式。我们假设c[i][j]表示Xi和Yi的LCS长度,那么:

  • c[i][j]=0(i=0或j=0);
  • c[i][j]=c[i-1]c[j-1]+1(i,j>0且xi=yi);
  • c[i][j]=max{c[i-1][j],c[i],[j-1]};(i,j>0且xi≠yi)。

这样我们就可以得到LCS的长度。如何得到具体内容是什么呢?我们可以借用一个辅助数组b[i][j],这个数组用来记录c[i][j]的来源,分别有如下情况:

  • c[i][j]=c[i-1][j-1]+1,则b[i][j]=1;
  • c[i][j]=c[i][j-1],则b[i][j]=2;
  • c[i][j]=c[i-1][j],则b[i][j]=3。

这样就可以根据b[m][n]反向追踪LCS,当b[i][j]=1,输出xi;当b[i][j]=2,追踪c[i][j-1];当b[i][j]=3,追踪c[i-1][j],直到i=0或j=0停止。

算法设计

(1)初始化。初始化c[][]第1行和第1列为0。
(2)开始操作。具体是将s1[i]分别与s2[j-1](j=1,2,…,len2)进行比较,若字符相等c[i][j]=左上角数值+1,且b[i][j]=1;若不相等,则c[i][j]等于左侧或者上侧重最大的一个数值,若左侧和上侧相等,则取左侧,且b[i][j]=2或3(当取左侧为2,取上侧为3)。最后的c[][]和b[][]如下所示:
下表是c[][]:

0 1 2 3 4 5 6
0 0 0 0 0 0 0
A 0 0 1 1 1 1 1
B 0 1 1 1 1 2 2
C 0 1 1 2 2 2 2
A 0 1 2 2 2 2 3
D 0 1 2 2 3 3 3
A 0 1 2 2 3 3 4
B 0 1 2 2 3 4 4

下表是b[][]:

0 1 2 3 4 5 6
0 0 0 0 0 0 0
1 0 2 1 2 2 2 1
2 0 1 2 2 2 1 2
3 0 3 2 1 2 2 2
4 0 3 1 2 2 2 1
5 0 3 3 2 1 2 2
6 0 3 1 2 3 2 1
7 0 1 3 2 3 1 2

根据c[][]可以得出,LCS的长度为4(也就是c[][]最后一个值)。然后开始判断内容是什么,这是要根据b[][]来。
首先,b[7][6]=2,向左找b[7][5]=1,所以向左上角找b[6][4],得到字母为s1[6]=[B];
b[6][4]=3,向上找b[5][4]=1,向左上角找b[4][3],得到字母s1[4]=[D];
b[4][3]=2,向左找b[4][2=1,向左上角找b[3][1],得到字母s1[3]=[A];
b[3][1]=3,向上找b[2][1]=1,向左上角找b[1][0],得到字母s1[1]=[B].
由于b[1][0]=0,所以算法停止,返回结果为“BADB”。

代码演示

    void LCSL()
    {
        int i, j;
        for(i=1;i<len1;i++)
            for (j = 1; j < len2; j++)
            {
                if (s1[i = 1] == s2[j - 1])
                {
                    c[i][j] = c[i - 1][j - 1] + 1;
                    b[i][j] = 1;
                }
                else
                {
                    if (c[i][j - 1] >= c[i - 1][j])
                    {
                        c[i][j] = c[i][j - 1];
                        b[i][j] = 2;
                    }
                    else
                    {
                        c[i][j] = c[i - 1][j];
                        b[i][j] = 3;
                    }
                }
            }
    }

    void print(int i, int j)
    {
        if (i == 0 || j == 0)
            return;
        if (b[i][j] == 1)
        {
            print(i - 1, j - 1);
            cout << s1[i - 1];
        }
        else if (b[i][j] == 2)
            print(i, j - 1);
        else
            print(i - 1, j);
    }

编辑距离

编辑距离和LCS的不同点

  1. 编辑距离的d[][]取值公式如下:
    (一个前提,若xi=yj,则diff=0;否则为1)
    d[i][j]=min{d[i – 1][j] + 1, d[i][j – 1] + 1,d[i-1][j-1]+diff}
  2. 构造最优解:编辑距离是从右下角开始,逆向查找d[i][j]的来源:上面表示需要删除,左侧表示需要插入;左上角要判断字符是否相等,若相等,不做任何操作,若不相等,执行替换
  3. 两者的时间复杂度都是O(n*m)。

代码实现

int min(int a, int b,int c)
{
    int temp = (a < b) ? a : b;
    return (temp < c) ? temp : c;
}

//编辑距离函数
int editdistance(char *str1, char *str2)
{
    int i, j;
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    for (i = 0; i <= len1; i++)
    {
        d[i][0] = i;
    }
    for (j = 0; j <= len2; j++)
    {
        d[0][j] = j;
    }
    for (i = 1; i <= len1; i++)
    {
        for (j = 1; j <= len2; j++)
        {
            int diff;
            if (str1[i - 1] == str2[j - 1])
                diff = 0;
            else
                diff = 1;
            d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1,d[i-1][j-1]+diff);
        }
    }
    return d[len1][len2];
}

游艇租赁问题

假设在一条河上有n个游艇出租站,游客可以在这些游艇出租站租游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到j之间的租金为r(i,j),i<=i<=j<=n。设计一个算法,计算从游艇出租站i到出租站j所需要的租金最少。

问题分析

(1)分析最优解的结构特征
(2)简历最优值的递归式
m[i][j]=
0(j=i);
r[i][j];j=i+1;
min{m[i][k]+m[k][j],r[i][j],j>i+1。

算法设计

(1)确定合适的数据结构:采用二维数组r[][]输入数据,二维数组m[][]存放各个子问题的最优值,二维数组s[][]存放各个子问题的最优决策(停靠站点)。
(2)初始化:m[i][j]=r[i][j],然后再找有没有比m[i][j]小的值,如果有,则记录该最优值和最优解即可,s[i][j]=0.
(3)循环阶段:

  • 按照递归关系式计算3个站点i,i+1,j(j=i+2)的最优值,并将其存入m[i][j],同时将最优策略存入s[i][j],i=1,2,…,n-2。
  • 按照递归关系式计算4个站点i,i+1,i+2,j(j=i+3)的最优值,并将其存入m[i][j],同时将最优策略存入s[i][j],i=1,2,…,n-3。
  • 以此类推,直到求出n个站点的最优值m[1][n]。

(4)构造最优解。根据s[][]递归构造最优解。s[1][n]是第一个站点到底n个站点)1,2,…,n)的最优解的停靠站点,即停靠了第s[1][n]个站点,我们在递归构造两个子问题(1,2,…,k)和(k,k+1,…,n)的最优解停靠站点,一直递归到只包含一个站点为止。

代码实现

void rent()
{
    int i, j, k, d;
    for (d = 3; d <= n; d++)
    {
        for (i = 1; i <= n - d + 1; i++)
        {
            j = i + d - 1;
            for (k = i + 1; k < j; k++)
            {
                int temp;
                temp = m[i][k] + m[k][j];
                if (temp < m[i][j])
                {
                    m[i][j] = temp;
                    s[i][j] = k;
                }
            }
        }
    }
}

void print(int i, int j)
{
    if (s[i][j] == 0)
    {
        cout << "-- " << j;
        return;
    }
    print(i, s[i][j]);
    print(s[i][j], j);
}

代码实现2:最贵的租金

其实只是把总结的递归式中的j>i+1的时候的min改为了max。所以只是修改了代码中的

if (temp<m[i][j])

将其改为了

if (temp>m[i][j])

快速计算——矩阵连乘

最优递归式:
当i=j时,只有一个矩阵,m[i][j]=0;
当i<j的时候,m[i][j]=min{m[i][k]+m[k+1][j]+pip(k+1)qj}

算法设计

(1)确定合适的数据结构。用一维数组p[]记录矩阵的行和列,第i个矩阵的行数存在数组的第i-1位置,列存在第i位置。二维数组m[][]用来存放各个子问题的最优值,二维数组s[][]来存放各个子问题的最优决策(加括号的位置)。
(2)初始化。m[i][i]=0,s[i][i]=0。
(3)循环阶段。
– 按照递归关系式计算2个矩阵Ai、Ai+1相乘时的最优值,j+i+1,并将其存入m[i][j];同时将最优策略计入s[i][j]。i=1,2,3,..,n-1。
– 按照递归关系式计算3个矩阵相乘Ai、Ai+1、Ai+2,相乘时的最优值,j+i+2,并将其存入m[i][j],同时将最优策略记入s[i][j],i=1,2,3,…,n-2。
– 以此类推,直到求出n个矩阵相乘的最优值m[1][n]。

(4)构造最优解
根据最有决策信息数组s[][]递归构造最优解。s[1][n]表示A1A2…An最优解的加括号位置,我们在递归构造两个子问题的最优解加括号位置,一直低轨道子问题只包含一个矩阵为止。

举例图解

矩阵 A1 A2 A3 A4 A5
规模 3*5 5*10 10*8 8*2 2*4

(1)初始化
m[i][i]=0,s[i][i]=0
(2)计算两个矩阵相乘的最优值
m[][]如下:

m[][] 1 2 3 4 5
1 0 150 390 290 314
2 0 400 260 300
3 0 160 240
4 0 64
5 0

s[][]如下:

s[][] 1 2 3 4 5
1 0 1 2 1 4
2 0 2 2 4
3 0 3 4
4 0 4
5 0

(3)构造最优解
类似于游艇租赁

代码实现

void matrixchain()
{
    int i,j,r,k;
    memset(m,0,sizeof(m));
    memset(s,0,sizeof(s));
    for(r = 2; r <= n; r++)         //不同规模的子问题
    {
        for(i = 1; i <= n-r+1; i++)
        {
           j = i + r - 1;
           m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j];  //决策为k=i的乘法次数
           s[i][j] = i;                     //子问题的最优策略是i;
           for(k = i+1; k < j; k++) //对从i到j的所有决策,求最优值,记录最优策略
            {
                int t = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
                if(t < m[i][j])
                {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
    }
}
void print(int i,int j)
{
    if( i == j )
    {
       cout <<"A[" << i << "]";
       return ;
    }
    cout << "(";
    print(i,s[i][j]);
    print(s[i][j]+1,j);
    cout << ")";
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注