《《動(dòng)態(tài)規(guī)劃算法》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《動(dòng)態(tài)規(guī)劃算法》PPT課件（48頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Chapter 7,動(dòng)態(tài)規(guī)劃Dynamic Programming,2020/10/5,2,What is dynamic programming,與分治法類似, 動(dòng)態(tài)規(guī)劃也是通過(guò)組合子問(wèn)題的解來(lái)求解問(wèn)題. 分治算法將問(wèn)題劃分成獨(dú)立子問(wèn)題, 遞歸地解決這些子問(wèn)題, 然后組合這些子問(wèn)題的解來(lái)求解原始問(wèn)題. If these subproblems are not independent, what will happen?,2020/10/5,3,算法總體思想,動(dòng)態(tài)規(guī)劃算法與分治法類似, 其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題,2020/10/5,4,但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立

2、的. 不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí). 在用分治法求解時(shí), 有些子問(wèn)題被重復(fù)計(jì)算了許多次.,算法總體思想,2020/10/5,5,算法總體思想,T(n),Those who cannot remember the past are doomed to repeat it. (無(wú)法記取教訓(xùn)者必重蹈覆轍 ) -----George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905),如果能夠保存已解決的子問(wèn)題的答案, 而在需要時(shí)再找出已求得的答案, 就可以避免大量重復(fù)計(jì)算,

3、從而得到多項(xiàng)式時(shí)間算法.,2020/10/5,6,Fibonacci sequence(序列),Fibonacci序列定義如下： 1. procedure f(n) 2. if n=1 or n=2 then return 1 3. else return f(n-1)+f(n-2) 這種遞歸形式有簡(jiǎn)潔、容易書寫和容易查錯(cuò)等優(yōu)點(diǎn), 最主要是它的抽象性. 但是它遠(yuǎn)不是有效的算法. 算法復(fù)雜性: (n) Why???,2020/10/5,7,Fibonacci sequence分析,f(n)= f(n-1)+ f(n-2) =2f(n-2)+ f(n-3) =3f(n-3)+2f(n-4)

4、=5f(n-4)+3f(n-5),2020/10/5,8,二項(xiàng)式系數(shù)的計(jì)算,有效計(jì)算上式的方法是按行構(gòu)造帕斯卡三角形,2020/10/5,9,What is dynamic programming什么是動(dòng)態(tài)規(guī)劃？,當(dāng)子問(wèn)題發(fā)生重疊時(shí), 分治法做了很多不必要的工作重復(fù)對(duì)重疊的子問(wèn)題進(jìn)行求解. 動(dòng)態(tài)規(guī)劃算法對(duì)每個(gè)子問(wèn)題求解一次, 然后將結(jié)果保存在一張表里面, 這樣可以避免每個(gè)已求解子問(wèn)題的重復(fù)計(jì)算. 對(duì)于Fibonacci序列, 一個(gè)明顯的方法是從f(1)開始自底向上地計(jì)算到f(n), 只需要(n)時(shí)間和(1)空間. 和前面的方法相比, 可以很大程度降低時(shí)間復(fù)雜度.,2020/10/5,10,Th

5、e longest common subsequence problem最長(zhǎng)公共子序列問(wèn)題,在字母表上, 分別給出兩個(gè)長(zhǎng)度為n和m的字符串A和B, 確定在A和B中最長(zhǎng)公共子序列的長(zhǎng)度. 這里A=a1a2...an的子序列的一個(gè)形式為ai1ai2...aik的字符串, 其中每個(gè)ij在1到n之間, 并且1i1

6、n和B=b1b2...bm 令Li, j表示a1a2...ai和b1b2...bj的最長(zhǎng)公共子序列的長(zhǎng)度(i, j可能是0, 此時(shí)a1a2...ai和b1b2...bj中至少一個(gè)為空). 可得如下結(jié)論：,2020/10/5,12,遞推公式,觀察結(jié)論7.1 如果i和j都大于0, 那么 若ai=bj, Li, j=Li-1, j-1+1 若aibj, Li, j=maxLi, j-1, + Li-1, j 可得如下公式：,2020/10/5,13,,現(xiàn)在可以直接用動(dòng)態(tài)規(guī)劃技術(shù)來(lái)求解最長(zhǎng)公共子序列問(wèn)題。對(duì)每一對(duì)i和j的值，0 i n，0 j m，我們用一個(gè)(n+1)(m+1)表來(lái)計(jì)算Li, j的值，

