小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. 正文

解析动态规划问题(1)

2019年2月21日 829点热度 0人点赞 0条评论

关于最长公共子序列(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 << ")";
}
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 最长公共子序列 算法
最后更新:2019年2月21日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
数据结构【浙江大学】(第3节)整理 关于2013年全市中小学假期安排有关工作的通知 英语四级成绩公布 KMP算法的简单理解 莱芜赛区第三天:河北VS福建,辽宁VS江苏,解放军VS天津 吴恩达深度学习课程DeepLearning.ai笔记(4-3)
标签聚合
python学习 学习 鸟哥的linux私房菜 算法 生活 Java 高中 Python linux leetcode
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 8 个月前(10月20日) :wink:
niming 发布于 9 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号