动态规划课件.pptxVIP

*動態規劃

*7.1引言在這一章中，我們將研究一種強有力的演算法設計技術，它被廣泛用於求解組合最優化問題。使用這種技術的演算法，不是遞歸調用自身，但是問題的基礎解通常是用遞歸函數的形式來說明的。分治演算法是採用自上而下的方式求值，導致了不止一次的遞歸調用；而動態規劃法是採取自下向上的方式遞推求值，並把中間結果存儲起來以便用於後續計算。利用這種技術可以設計出特別有效演算法來解決許多組合最優化問題，也可以用來改善蠻力有哪些信誉好的足球投注网站演算法的時間複雜性，從而解決一些有NP難度的問題（詳見第10章）這種技術把一個問題的解決方案視為一系列決策的結果，還要考察每個決策序列中是否包含一個最優子序列。

*例：Fibonacci序列問題 f1=1，f2=1，f3=2，f4=3，f5=5，f6=8，f7=13,……序列中的每一個數是它前面二個數的和。這個序列遞歸定義如下：上述定義可用下麵遞歸過程來實現1.procedureFibonacciRec(n)2. ifn=1orn=2then3. return14. else5. returnFibonacciRec(n-1)+FibonacciRec(n-2)6. endif7.endprocedure

*我們不能認為上頁給出的計算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) =………………這導致了巨大數量的重複調用。

*我們用數組F[1..n]來存儲Fibonacci序列的值，由此得出自下而上的遞推計算過程。1.procedureFibonacci(n)2. F[1]←13. F[2]←14. fori←3ton5. F[i]←F[i-1]+F[i-2]6. endfor7. returnF[n]9.endprocedure//若i=1或i=2，則迴圈不執行，返回值為F[1]或F[2]。

*7.2最長公共子序列問題㈠問題描述在字母表∑上，分別給出長度為n和m的字串A和B，確定在A和B中最長公共子序列的長度。其中1≤i1i2...ik≤n（嚴格遞增下標序列）A=a1a2...an的子序列為：B=b1b2...bm的子序列為：其中1≤j1j2...jk≤m（嚴格遞增下標序列）和相等。並且例：∑={x,y,z},A=zxyxyz,B=xyyzxxyy是A（a2a3a5）和B（b1b2b3）長度為3的公共子序列，但不是A和B的最長公共子序列。xyyz是A（a2a3a5a6）和B（b1b2b3b4）長度為4的公共子序列，並且是A和B的最長公共子序列。

*㈡窮舉法可使用窮舉法求解字串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)。

*㈢動態規劃法設A=a1a2...an、B=b1b2...bm，L[i,j]表示a1a2...ai和b1b2...bj的最長公共子序列長度。設1≤i≤n、1≤j≤m，很容易證明下麵的觀察結論：觀察結論7.1（Page131）設i0且j0，那麼若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-1和b1b2...bj（j不變、i-