7、只需要用上面的公式逐行地填表L0n, 0m。算法如下：,2020/10/5,14,Algorithm 7.1 LCS Input: Two strings A and B of length n and m, respectively, over an alphabet Output: The length of the longest common subsequence of A and B 1. for i0 to n 2. Li, 00 3. end for 4. for j0 to m 5. L0, j0 6. end for,2020/10/5,15,7. for

8、i1 to n 8. for j1 to m 9. if ai=bj then Li, jLi-1, j-1+1 10. else Li, jmaxLi, j-1, Li-1, j 11. end if 12. end for 13. end for 14. return Ln, m,2020/10/5,16,定理7.1 最長(zhǎng)公共子序列問(wèn)題的最優(yōu)解能夠在(nm)時(shí)間和(minm, n) 空間內(nèi)得到. ？,2020/10/5,17,A=“xyxxzxyzxy” B=“zxzyyzxxyxxz”,圖7.1 最長(zhǎng)公共子序列問(wèn)題的一個(gè)例子,2020/10/5,18,Algorith

9、m 7.1pro LCS 1. for i0 to n 2. Li, 00 3. end for 4. for j0 to m 5. L0, j0 6. end for 7. for i1 to n 8. for j1 to m 9. if ai=bj then Li, jLi-1, j-1+1, bi, j””,2020/10/5,19,10. else 11. if Li-1, jLi, j-1 then 12. Li, jLi-1, j, bi, j”” 13. else 14. Li, jLi, j-1, bi, j”” 15

10、. end if 16. end if 17. end for 18. end for 19. return Ln, m and bn, m,2020/10/5,20,print-LCS(b, A, i, j) 1. if i=0 or j=0 then return 2. if bi, j= ”” then 3. print-LCS(b, A, i-1, j-1) 4. print ai 5. else 6. if bi, j= ”” then print-LCS(b, A, i-1, j) 7. else print-LCS(b, A, i, j-1) 8. end i

11、f,2020/10/5,21,2020/10/5,22,算法的改進(jìn),在算法lcs和print-LCS中, 可進(jìn)一步將數(shù)組b省去. 事實(shí)上, 數(shù)組元素Lij的值僅由Li-1j-1, Li-1j和Lij-1這3個(gè)數(shù)組元素的值所確定. 對(duì)于給定的數(shù)組元素Lij, 可以不借助于數(shù)組b而僅借助于L本身確定Lij的值是由Li-1j-1, Li-1j和Lij-1中哪一個(gè)值所確定的.,2020/10/5,23,算法的改進(jìn),如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度, 則算法的空間需求可大大減少. 事實(shí)上, 在計(jì)算Lij時(shí), 只用到數(shù)組L的第i行和第i-1行. 因此, 用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度.

12、 進(jìn)一步的分析還可將空間需求減至O(min(m, n)).,2020/10/5,24,Matrix chain multiplication矩陣鏈相乘,設(shè)有4個(gè)矩陣A, B, C, D, 它們的維數(shù)分別是A:5010 B:1040 C:4030 D:305, 共有5種加括號(hào)的方式： (A((BC)D)) 乘法次數(shù): 16000 (A(B(CD))) 乘法次數(shù): 10500 ((AB)(CD)) 乘法次數(shù): 36000 (((AB)C)D) 乘法次數(shù): 87500 ((A(BC))D) 乘法次數(shù): 34500,2020/10/5,25,Matrix chain multiplicati

13、on矩陣鏈相乘,一般情況下, n個(gè)矩陣鏈M1M2...Mn相乘的耗費(fèi), 取決于n-1個(gè)乘法執(zhí)行的順序(結(jié)合方式). 蠻力算法: 計(jì)算出每一種可能順序的數(shù)量乘法次數(shù). 時(shí)間復(fù)雜度是：,算法復(fù)雜度分析： 對(duì)于n個(gè)矩陣的連乘積, 設(shè)其不同的計(jì)算次序?yàn)镻(n). 由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1...Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：,2020/10/5,26,假設(shè)我們有n+1維數(shù)r1, r2, ..., rn+1, 這里ri和ri+1分別是矩陣Mi的行數(shù)和列數(shù), 1in. 我們將用Mi, j記MiMi+1...Mj的乘積, 我們還假設(shè)鏈Mi,j的乘法

14、的最小耗費(fèi)用數(shù)量乘法的次數(shù)來(lái)度量, 記為Ci, j. 對(duì)于給定的一對(duì)索引i和j, 1i

15、8,Illustration of matrix chain multiplication矩陣鏈乘圖示,2020/10/5,29,Algorithm 7.2 MATCHAIN Input: An array r1..n+1 of positive integers corresponding to the dimensions of a chain of n matrices, where r1..n are the number of rows in the n matrices and rn+1 is the number of columns in Mn Output: The leas

16、t number of scalar multiplications required to multiply the n matrices 1. for i1 to n Fill in diagonal d0 2. Ci, i0 3. end for 4. for d1 to n-1 Fill in diagonals d1 to dn-1 5. for i1 to n-d Fill in entries in diagonal di 6. ji+d 7. comment: The next three lines computes Ci, j 8. C

17、i, j 9. for ki+1 to j 10. Ci, jminCi, j, Ci, k-1+Ck, j+rirkrj+1 11. end for 12. end for 13. end for 14. return C1, n,2020/10/5,30,分析,算法matrixChain的主要計(jì)算量取決于算法中對(duì)r, i和k的3重循環(huán). 循環(huán)體內(nèi)的計(jì)算量為O(1), 而3重循環(huán)的總次數(shù)為 定理7.2 一個(gè)由n個(gè)矩陣組成的鏈相乘, 它所需的數(shù)量乘法最少次數(shù)可以在(n3)時(shí)間和(n2)空間內(nèi)找出.,2020/10/5,31,M1:510 M2:104 M3:46 M2:610

18、 M5:102,圖7.3 矩陣鏈乘算法的一個(gè)例子,2020/10/5,32,動(dòng)態(tài)規(guī)劃算法的基本要素,一、最優(yōu)子結(jié)構(gòu) 矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解. 這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì). 在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí), 所用的方法具有普遍性：首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的, 然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解, 從而導(dǎo)致矛盾.,2020/10/5,33,動(dòng)態(tài)規(guī)劃算法的基本要素,一、最優(yōu)子結(jié)構(gòu) 利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì), 以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解. 最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提. 注意：同一

19、個(gè)問(wèn)題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu), 有些表示方法的求解速度更快(空間占用小, 問(wèn)題的維度低),2020/10/5,34,二、重疊子問(wèn)題,,遞歸算法求解問(wèn)題時(shí), 每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題, 有些子問(wèn)題被反復(fù)計(jì)算多次. 這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì). 動(dòng)態(tài)規(guī)劃算法, 對(duì)每一個(gè)子問(wèn)題只解一次, 而后將其解保存在一個(gè)表格中, 當(dāng)再次需要解此子問(wèn)題時(shí), 只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果. 通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng). 因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間, 從而獲得較高的解題效率.,2020/10/5,35,三、備忘錄方法,,備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同,

20、 區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看, 避免了相同子問(wèn)題的重復(fù)求解.,m0 private static int lookupChain(int i, int j) if (mij 0) return mij; if (i == j) return 0; int u = lookupChain(i+1, j) + pi-1*pi*pj; sij = i; for (int k = i+1; k < j; k++) int t = lookupChain(i, k) + lookupChain(k+1, j) + pi-1*pk*pj; if (t

21、 < u) u = t; sij = k; mij = u; return u; ,2020/10/5,36,The Dynamic Programming Paradigm動(dòng)態(tài)規(guī)劃范式,適用范圍 多階段決策的最優(yōu)化問(wèn)題 最優(yōu)解滿足最優(yōu)性原理 子問(wèn)題的重疊性 基本思想 將原問(wèn)題分解為子問(wèn)題來(lái)求解, 求出子問(wèn)題的解并由此來(lái)構(gòu)造出原問(wèn)題的解(即自下而上來(lái)求解). 在求解過(guò)程中不必回頭看以前的情況. 設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法有四個(gè)步驟.,2020/10/5,37,Basic steps of dynamic programming動(dòng)態(tài)規(guī)劃的基本步驟,找出最優(yōu)解的性質(zhì), 并刻劃其結(jié)構(gòu)

