文档介绍：第7章动态规划
上海第二工业大学温敬和
******@it.
2008年4月1日
1
引言
最长公共子序列问题
矩阵链相乘(略)
动态规划法讨论
所有点对的最短路径问题
背包问题
2
引言
在这一章中,我们将研究一种强有力的算法设计技术,它被广泛用于求解组合最优化问题。使用这种技术的算法,不是递归调用自身,但是问题的基础解通常是用递归函数的形式来说明的。
分治算法是采用自上而下的方式求值,导致了不止一次的递归调用;而动态规划法是采取自下向上的方式递推求值,并把中间结果存储起来以便用于后续计算。
利用这种技术可以设计出特别有效算法来解决许多组合最优化问题,也可以用来改善蛮力搜索算法的时间复杂性,从而解决一些有NP难度的问题(详见第10章)
这种技术把一个问题的解决方案视为一系列决策的结果,还要考察每个决策序列中是否包含一个最优子序列。
3
例:i序列问题
f1=1,f2=1,f3=2,f4=3,f5=5,f6=8,f7=13, ……
序列中的每一个数是它前面二个数的和。这个序列递归定义如下:
上述定义可用下面递归过程来实现
1. procedure iRec(n)
2. if n=1 or n=2 then
3. return 1
4. else
5. return iRec(n-1)+ iRec(n-2)
6. end if
7. end procedure
4
i序列的递归过程是有效的,相反由于对过程的重复调用,它远不是有效的算法。为了说明这一点,我们把它展开。
f(n) =f(n-1)+f(n-2)
=(f(n-2)+f(n-3))+f(n-2)
=2f(n-2)+f(n-3)
=2(f(n-3)+f(n-4))+f(n-3)
=3f(n-3)+2f(n-4)
=3(f(n-4)+f(n-5))+2f(n-4)
=5f(n-4)+3f(n-5)
=………………
这导致了巨大数量的重复调用。
5
我们用数组F[1..n]i序列的值,由此得出自下而上的递推计算过程。
1. procedure i(n)
2. F[1]←1
3. F[2]←1
4. for i←3 to n
5. F[i]←F[i-1]+F[i-2]
6. end for
7. return F[n]
9. end procedure
//若i=1或i=2,则循环不执行,返回值为F[1]或F[2]。
6
最长公共子序列问题
㈠问题描述
在字母表∑上,分别给出长度为n和m的字符串A和B,确定在A和B中最长公共子序列的长度。
其中1≤i1<i2<... <ik≤n(严格递增下标序列)
A=a1a2...an的子序列为:
B=b1b2...bm的子序列为:
其中1≤j1<j2<... <jk≤m(严格递增下标序列)
和
相等。
并且
例:∑={x,y,z},A="zxyxyz",B="xyyzx"
"xyy"是A(a2a3a5)和B(b1b2b3)长度为3的公共子序列,但不是A和B的最长公共子序列。
"xyyz"是A(a2a3a5a6)和B(b1b2b3b4)长度为4的公共子序列,并且是A和B的最长公共子序列。
7
㈡穷举法
可使用穷举法求解字符串A和B的最长公共子序列长度,算法描述如下:
列举字符串A的除空串之外的所有子序列,设A的长度为n,A共有2n-1个子序列。
例A="abcd",可能的24-1=15个子序列为:
a、b、c、d、(4个)
ab、ac、ad、bc、bd、cd、(6个)
abc、abd、acd、bcd、(4个)
abcd(1个)
设字符串B的长度为m,对于A的每一个子序列可在O(m)时间内确定它是否是B的子序列。显然,穷举法的时间复杂性为O(m2n)。若采用动态规划法,它的时间复杂性仅为Θ(mn)。
8
㈢动态规划法
设A=a1a2...an、 B=b1b2...bm,L[i,j]表示a1a2...ai和b1b2...bj的最长公共子序列长度。设1≤i≤n、1≤j≤m,很容易证明下面的观察结论:
(Page131)
设i>0且j>0,那么
若ai=bj,L[i,j]=L[i-1,j-1]+1;
若ai≠bj,L[i,j]=max(L[i,j-1],L[i-1,j])。
①若ai=bj,计算a1a2...ai和b1b2...bj的最长公共子序列的长度,相当于在计算a1a2...ai-1和b1b2...bj-1最长公共子序列长度的基础上加1。
②若ai≠bj,计算a1a2...ai和b1b2...bj的最长公共子序列的长度,相当于分别计算a1a2...ai-