第四章dynamicprogramming技術(shù)-文庫吧資料
2025-08-07 13:32本頁面
【正文】 則可加 xm=yn到 Z， 得到一個(gè)長(zhǎng)為 k+1的 X與 Y 的公共序列 ， 與 Z是 X和 Y的 LCS矛盾 。DBLAB(2022) ?優(yōu)化子結(jié)構(gòu) 定理 1（ 優(yōu)化子結(jié)構(gòu)） 設(shè) X=(x1, ..., xm)、 Y=(y1, ..., yn) 是兩個(gè)序列， Z=(z1, ..., zk)是 X與 Y的 LCS，我們有 ： ⑴ 如果 xm=yn, 則 zk=xm=yn, Zk1是 Xm1和 Yn1的 LCS， 即 ， LCSXY = LCSXm1Yn1+ xm=yn. ⑵ 如果 xm?yn， 且 zk?xm， 則 Z是 Xm1和 Y的 LCS， 即 LCSXY= LCSXm1Y ⑶ 如果 xm?yn,且 zk?yn,則 Z是 X與 Yn1的 LCS， 即 LCSXY= LCSXYn1 HIT CSamp。DBLAB(2022) 最長(zhǎng)公共子序列結(jié)構(gòu)分析 ?第 i前綴 – 設(shè) X=(x1, x2, ..., xn)是一個(gè)序列 ， X的第 i前綴 Xi是一個(gè)序列 ， 定義為 Xi=(x1, ..., xi ) 例 . X=(A, B, D, C, A), X1=(A), X2=(A, B), X3=(A, B, D) HIT CSamp。DBLAB(2022) 最長(zhǎng)公共子序列（ LCS） 問題 輸入： X = (x1,x2,...,xn)， Y = (y1,y2,...ym) 輸出： Z = X與 Y的最長(zhǎng)公共子序列 HIT CSamp。 問題的定義 HIT CSamp。E 169。E 169。E 169。DBLAB(2022) PrintOptimalParens(s, i, j) IF j=i THEN Print “A”i。 Return m and s. 獲取構(gòu)造最優(yōu)解的信息 S[i,j]記錄 AiAi+1…A j的 最優(yōu)劃分處在 Ak與 Ak+1 之間 HIT CSamp。 m[i, j]=∞。DBLAB(2022) MatrixChainOrder(p) n=length(p)1； FOR i=1 TO n DO m[i, i]=0。 Return m. HIT CSamp。 m[i, j]=∞。DBLAB(2022) MatrixChainOrder(p) n=length(p)1； FOR i=1 TO n DO m[i, i]=0。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) 自底向上計(jì)算優(yōu)化解的代價(jià) m[i, j]= mini? k j { m[i, k] + m[k+1, j] + p0 pk p5 } 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] m[2,4] = min{ m[2,2]+m[3,4] m[2,3]+m[4,4] HIT CSamp。DBLAB(2022) 考慮到所有的 k，優(yōu)化解的代價(jià)方程為 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) ?假設(shè) – m[i, j] = 計(jì)算 Ai?j的最小乘法數(shù) – m[1, n] = 計(jì)算 A1?n的最小乘法數(shù) – A1 ... Ak Ak+1 .... An 是優(yōu)化解 (k實(shí)際上是不可預(yù)知 ) ?代價(jià)方程 m[i, i] = 計(jì)算 Ai ? i 的最小乘法數(shù) = 0 m[i, j] = m[i, k] + m[k+1, j] + pi1pkpj 其中 , pi1pkpj是計(jì)算 Ai?k?Ak+1?j所需乘法數(shù) , Ai? k和 Ak+1 ? j分別是 pi1?pk和 pk?pj矩陣 . 遞歸地定義最優(yōu)解的代價(jià) 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) ?兩個(gè)記號(hào) – Aij=Ai?Ai+1?....?Aj – cost(Aij )=計(jì)算 Aij的代價(jià) ?優(yōu)化解的結(jié)構(gòu) –若計(jì)算 A1?n的優(yōu)化順序在 k處斷開矩陣鏈 , 即A1?n=A1?k?Ak+1?n， 則在 A1?n的優(yōu)化順序中 ， 對(duì)應(yīng)于子問題 A1?k的解必須是 A1k的優(yōu)化解 ， 對(duì)應(yīng)于子問題 Ak+1?n的解必須是 Ak+1?n的優(yōu)化解 分析優(yōu)化解的結(jié)構(gòu) 具有優(yōu)化子結(jié)構(gòu)： 問題的優(yōu)化解包括子問題優(yōu)化解 HIT CSamp。DBLAB(2022) 下邊開始設(shè)計(jì)求解矩陣鏈乘法問題的Dynamic Programming算法 ? 分析優(yōu)化解的結(jié)構(gòu) ? 遞歸地定義最優(yōu)解的代價(jià) ? 自底向上地計(jì)算優(yōu)化解的代價(jià)保存之， 并獲取構(gòu)造最優(yōu)解的信息 ? 根據(jù)構(gòu)造最優(yōu)解的信息構(gòu)造優(yōu)化解 HIT CSamp。DBLAB(2022) p(n)= 1 if n=1 p(n)= if n1 p(n)=C(n1)=Catalan數(shù) = = ?(4n/n3/2) ?矩陣鏈乘法優(yōu)化問題的解空間 – 設(shè) p(n)=計(jì)算 n個(gè)矩陣乘積的方法數(shù) – p(n)的遞歸方程 p k p n kkn( ) ( )????11（ A1 ?… ? Ak)?(Ak+1?… ?An) ??????????1)1(21nnn如此之大的解空間是無法用枚舉方法求出最優(yōu)解的！ HIT CSamp。DBLAB(2022) ?矩陣鏈乘法的代價(jià)與計(jì)算順序的關(guān)系 – 設(shè) 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 結(jié)論 : 不同計(jì)算順序有不同的代價(jià) HIT CSamp。 – 計(jì)算一個(gè)矩陣鏈的乘法可有多種方法 : 例如 , （ A
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1