NLP

动态规划算法

Nlp基础概论

Posted by Nova on 2019-05-26

问题：假如有1、5、10、20、50、100元面值的钞票。现在需要凑出某个金额w.需要用到尽量少的钞票。

根据生活经验，会采取这样的策略：能用100的尽量用100，否则尽量用50的…依次类推. 这种策略下，666共需要10张钞票。
这种策略称为贪心策略。贪心策略尽快让w变得更小。长期的生活经验表明，贪心策略是正确的。

但是如果钞票的面值边了，只有1、5、11这三种面值，需要凑出15的时候，贪心就是失效。
贪心15=1 * 11+4 * 1 使用了5张钞票。然而15=3 * 5,只用3张就可以了。

动态规划

1
2
3
4
5
核心概念：最优子结构、状态转移方程、边界、重叠子问题
核心思想：拆分子问题；记住过往，减少重复计算
解题思路：穷举举例、确定边界、找规律、确定最优子结构、写出状态转移方程

> 记住求过的解来节省时间
1
2
3
4
5
- 青蛙跳阶问题
f(n-1)和f(n-2) 称为 f(n) 的最优子结构
f(n)= f（n-1）+f（n-2）就称为状态转移方程
f(1) = 1, f(2) = 2 就是边界啦
比如f(10)= f(9)+f(8),f(9) = f(8) + f(7),f(8)就是重叠子问题

怎样才能避免上面的问题. 如果直接暴力枚举凑出w的方案，复杂度太高。枚举是不可以承受的。

但可以尝试一下一步选择之后的影响，发生的变化。重新分析刚才的例子。如果取11，接下来就面对w=4的情况；如果取5，接下来面对w=10的情况。

我们发现这些问题都有相同的形式：“给定w,凑出w所用的最少钞票是多少张？” .可以使用f(n)来表示“凑出n所需的最少钞票数量”。

那么如果取了11.cost = f(4) +1 = 4+1 = 5.
如果取了5，cost = f(10) + 1 = 2 + 1 = 3.

  • 取11：cost=f(4)+1=4+1=5
  • 取5： cost=f(10)+1=2+1=3
  • 取1： cost=f(14)+1=4+1=5

这给了我们一个至关重要的启示—— f(n) 只与 f(n-1),f(n-5),f(n-11) 相关；更确切地说：

1
f(n)=min{f(n-1),f(n-5),f(n-11)}+1

这个式子是非常激动人心的。我们要求出f(n)，只需要求出几个更小的f值；既然如此，我们从小到大把所有的f(i)求出来不就好了？注意一下边界情况即可

我们以 O(n) 的复杂度解决了这个问题。（n为指定的凑出数的大小）。现在回过头来，我们看看它的原理：

  • f(n) 只与f(n-1),f(n-5),f(n-11)的值相关。
  • 我们只关心 f(w) 的值，不关心是怎么凑出w的。

这两个事实，保证了我们做法的正确性。它比起贪心策略，会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”！

我们能这样干，取决于问题的性质：求出f(n)，只需要知道几个更小的 f©。我们将求解 f© 称作求解f(n)的“子问题”。

这就是DP（动态规划，dynamic programming）.

将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解

其他概念

什么样的问题可以考虑使用动态规划解决呢？

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

比如：最长递增子序列、最小编辑距离、背包问题、凑零钱问题

动态规划

动态规划实际上是一类题目的总称，并不是指某个固定的算法。动态规划的意义就是通过采用递推（或者分而治之）的策略，通过解决大问题的子问题从而解决整体的做法。

动态规划的核心思想是巧妙的将问题拆分成多个子问题，通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题，从而用类似递推迭代的方法解决要求的问题。

与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

动态规划的解题核心主要分为两步：

  • 第一步：状态的定义
  • 第二步：状态转移方程的定义

无后效性

一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。

要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。

“未来与过去无关”，这就是无后效性。

（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）

最优子结构

回顾我们对f(n)的定义：我们记“凑出n所需的最少钞票数量”为f(n).
f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解，我们即可算出w=15的最优解。
大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。

引入这两个概念之后，我们如何判断一个问题能否使用DP解决呢？

能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

DP的典型应用-DAG

问题很简单：给定一个城市的地图，所有的道路都是单行道，而且不会构成环。每条道路都有过路费，问您从S点到T点花费的最少费用。
这个问题能用DP解决吗？我们先试着记从S到P的最少费用为f§.
想要到T，要么经过C，要么经过D。从而f(T)=min⁡{f©+20,f(D)+10}

代码实现也很简单，拓扑排序即可。(TODO)

DP原理的一些讨论

在暴力算法中，可能解空间往往是指数级的大小；如果我们采用DP，那么有可能把解空间的大小降到多项式级。
一般来说，解空间越小，寻找解就越快。这样就完成了优化。

最长上升子序列

例子一:数塔取数问题

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

该三角形第n层有n个数字，例如：

1
2
3
4
5
6
第一层有一个数字：5
第二层有两个数字：8 4
第三层有三个数字：3 6 9
第四层有四个数字：7 2 9 5

最优方案是：5 + 8 + 6 + 9 = 28

例子二:编辑距离

编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如将kitten一字转成sitting：

1
2
3
4
5
sitten （k->s） 
sittin （e->i） 
sitting （->g） 
所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。 
给出两个字符串a,b，求a和b的编辑距离。

状态定义:Fi,j表示第一个字符串的前i个字母和第二个字符串的前j个字母需要编辑的次数，求Fn,m，n和m分别是两个字符串的长度。

状态转移方程：
当Fi,j-1=Fi-1,j时，Fi,j=Fi-1,j-1；
当Fi,j-1！=Fi-1,j时，Fi,j=min{Fi-1,j-1,Fi,j-1,Fi-1,j}+1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String aStr = in.nextLine();
        String bStr = in.nextLine();
        int aLen = aStr.length();
        int bLen = bStr.length();
        int[][] dp = new int[aLen + 1][bLen + 1];
        for (int i = 0; i < aLen + 1; i++) dp[i][0] = i;
        for (int i = 0; i < bLen + 1; i++) dp[0][i] = i;
        for (int i = 1; i < aLen + 1; i++)
            for (int j = 1; j < bLen + 1; j++)
                if (aStr.charAt(i - 1) == bStr.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
        System.out.println(dp[aLen][bLen]);
    }
}

什么是动态规划？动态规划的意义是什么？

java 动态规划策略原理及例题

FEATURED TAGS
NLP
FRIENDS