算法講義-Chapter-4 動態(tài)規(guī)劃

1、4 動態(tài)規(guī)劃Dynamic Programming引例：費氏數(shù)列費氏數(shù)列是由13世紀的意大利數(shù)學家、來自Pisa的 Leonado Fibnacci發(fā)現(xiàn)。費氏數(shù)列是由0，1開始，之后的每一項等于前兩項之和： 0，1，1，2，3，5，8，13，21，34，55，89，144. 。這個數(shù)列有如下一些特性：前2個數(shù)相加等于第3個數(shù)前1個數(shù)除以后一個數(shù)越往后越無限接近于0.618 (黃金分割)相鄰的兩個比率必是一個小于一個大于后1個數(shù)除以前一個數(shù)越往后越無限接近于遞歸形式的算法：procedure Fib(n) if n=1 or n=2 then return 1 else return Fib(n

2、-1)+Fib(n-2)簡潔，容易書寫以及調(diào)試。 效率低下 。 優(yōu)點：缺點：為何效率低下？使用直觀的方式分析存在大量重復計算使用時間復雜性的方式分析即時間復雜度為輸入規(guī)模的指數(shù)形式。當n=100時，用遞歸求解的時間T(100)3.531020, 若每秒計算108次，需111,935年!解決方法借助于變量存儲中間計算結果，消除重復計算。代碼片斷如下：f1 1f2 1for i 3 to n result f1+f2 f1 f2 f2 resultend forreturn result動態(tài)規(guī)劃的基本思想 動態(tài)規(guī)劃的實質(zhì)是分治和消除冗余，是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解

3、以避免計算重復的子問題，來解決最優(yōu)化問題的算法策略?；静襟E：找出最優(yōu)解的性質(zhì)，并刻劃其結構特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。矩陣鏈相乘 給定n個連乘的矩陣M1M2 Mn-1 Mn，問：所需要的最小乘法次數(shù)是多少次？對應此最小乘法次數(shù)，矩陣是按照什么結合方式相乘的？觀察發(fā)現(xiàn)：多個矩陣連乘時，相乘的結合方式不同，所需要的乘法次數(shù)大不相同。所需要的乘法次數(shù)為：表示個矩陣連乘所有可能的結合方式,下面設法求出其解析解。按照何種結合方式相乘，所需要的乘法次數(shù)最少？窮舉法：1.找出所有可能的相乘結合方式；2.計算每種相乘結合方式所需要的乘法次數(shù);

4、 3.求min;結論：窮舉法復雜度太高。使用動態(tài)規(guī)劃法：計算所需的最小乘法次數(shù)。 時，原問題得解。輸入： r1.n+1: 表示n個矩陣規(guī)模的n+1個整數(shù).輸出： n個矩陣連乘的最小乘法次數(shù).1. for i1 to n 填充對角線d02. Ci,i 03. end for4. for d1 to n-1 填充對角線d1到dn-15. for i1 to n-d 填充對角線di的每個項目6. ji+d 該對角線上j,i滿足的關系7. Ci,j 8. for ki +1 to j9. Ci,j min Ci,j, Ci,k-1+ Ck,j+ rirkrj+110. end for11. end f

5、or12.end for13.return C1,n一個實例C1,1=0(M1)C1,2=200(M1 M2)C1,3=320C1,4=620C1,5=348C2,2=0(M2)C2,3=240(M2 M3)C2,4=640(M2) (M3M4)C2,5=248C3,3 =0(M3)C3,4=240(M3M4)C3,5=168C4,4 =0(M4)C4,5=120(M4 M5)C5,5 =0(M5) min平面凸多邊形最優(yōu)三角劃分 平面多邊形由在同一平面且不在同一直線上的多條線段首尾順次連結且不相交所組成的圖形叫做多邊形。平面凸多邊形弦：連接平面多邊形的任意兩個不同頂點的線段。平面凸多邊形：如

6、果一個平面多邊形的任意一條弦，要么在該多邊形的內(nèi)部，要么恰好為該多變形的邊，那么，稱該平面多邊形為凸的。三角劃分將平面凸多邊形分割成互不相交的三角形。平面凸多邊形的表示：用平面凸多邊形頂點的逆時針序列表示凸多邊形，即P=v0, v1,vn表示具有n1條邊的平面凸多邊形。1. 給定一個平面凸多邊形P，其三角劃分不是唯一的。2. 給定平面凸多邊形P，對于P的每種三角劃分，可以定義一個權函數(shù)(例如： 三角劃分中所有三角形的邊長之后)。3. 最優(yōu)三角劃分：使得權函數(shù)取最小值的三角劃分。問題：給定平面凸多邊形P=v0, v1,vn，求： P的最優(yōu)三角劃分。(不妨假設：權函數(shù)定義為三角劃分中所有三角形的邊

7、長之和)現(xiàn)在要求： 權函數(shù)的最小值，以及對應該最小值的三角劃分方式。矩陣連乘：最小乘法次數(shù)，以及對應該最小乘法次數(shù)的矩陣結合方式。類比若P =v0, v1,vn是一個凸多邊形，那么vi-1,vi,vj所構成的必定也是一個凸多邊形。定義Ci,j 為子凸多邊形vi-1,vi,vj的最優(yōu)三角劃分所對應的權函數(shù)值，即其最優(yōu)值。退化的多邊形vi-1 ,vi的權值最長公共子序列問題給定兩個定義在字符集上的字符串A和B，長度分別為n和m，現(xiàn)在要求它們的最長公共子序列的長度值(最優(yōu)值)，以及對應的子序列(最優(yōu)解) 。子序列 的一個子序列是形如下式的一個字符串： ,其中 例如：但是xz, yz, xyz不是它的

8、子序列。 子序列可以是 : “”, z, x, y, zx, zy, xy, zxy。窮舉法(Brute-Force)：找出A字符串所有可能的子序列(2n)；對于A的每一個子序列， 判斷其是否是B的一個子序列,需要的時間為(m) ; 求max;總的時間為 (m 2n).最長公共子序列的長度值max輸入：兩個字符串A, B, 長度分別為n, m.輸出：X和Y的最長公共子序列長度.1 for i 0 to n2 Ci,0 03 end for4 for j 0 to m5 C0,j 06 end for7 for i 1 to n8 for j 1 to m9 if ai=bj then Ci,

9、j Ci1, j1+110 else Ci, jmaxCi, j1,Ci 1, j11 end if12 end for13. end for14. return Cn,m一個實例： 0 1 2 3 4 5 6012345使用一個(n+1)(m+1)的表格來進行計算。逐行填滿表格，問題得解。 0 0 0 0 0 0 000000 0 1 1 1 1 1 0 1 1 2 2 2 0 1 1 2 2 2 0 1 1 2 2 2 0 1 1 2 2 3因為a5=b6 , 所以C5, 6 = C4,5 + 1 = 2+1=3因為a3! =b4 , 所以C3, 4 = maxC3, 3,C2, 4= m

10、ax1,2 = 20-1背包問題給定n個物品u1,u2,un和一個背包，物品i 的重量為wi，價值為vi，已知背包的承重量為C。問：在不撐破背包的條件下，選擇哪些物品裝入背包，得到的總價值最大？之所以稱為0-1 背包問題，是因為一個物品要么裝入、要么不裝入，這兩種狀態(tài)分別用1 和0 表示。u1u2u3unC?w1w2w3wnv1v2v3vn 0-1背包問題的形式化描述： 給定C0 , wi0, vi0, 1in, 找出一個n 元的0-1 向量(x1,x2,xn)，xi0,1, 1in, 求如下優(yōu)化問題：設Vi,j表示從前i個物品u1,u2,ui中取出一部分裝入承重量為j的背包所能取得的最大價值

11、。那么，當i=n,j=C時， Vn,C 就是原問題的解。u1u2ui-1uij?w1w2wi-1wiv1v2vi-1viwij-wiu1u2ui-1w1w2wi-1v1v2vi-1Vi-1,j-wi ju1u2ui-1w1w2wi-1v1v2vi-1Vi-1,j Case 1:Case 2:輸入：物品集合u1,u2,un，重量分別為w1, w2,wn，價值分 別為v1,v2,vn, 承重量為C的背包輸出：背包所能裝物品的最大價值1. for i0 to n2. Vi,0 03. end for4. for j0 to C5. V0,j 06. end for7. for i1 to n /前i

12、個物品8. for j1 to C /承重量C與物品重量wi均為整數(shù)，故j為整數(shù)9. Vi,j Vi-1,j10. if wi j then Vi,j max Vi,j, Vi-1,j-wi+vi11. end if12. end for13. end for14. return Vn,C 0 1 2 3 4 5 6 7 8 901234 0 0 0 0 0 0 0 0 0 00000因為w3=4=j=7; 所以V3, 7 = maxV3-1,7, V3-1,7-w3+v3 = maxV2,7, V2,3+5= max7,4+5 = 9 0 3 3 3 3 3 3 3 3 0 3 4 4 7

13、7 7 7 7 0 3 4 4 7 8 9 9 12 0 3 4 5 7 8 10 11 12一個實例 背包的承重量為C=9；給定4個物品，重量(w)分別為2，3，4，5；價值(v)依次為3，4，5，7。問：背包中最多能裝的物品的總價值是對少？多邊形游戲給定N個頂點的多邊形，每個頂點標有一個整數(shù)，每條邊上標有+(加)或是(乘)號，并且N條邊按照順時針依次編號為1N。下圖給出了一個N4個頂點的多邊形。-74251234游戲規(guī)則(1) 首先，移走一條邊。 (2) 然后進行下面的操作：選中一條邊E，該邊有兩個相鄰的頂點，不妨稱為V1和V2。對V1和V2頂點所標的整數(shù)按照E上所標運算符號(+或是)進行

14、運算，得到一個整數(shù)；用該整數(shù)標注一個新頂點，該頂點代替V1和V2 。持續(xù)進行此操作，直到最后沒有邊存在，即只剩下一個頂點。該頂點的整數(shù)稱為此次游戲的得分(Score)。-74251234-7425124 Remove edge 3 Pickedge 1 -24224Pickedge 4 -442Pickedge 2 0任務：給定一個多邊形，頂點和邊已按上述方式進行標注。問：按照游戲規(guī)則，最高得分(最優(yōu)值)是多少？對應該最高得分，按照什么順序移走邊(最優(yōu)解)？輸入文件：文件中存儲了多邊形的信息，該文件中有兩行數(shù)據(jù) ：第一行是一個整數(shù)N第二行按照 邊 頂點 邊 頂點 . 邊 頂點 的順序以此存放了

15、N個頂點和N條邊的標注信息。其中字符t表示+，字符x表示。例如，下圖對應的為： 4 t -7 t 4 x 2 x 5-74251234輸出文件：文件，該文件中有兩行數(shù)據(jù) ：第一行是該游戲可能的最高得分。第二行列出第一次移走哪條邊(可能有多個, 如果是多個，則按照遞增順序排列)，會導致最高得分的出現(xiàn)。例如，下圖對應的為：331 2-74251234思路Brute-Force方法：時間復雜度為T(n)=(n!)分析：關鍵在于乘法運算同號得正，異號得負，如果a和b都是負數(shù)，a*b有可能得到一個很大的正數(shù)。因此需要同時保存子問題的最大值和最小值。從頂點i開始，按順時針長度為L的鏈的計算結果最小值為Fm

16、in(i,L)，最大值為Fmax(i,L) ，聯(lián)結第i個頂點和其順時針方向的下一個頂點(i mode n +1)的邊上的運算符記為opr(i)，則可以得到以下遞歸公式：注意：第i個頂點沿順時針方向后的第t個頂點的編號為：( i+(t-1) )mod n +1i +(i+t) mod n +1tL-t-1公式中(i+t) mod n +1是頂點i順時針方向后的第個t+1頂點的編號，V(i)為頂點i上所標的數(shù)字，opr(i)為聯(lián)結第i個頂點和其順時針方向的下一個頂點i mod n +1的邊上的運算符。根據(jù)上述公式，我們可以求出所有的Fmax(i,n)，(i=1,2,n)，其中的最大值就是問題的解。

17、高性能計算機任務分配問題數(shù)據(jù)說明：任務計算節(jié)點- 1份A類子任務- 1份B類子任務第i個節(jié)點所需最短計算時間: p=1 分析:節(jié)點i完成所分配的任務時,最后所完成的子任務不是A類子任務就是B類子任務.? 節(jié)點i完成任務(a,b)所花的最短時間,(最后完成的一項子任務是A類子任務)節(jié)點i完成任務(a,b)所花的最短時間,(最后完成的一項子任務是B類子任務)邊界值: 現(xiàn)在我們已經(jīng)知道節(jié)點i完成任務(a,b)所需要的最短時間為fi(a,b)，下面的問題就變成，有 (nA ,nB) 項任務，有p個節(jié)點可以并行地完成該任務，每個節(jié)點完成任務(a,b)所需要的最短時間為fi(a,b)已知，如何分配任務使得完成全部任務的時間最短。這樣這個問題已經(jīng)變成一個很簡單且經(jīng)典的動態(tài)規(guī)劃問題了。 設Ci(a,b)表示將任務(a,b)分配給前i個節(jié)點，并行完成這些任務所需要的最短的時間。則原來題目所求就是Cp(nA ,nB)。我們可以寫出遞歸式： 其中:表示無窮大，表示此情形是不可能