MIT算法导论公开课之第15课 动态规划、最长公共子序列
程序员文章站
2024-02-13 23:04:52
...
动态规划(Dynamic programming)
动态规划是一种设计技巧,而不是一种特定的算法,就像分治法一样。
最长公共子序列(Longest common subsequence)问题
有两个序列,序列x[1~m],序列y[1~n],找到它们的最长公共子序列,子序列不需要在原序列中占用连续的位置(最长公共子串要求连续),子序列可能不唯一。
- Ex:
x:A B C B D A B
y:B D C A B A
公共子序列:BDAB BCAB BCBA(LCS(x,y))
暴力算法
检查x[1~m]的每个子序列在y[1~n]中也是否存在,找到其中最长的。
运行时间分析:
检查是否存在代价为O(n)
x中的子序列数量为2^m,可以用一个m位的向量来表示,1表示选取那个字符,0表示不选取那个字符。
总运行时间为O(n·2^m),指数级的运行时间是非常慢的。
LCS问题简化
1.计算最长公共子序列的长度(唯一)。
2.扩展算法使其能够找到最长公共子序列。
注:|S|表示序列S的长度。
动态规划策略
- 考虑序列x和y的前缀序列。
定义c[i,j]=|LCS(x[1,i],y[1,j])|,则有c[m,n]=|LCS(x,y)|。 - 动态规划递归方程:
- 证明方程的正确性:
x[i]=y[j]的情况:
设z[1~k]=LCS(x[1~i],y[1~j]),且有c[i,j]=k,则有z[k]=x[i](=y[j])。
证明z[1~k-1]=LCS(x[1~i-1],y[1~j-1]):
假设存在w为x[1~i-1],y[1~j-1]的一个子序列且|w|>k-1。
w和z[k]合成的序列(剪贴法),也应是x[1~i],y[1~j]的一个子序列。
|w和z[k]合成的序列|>k。
与c[i,j]=k矛盾,假设不成立,z[1~k]=LCS(x[1~i],y[1~j])得证。
因此有c[i-1,j-1]=k-1,c[i,j]= c[i-1,j-1]+1。
x[i]≠y[j]的情况:
可利用与上面方法类似的方法证明。
动态规划问题特性1
- 最优子结构,问题的最优解包含了子问题的最优解。
在最长公共子序列问题中,如果有z=LCS(x,y),那么z的某个前缀= LCS(x的某个前缀,y的某个前缀)。
LCS的递归算法伪码
LCS(x,y,i,j)//忽略基本情况
if x[i]=y[j]
c[i,j] ← LCS(x,y,i-1,j-1)+1
else
c[i,j] ← max{LCS(x,y,i-1,j), LCS(x,y,i,j-1)}
return c[i,j]
- 上述算法得最坏情况分析:
对任意的i和j,x[i]≠y[j]。- 递归树分析:
假设m=7,n=6。
树高为Θ(m+n)=>此算法的运行时间为Θ(2^(m+n)),指数阶的速度很满。
- 递归树分析:
动态规划问题特性2
- 重叠子问题,一个递归的过程包含一些数量的独立的子问题被重复计算了多次。
在最长公共子序列问题中,可以发现在递归树中有很多相同的子问题,可分析得独立子问题得数量为m·n。
LCS的备忘录递归算法伪码
LCS(x,y,i,j) //忽略基本情况
if c[i,j]=nil
if x[i]=y[j]
c[i,j] ← LCS(x,y,i-1,j-1)+1
else
c[i,j] ← max{LCS(x,y,i-1,j), LCS(x,y,i,j-1)}
return c[i,j]
- 上述算法的运行分析:
运行时间为Θ(m·n),可从平摊代价的方面考虑,每次操作只有访问c[i,j]需要计算代价,递归操作会开启新的操作,重新计算平摊代价,所以运行时间为Θ(m·n)。
占用空间为Θ(m·n),占用空间较多,且计算c[i,j]表的过程比较混乱。
完善的动态规划算法
自底向上的计算c[i,j]表。
Ex:
x:A B C B D A B
y:B D C A B A
右下角即为最长公共子序列的长度,运行时间为Θ(m·n),且利用了内存访问的局部性特点,此算法效率很高。回溯法重建LCS:
BCBA即为一个最长公共子序列,走别的路径即可得到其他几个结果。
朴素算法占用空间为Θ(m·n),改进算法只使用两行或两列可将占用空间减小到O(min{m,n})。
思考:改进算法如何重建LCS?(提示:采用分治法)
上一篇: iOS 定位说明
下一篇: AI基础:深度强化学习之路