动态规划原理和使用

  • A+
所属分类:深度学习

在做文本相似度的时候遇到了动态规划这个概念。

这边做个简单的介绍,它原理概念和使用。

基本思路:

如果需要解决一个算法问题,而这个算法问题是由几个小问题有规律的组成的。动态规划的思路是通过解决最小的问题,然后存储最小问题的解,然后在解答上一级问题的时候就可以直接使用这个解,因此可以轻松的解决这个算法问题,动态规划的核心是从低至上解决问题。

问题举例:

斐波那契数列求解:

f(n) = f(n - 1) + f(n - 2)

这个数列的求解我们早就学过了,可以用一个简单的递归就解决了,如下。

public int f(int n)
{
    if(n<=0)
        return 0;
    if(n==1)
        return 1;
    return f(n-1)+f(n-2);
}

我们画出这个n = 6 的斐波那契数列计算过程的递归树形结构,大概是这样子的。最后答案是8.

动态规划算法

动态规划的思想是从 f(1) f(2) 开始。从底层一步一步往上计算,算法如下:

public static int f(int n)
{
        if(n<=0)
            return n;
        int * p=new int[n+1];
        p[0]=0;
        p[1]=1;
        for(int i=2;i<=n;i++)
        {
            p[i]=p[i-1]+p[i-2];
        }       
        return p[n];
}

最小编辑距离问题:

两个字符串之间存在差异,例如abcd 和 acd,或者happy 和 huppy ,如何通过最小的手段让两个字符一样。可以用的操作为,插入,删除和替换。

动态规划思路解决这个问题:两个字符串可以看出两个数组,str1 str2,从str1[0] 和str2[0] 开始比较,然后从一个方向引申,使用前面已有的数据进行分析。这样讲比 较抽象用一个图来表示会比较清楚。

  • 假设两个数组分别是 abcd 和 acd,如下排布

动态规划算法

  • 先初始化数组序列

动态规划算法

  • 现在我们要开始做动态规划

先比较str1[0] 和 str2[0] 然后比较 str1[1] 和 str2[0] 就是横向比较,然后再跳到下一行横向比较,然后就是说,比较来干嘛,比较如果两个字符相等就取对角线的值,如果不相等就取周围三个最小的值加+1。比如我们现在要填的第一个值, a == a 那么就填写对角线的 0。

动态规划算法

  • 这一次,a != b 了,查看周围三个地方,最小的值加+1

动态规划算法

  • 以此类推, 到第二列也是一样的。

动态规划算法

  • 填到这个值的时候,发现c == c 就填充对角线的。一直这样到最后

动态规划算法

最后这个值就是我们需要的解。那么代码怎么写:如下

/**
 * 动态规划算法
 * @param {string} a
 * @param {string} b
 * @returns {number} 从 a → b 的最小编辑距离
 */
function dynamicPlanning(a, b) {
    let lenA = a.length;
    let lenB = b.length;
    let d = [];
    d[0] = [];

    for (let j = 0; j <= lenB; j++) {
        d[0].push(j);
    }

    for (let i = 0; i <= lenA; i++) {
        if (d[i]) {
            d[i][0] = i;
        } else {
            d[i] = [];
            d[i][0] = i;
        }
    }

    for (let i = 1; i <= lenA; i++) {
        for (let j = 1; j <= lenB; j++) {
            if (a[i - 1] === b[j - 1]) {
                d[i][j] = d[i - 1][j - 1];
            } else {
                let m1 = d[i - 1][j] + 1;
                let m2 = d[i][j - 1] + 1;
                let m3 = d[i - 1][j - 1] + 1;
                d[i][j] = Math.min(m1, m2, m3);
            }
        }
    }

    return d[lenA][lenB];
}

 

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: