第四章dynamicprogramming技術-全文預覽

　　

【正文】 m1和 Y的 LCS， 即 LCSXY= LCSXm1Y ⑶ 如果 xm?yn,且 zk?yn,則 Z是 X與 Yn1的 LCS， 即 LCSXY= LCSXYn1 HIT CSamp。DBLAB(2022) 最長公共子序列（ LCS） 問題 輸入： X = (x1,x2,...,xn)， Y = (y1,y2,...ym) 輸出： Z = X與 Y的最長公共子序列 HIT CSamp。E 169。E 169。 Return m and s. 獲取構造最優解的信息 S[i,j]記錄 AiAi+1…A j的 最優劃分處在 Ak與 Ak+1 之間 HIT CSamp。DBLAB(2022) MatrixChainOrder(p) n=length(p)1； FOR i=1 TO n DO m[i, i]=0。 m[i, j]=∞。DBLAB(2022) m[i, j]= mini? k j { m[i, k] + m[k+1, j] + pi1 pk pj } m[1,5] m[1,1] m[4,4] m[5,5] m[2,2] m[3,3] m[4,5] m[3,4] m[2,3] m[1,2] m[1,3] m[2,4] m[3,5] m[1,4] m[2,5] HIT CSamp。DBLAB(2022) 考慮到所有的 k，優化解的代價方程為 m[i, j]= 0 if i=j m[i, j]= mini?kj{ m[i, k]+m[k+1, j]+pi1 pk pj } if ij HIT CSamp。DBLAB(2022) ?子問題重疊性 A1?A2?A3?A4 (A1)?(A2?A3?A4) (A1?A2)?(A3?A4 ) (A1?A2? A3)?(A4 ) (A2?A3) (A3? A4) (A1? A2) (A3?A4) (A1?A2) (A2?A4) 具有子問題重疊性 2 HIT CSamp。DBLAB(2022) 下邊開始設計求解矩陣鏈乘法問題的Dynamic Programming算法 ? 分析優化解的結構 ? 遞歸地定義最優解的代價 ? 自底向上地計算優化解的代價保存之， 并獲取構造最優解的信息 ? 根據構造最優解的信息構造優化解 HIT CSamp。DBLAB(2022) ?矩陣鏈乘法的代價與計算順序的關系 – 設 A1=10?100矩陣 , A2=100?5矩陣 , A3=5?50矩陣 T((A1?A2)?A3)=10?100?5+10?5?50=7500 T(A1?(A2?A3))=100?5?50+10?100?50=750000 結論 : 不同計算順序有不同的代價 HIT CSamp。E 169。E 169。DBLAB(2022) ? 使用 Dynamic Programming的條件 – Optimal substructure（ 優化子結構 ） ? 當一個問題的優化解包含了子問題的優化解時 ，我們說這個問題具有優化子結構 。DBLAB(2022) ? Divideandconquer技術的問題 – 子問題是相互獨立的 – 如果子問題不是相互獨立的 ， 分治方法將重復計算公共子問題 ， 效率很低 ? 優化問題 – 給定一組約束條件和一個代價函數 ， 在解空間中搜索具有最小或最大代價的優化解 – 很多優化問題可分為多個子問題 ， 子問題相互關聯 ， 子問題的解被重復使用 Why? HIT CSamp。DBLAB(2022) 參考資料 《 Introduction to Algorithms》 ? 第 15章 : , , , 《 計算機算法設計與分析 》 ? 第 3章 : , , , , 《 網站資料 》 ? 第四章 HIT CSamp。DBLAB(2022) 第四章 Dynamic Programming技術 駱吉洲 計算機科學與工程系 HIT CSamp。E 169。E 169。E 169。E 169。DBLAB(2022) ? Dynamic Programming算法的設計步驟 – 分析優化解的結構 – 遞歸地定義最優解的代價 – 自底向上地計算優化解的代價保存之 ， 并獲取構造最優解的信息 – 根據構造最優解的信息構造優化解 HIT CSamp。DBLAB(2022) ? 輸入： A1, A2, ..., An, Ai是矩陣 ? 輸出： 計算 A1?A2?...?An的最小代價方法 問題的定義 矩陣乘法的代價 /復雜性 : 乘法的次數 若 A是 p?q矩陣， B是 q?r矩陣，則 A?B 的代價是 O(pqr) HIT CSamp。E 169。E 169。E 169。E 169。E 169。 FOR l=2 TO n DO /* 計算地 l對角線 */ FOR i=1 TO nl+1 DO j=i+l1。E 169。 FOR k?i To j1 DO q = m[i, k]+m[k+1, j]+pi1 pk pj IF qm[i, j] THEN m[i,j]=q， s[i,j]=k。 ELSE Print “(” PrintOptimalParens(s, i, s[i, j]) PrintOptimalParens(s, s[i, j]+1, j) Print “)” ? 構造最優解 調用 PrintOptimalParens(s, 1, n) 即可輸出 A1?n的優化計算順序 S[i, j]記錄 Ai …A j的最優劃分處 ； S[i, S[i,j]]記錄 Ai …A s[i,j]的最優劃分處 ； S[S[i,j]+1, j]記錄 As[i,j]+1 …A j的最優劃分處 . HIT CSamp。DBLAB(2022) Longest Common Susequence ? 問題的定義 ? 最長公共子序列 (LCS) 結構分析 ? 建立求解 LCS長度的遞歸方程 ? 自底向上 LCS長度的計算 ? 構造優化解 HIT CSamp。E 169。E 169。 于是 zk=xm=yn。 設不然，則存在 Xm1與 Yn1的公共子序列 W， W的 長大 于 k1。DBLAB(2022) ⑵ X=x1, …, x m1, xm, Y=y1, …, y n1, yn， xm?yn， zk?xm， 則 LCSXY= LCSXm1Y 由于 zk?xm， Z是 Xm1與 Y的公共子序列。 HIT CSa