【算法】动态规划法 |
您所在的位置:网站首页 › 求根公式算法设计思路 › 【算法】动态规划法 |
【fishing-pan:https://blog.csdn.net/u013921430转载请注明出处】
前言
这篇是自己写的第一篇关于算法方面的博客,写他是因为自己今天打开笔记,刚好看到了它,就这么简单。 这篇博客主要想讲讲动态规划法,然后以LCS问题为例展开来说一下怎么利用动态规划法求解它,下面是自己的一些理解和总结,有不对的地方还请大家指正。 动态规划法动态规划法(dynamic programming)通常用于求解最优化问题(optimization problem),它适用于那些子问题相互重叠的情况,即子问题不独立,不同的子问题具有公共的子子问题(就是子问题的子问题)。这显然与分治法是不同的,分治法将问题划分为不重叠的子问题,然后分别求解这些子问题,最后将这些问题合并得到最终的解。 对于具有公共子问题的情况,分治法会做很多不必要的工作,它会多次求解同一子子问题。动态规划法却不一样,对每个子子问题它只会求解一次,将其保存在一个表格中,避免了不必要的重复计算。 如之前所说,动态规划法用于求解最优化问题,这就意味着可能这个问题,有很多解,但是呢,不一定都是最优解。利用动态规划法求出来的是这个问题的一个最优解(an optimal solution),记住这里求解的只是最优解(the optimal solution)中的一个,因为最优解可能有多个。 设计一个问题的动态规划算法主要有一下的几步 (1) 找出最优解的性质,刻画其结构特征; (2) 递归的定义最优解的值; (3) 以自底向上的方式计算出最优值; (4) 根据计算最优解时得到的信息,构造一个最优解。 如果你只需要一个最优解的值,而不是这个结本身,就不需要第(4)步。如果你需要得到这个解本身,也就是说你需要执行第(4)步,这往往需要我们在第(3)步中记录一些额外的信息,以方便第(4)步的求解。 下面让我们来看看LCS问题如何利用动态规划法求解。 最长公共子序列的动态规划法实现 最长公共子序列(longest-common-subsequence, LCS)(1)子序列:一个序列X = x1x2...xn,中任意删除若干项,剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。 例如:对序列 1,3,5,4,2,6,8,7来说,序列3,4,8,7 是它的一个子序列。对于一个长度为n的序列,它一共有2^n 个子序列,有(2^n – 1)个非空子序列。在这里需要提醒大家,子序列不是子集,它和原始序列的元素顺序是相关的。 (2)公共子序列:如果序列Z既是序列X的子序列,同时也是序列Y的子序列,则称它为序列X和序列Y的公共子序列。空序列是任何两个序列的公共子序列。 (3)最长公共子序列:X和Y的公共子序列中长度最长的(包含元素最多的)叫做X和Y的最长公共子序列。 这个问题如果用穷举法时间,最终求出最长公共子序列时,时间复杂度是Ο(2mn),是指数级别的复杂度,对于长序列是不适用的。因此我们使用动态规划法来求解。 刻画最长公共子序列问题的最优子结构设X=x1x2…xm和Y=y1y2…yn是两个序列,Z=z1z2…zk是这两个序列的一个最长公共子序列。 1. 如果xm=yn,那么zk=xm=yn,且Zk-1是Xm-1,Yn-1的一个最长公共子序列; 2. 如果xm≠yn,那么zk≠xm,意味着Z是Xm-1,Y的一个最长公共子序列; 3. 如果xm≠yn,那么zk≠yn,意味着Z是X,Yn-1的一个最长公共子序列。 从上面三种情况可以看出,两个序列的LCS包含两个序列的前缀的LCS。因此,LCS问题具有最优子结构特征。 递归的定义最优值从最优子结构可以看出,如果xm=yn,那么我们应该求解Xm-1,Yn-1的一个LCS,并且将xm=yn加入到这个LCS的末尾,这样得到的一个新的LCS就是所求。 如果xm≠yn,我们需要求解两个子问题,分别求Xm-1,Y的一个LCS和X,Yn-1的一个LCS。两个LCS中较长者就是X和Y的一个LCS。 可以看出LCS问题具有重叠子问题性质。为了求X和Y的一个LCS,我们需要分别求出Xm-1,Y的一个LCS和X,Yn-1的一个LCS,这几个字问题又包含了求出Xm-1,Yn-1的一个LCS的子子问题。(有点绕了。。。晕没晕。。。。) 根据上面的分析,我们可以得出下面的公式; 根据上面的,我们很容易就可以写出递归计算LCS问题的程序,通过这个程序我们可以求出各个子问题的LCS的值,此外,为了求解最优解本身,我们好需要一个表b,b[i,j]记录使C[i,j]取值的最优子结构。 C++代码如下; int **Lcs_length(string X,string Y,int **B) { int x_len = X.length(); int y_len = Y.length(); int **C = new int *[x_len+1]; for (int i = 0; i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |