第7章 动态规划法

1第7章动态规划法27.1引言7.2最长公共子序列问题7.3矩阵链相乘(略)7.4动态规划法讨论7.5所有点对的最短路径问题7.6背包问题37.1引言在这一章中，我们将研究一种强有力的算法设计技术，它被广泛用于求解组合最优化问题。使用这种技术的算法，不是递归调用自身，但是问题的基础解通常是用递归形式来说明的。分治算法是采用自上而下的方式求值，导致了不止一次的递归调用；而动态规划法是采取自下向上的方式递推求值，并把中间结果存储起来，以便用于后续计算。利用这种技术可以设计出特别有效算法，来解决许多组合最优化问题，也可以用来改善蛮力搜索算法的时间复杂性，从而解决一些有NP难度的问题。这种技术把一个问题的解决方案，视为一系列决策的结果。在决策过程中，考察每个决策是否包含一个最优子序列。4例7.1Fibonacci序列问题f1=1，f2=1，f3=2，f4=3，f5=5，f6=8，f7=13，……序列中的每一个数是它前面二个数的和。这个序列递归定义如下：3)2()1(2,11)(nnfnfnnnf上述定义可用下面递归过程来实现过程FibonacciRec(n)1.if(n=1)or(n=2)then2.return13.else4.returnFibonacciRec(n-1)+FibonacciRec(n-2)5.endif5不能认为上页给出的计算Fibonacci序列的递归过程是有效的。相反，由于对过程的重复调用，它远不是有效的算法。为了说明这一点，我们把它展开：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(n-5)+f(n-6))+3f(n-5)=8f(n-5)+5f(n-6)=8(f(n-6)+f(n-7))+5f(n-6)=13f(n-6)+8f(n-7)=………………在求解过程中，产生了巨大数量的重复调用。6我们用数组F[1..n]来存储Fibonacci序列的值，由此得出自下而上的递推计算过程。1.inputn2.F[1]←13.F[2]←14.fori←3ton5.F[i]←F[i-1]+F[i-2]6.endfor7.outputF[n]//若n=1或n=2，则循环不执行。77.2最长公共子序列问题㈠问题描述在字母表∑上有二个长度分别为n和m的字符串A和B。设A=a1a2...an、B=b1b2...bm，A和B的公共子序列定义如下：设A的某一子序列为：(1≤i1＜i2＜...＜ik≤n)设B的某一子序列为：(1≤j1＜j2＜...＜jk≤m)若二个子序列相等，则称是A和B的公共子序列。在A和B的所有公共子序列中，字符个数最多的公共子序列称为A和B的最长公共子序列。kiiiaaa...21kjjjbbb...21kiiiaaa...218设字母表∑={x,y,z}，字符串A=zxyxyz、字符串B=xyyzx。∵A的子序列a2a3a5=xyy(235)B的子序列b1b2b3=xyy(123)∴xyy是A和B长度为3的公共子序列，但不是A和B的最长公共子序列。∵A的子序列a2a3a5a6=xyyz(2356)B的子序列b1b2b3b4=xyyz(1234)∴xyyz是A和B长度为4的公共子序列，并且是A和B的最长公共子序列。9㈡穷举法可使用穷举法求解字符串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)。10㈢动态规划法设A=a1a2...an、B=b1b2...bm，L[i,j]表示a1a2...ai和b1b2...bj的最长公共子序列长度，很容易证明下面的观察结论：观察结论7.1(Page131)如果i和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])。可以从观察结论7.1立即得出：jijibajibajijijiLjiLjiLjiL且若且若或若0,00,000]},1[],1,[max{1]1,1[0],[11可采用动态规划法求解最长公共子序列。对于每对i和j的值，用一个二维数组L[0..m,0..n]来存放L[i,j]的值。⑴设字符串A=a1a2…an，字符串B=b1b2…bm。以字符串A为y轴，字符串B为x轴。⑵首先从A子串只有一个字符开始，计算出a1和B中各子串的最大公共子序列长度；然后逐个增加A子串中的字符，分别计算出当前A子串和B各子串的最大公共子序列长度；直至A的全部字符。⑶L[i,j]表示A子串a1a2…ai(1≤i≤n)和B子串b1b2…bj(1≤j≤m)的最大公共子序列长度。1.ifai=bjthen2.L[i,j]←L[i-1,j-1]+13.else4.L[i,j]←max{L[i,j-1],L[i-1,j]}5.endif12算法7.1LCS(Page131)输入：字符串A和B，设A和B的长度分别为n和m。输出：A和B的最长公共子序列的长度1.fori←0ton//字符串A为y轴2.L[i,0]←0//字符串B为空3.endfor4.forj←0tom//字符串B为x轴5.L[0,j]←0//字符串A为空6.endfor7.fori←1ton//A子串中字符逐个增加8.forj←1tom//当A子串确定，B子串中字符逐个增加。9.ifai=bjthenL[i,j]←L[i-1,j-1]+1//i-1表示上一行10.elseL[i,j]←max{L[i,j-1],L[i-1,j]}//j-1表示前一列11.endif12.endfor13.endfor14.returnL[m,n]//返回最长公共子序列长度130000000000000123456Azxyxyz012345Bxyyzx011111012222012233112234122334字符串A=zxyxyx字符串B=xyyzx定义二维数组L[0..5,0..6]14算法LCS可方便地修改成输出最长公共子序列；由于计算表的每一项需要Θ(1)时间，因此算法的时间复杂性恰好是表的大小Θ(nm)；由于计算当前行仅需要上一行和左面元素的值，算法可容易地修改成只需要Θ(min{m,n})空间。定理7.1(Page131)最长公共子序列问题的最优解，可在Θ(nm)时间和Θ(min{m,n})空间内得到。157.4动态规划法讨论⑴在许多组合优化问题中，问题的解经常可用递推式来表示。若直接求解，将导致许多子实例被不止一次地计算。在动态规划法中，子问题的解以表项的形式被存储，避免了重复计算。⑵在动态规划法中，对于原问题的每个子问题，算法都计算了一个最优解。例公共子序列问题中的L[i,j]，它是在L[i-1,j]、L[i,j-1]、L[i-1,j-1]的基础上计算而得，这三者本身是问题的最优子解。最优化原理：给出一个最优决策序列，每个子序列自身必须是最优的决策序列。167.5所有点对的最短路径问题在介绍“所有点对的最短路径问题”之前，让我们回忆一下Dijkstra算法的一些重要细节。Dijkstra算法是从源结点出发，计算它到其它各个结点的最短路径长度；Dijkstra算法是按照路径长度顺序，产生从源到各结点的最短路径，而不是按照结点的编号顺序。每采用一次贪心准则，便做出了一个不可撤回的决策；可以使用n次Dijkstra算法，求出所有点对的最短路径。但是我们期望有更快的解法，尤其是对于稠密图；Dijkstra算法提供了动态规划算法的基础，可逐个增加可途经的结点，自下而上地逐步计算出所有点对的最近距离。17设G=(V,E)是一个有向图，其中每条边(i,j)有一个非负长度l[i,j]，如果i=j，则l[i,j]=0；如果从顶点i到结点j没有边，则l[i,j]=∞。设V={1,2,3,…,n}，设i和j是V中二个不同的结点。定义是从i到j可能经过结点子集{1,2,3,…,k}，但不经过结点子集{k+1,k+2,…,n}中任何结点的最短路径。表示不经过任何结点直接从i到j的最短路径。表示从i到j除了可能经过结点1，但不经过任何其它结点的最短路径。表示从i到j除了可能经过结点1、结点2或同时经过它们，但不经过任何其它结点的最短路径。kjid,0,jid1,jid2,jid18nkdddkjild。，。dkjkkkikjikjikji1},min{0],[1,1,1,,,可采用递推方法也既可采用递归方法可使用下式进行计算。、d、、ddnnn，njijiji,1,0,*1矩阵来存放个可用推方法进行计算考虑采用自下而上的递。ji，dnji的最短路径到结点是结点由定义可知,19①2891②6③k=1D1[1,1]=min(D0[1,1],D0[1,1]+D0[1,1])=min(0,0+0)=0D1[1,2]=min(D0[1,2],D0[1,1]+D0[1,2])=min(2,0+2)=2D1[1,3]=min(D0[1,3],D0[1,1]+D0[1,3])=min(9,0+9)=9D1[2,1]=min(D0[2,1],D0[2,1]+D0[1,1])=min(8,8+0)=8D1[2,2]=min(D0[2,2],D0[2,1]+D0[1,2])=min(0,8+2)=0D1[2,3]=min(D0[2,3],D0[2,1]+D0[1,3])=min(6,8+9)=6D1[3,1]=min(D0[3,1],D0[3,1]+D0[1,1])=min(1,1+0)=1D1[3,2]=min(D0[3,2],D0[3,1]+D0[1,2])=min(∞,1+2)=3D1[3,3]=min(D0[3,3],D0[3,1]+D0[1,3])=min(0,1+9)=0016089200D0316089201D20①2891②6③k=2D2[1,1]=min(D1[1,1],D1[1,2]+D1[2,1])=min(0,2+8)=0D2[1,2]=min(D1[1,2],D1[1,2]+D1[2,2])=min(2,2+0)=2D2[1,3]=min(D1[1,3],D1[1,2]+D1[2,3])=min(9,2+6)=8D2[2,1]=min(D1[2,1],D1[2,2]+D1[2,1])=min(8,0+8)=8D2[2,2]=min(D1[2,2],D1[2,2]+D1[2,2])=min(0,0+0)=0D2[2,3]=min(D1[2,3],D1[2,2]+D1[2,3])=min(6,0+6)=6D2[3,1]=min(D1[3,1],D1[3,2]+D1[2,1])=min(1,3+8)=1D2[3,2]=min(D1[3,2],D1[3,2]+D1[2,2])=min(3,3+0)=3D2[3,3]=min(D1[3,3],D1[3,2]+D1[2,3])=min(0,3+6)=00316089201D0316088202D21①2891②6③k=3D3[1,1]=min(D2[1,1],D2[1,3]+D2[3,1])=min(0,8+1)=0D3[1,2]=min(D2[1,2],D2[