22、特征. 遞歸地定義最優(yōu)值. 以自底向上的方式計(jì)算出最優(yōu)值. 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息, 構(gòu)造最優(yōu)解.,2020/10/5,38,The all-pairs shortest path problems所有點(diǎn)對(duì)的最短路徑問(wèn)題,設(shè)G=(V, E)是一個(gè)有向圖, 其中的每條邊(i, j)有一個(gè)非負(fù)的長(zhǎng)度li, j, 如果頂點(diǎn)i到頂點(diǎn)j沒(méi)有邊, 則li, j=. 問(wèn)題是要找出從每個(gè)頂點(diǎn)到其他所有頂點(diǎn)的距離. 頂點(diǎn)x到頂點(diǎn)y的距離是指x到y(tǒng) 的最短路徑長(zhǎng)度.,2020/10/5,39,The all-pairs shortest path problems,假設(shè)V=1, 2, ..., n, 設(shè)i和j

23、是V中兩個(gè)不同的頂點(diǎn). 定義dki, j是從i到j(luò)不經(jīng)過(guò)k+1, k+2, ..., k+n中任何頂點(diǎn)的最短路徑的長(zhǎng)度. di, j0=li, j, di, j1表示i, j最多經(jīng)過(guò)頂點(diǎn)1的最短路徑 給出上述定義后, 可以遞歸的計(jì)算：,2020/10/5,40,迭代公式,2020/10/5,41,Algorithm 7.3 FLOYD Input: An nn matrix l1..n, 1..n is the length of the edge (i, j) in a directed graph G=(1, 2, ..., n, E) Output: A matrix D with Di

24、, j=the distance from i to j 1. Dl copy the input matrix l into D 2. for k1 to n 3. for i1 to n 4. for j1 to n 5. Di, j=minDi, j, Di, k+Dk, j 6. end for 7. end for 8. end for Time: (n3) Space: (n2),2020/10/5,42,Knapsack problem背包問(wèn)題,設(shè)U=u1, ..., un是一個(gè)準(zhǔn)備放入容量為C的背包中的n項(xiàng)物品的集合. 對(duì)于1jn, 令sj和

25、vi分別表示第j項(xiàng)物品的體積和價(jià)值. 要解決的問(wèn)題是用U中的一些物品來(lái)裝滿背包, 這些物品的總體積不超過(guò)C, 然而要使它們的總價(jià)值最大.,2020/10/5,43,背包問(wèn)題的遞推公式,設(shè)Vi, j用來(lái)表示從前i項(xiàng)u1...ui中取出來(lái)的裝入體積為j的背包的物品的最大值. 這樣要尋求的是Vn, C. 顯然V0, j和Vi, 0都是等于0的. 當(dāng)i, j0時(shí), 有如下結(jié)論: 觀察結(jié)論7.2 Vi, j是下面兩個(gè)量的最大值 Vi-1, j: 僅用最優(yōu)的方法取自u(píng)1...ui-1的物品去裝體積為j的背包所得到的最大價(jià)值. Vi-1, j-si+vi:用最優(yōu)的方法取自u(píng)1...ui-1的物品去裝體積為j

26、-si的背包所得到的最大價(jià)值加上物品ui的價(jià)值.,2020/10/5,44,背包問(wèn)題的遞推公式,遞推公式如下：,2020/10/5,45,Algorithm 7.4 KNAPSACK Input: A set of items U=u1...un with sizes s1, ..., sn and values v1, ..., vn and a knapsack capacity C Output: The maximum value of the problem 1. for i0 to n 2. Vi, 00 3. end for 4. for j0 to C 5. V0

27、, j0 6. end for 7. for i1 to n 8. for j1 to C 9. Vi, jVi-1, j 10. if sij then Vi, jmaxVi, j, Vi-1, j-si+vi 11. end for 12. end for 13. return Vn, C,2020/10/5,46,分析,Time: (nC) Space: (C) But it is a pseudopolynomial time algorithm! 當(dāng)背包容量c很大時(shí), 算法需要的計(jì)算時(shí)間較多. 例如, 當(dāng)c2n時(shí), 算法需要(n2n)計(jì)算時(shí)間.,2020/10/5,47,C=9 s1=2 s2=3 s3=4 s4=5 v1=3 v2=4 v3=5 v4=7,圖7.5 背包問(wèn)題算法的一個(gè)例子,2020/10/5,48,Homework,7.5 7.7 7.11 7.22,