【正文】 開始并跟著箭頭走 . ?當(dāng)我們?cè)?b[i, j]中碰到 “ ” ? xi = yj 是 最長共同子序列中的一個(gè)元素 0 1 2 6 3 4 5 yj B D A C A B 5 1 2 0 3 4 6 7 D A B xi C B A B 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ? 0 ? 0 ? 0 1 ?1 1 1 ?1 ?1 ? 1 2 ?2 ? 1 ? 1 2 ?2 ? 2 ? 2 1 ? 1 ? 2 ? 2 3 ?3 ? 1 2 ? 2 ? 2 ? 3 ? 3 ? 1 ? 2 ? 3 ? 2 3 4 1 ? 2 ? 2 ? 3 4 ? 4 2021年 11月 12日 63 思考： 若有兩個(gè)字符串 A=“xyxxzxyzxy” 和B=“zxzyyzxxyxxz”，試用 LCS算法求出最長公共子序列。 } else if (b[i][j]== “↑”) LCS(i1， j， x， b)。 if (b[i][j]==“ ↖ ”){ LCS(i1， j1， x， b)。 } } } c[i][j]存儲(chǔ) Xi和 Yj的最長公共子序列的長度； 獲取構(gòu)造最優(yōu)解的信息：b[i][j]是指針，指向計(jì)算c[i][j]時(shí)所選擇的子問題的最優(yōu)解所對(duì)應(yīng)的 c表的表項(xiàng)。} else { c[i][j]=c[i][j1]。} else if (c[i1][j]=c[i][j1]) { c[i][j]=c[i1][j]。 j++) { if (x[i]==y[j]) { c[i][j]=c[i1][j1]+1。 i++) for (j = 1。 for (i = 1。 i = n。 i++) c[i][0] = 0。 for (i = 1。0,。因此，最長公共子序列問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 4. 構(gòu)造最優(yōu)解。 2. 建立求解 LCS長度的遞歸方程 。 ?例如： X={A,B,C,B,D,A,B}， Y={B,D,C,A,B,A}，則 X和 Y的公共子序列有 {B,C,A}； {B,C,B}；{B,C,B,A} ?最長公共子序列 :公共子序列中長度最長的子序列。 ?定義二： 一個(gè)給定序列的 子序列 是在該序列中刪去若干元素后得到的序列。 2021年 11月 12日 44 提綱 一、動(dòng)態(tài)規(guī)劃算法的基本思想 二、矩陣連乘問題 三、最長公共子序列 四、最大子段和 五、 01背包問題 六、最優(yōu)二叉搜索樹 2021年 11月 12日 45 問題定義 ?Longest Common Subsequence (LCS) ?定義一： 若給定序列 X={x1,x2,…,x m}，則另一序列 Z={z1,z2,…,z k}，是 X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列 {i1,i2,…,i k}使得對(duì)于所有j=1,2,…,k 有： zj=xij。 return LookupChain(1, n)。 j=n。 i=n。 return u。 s[i][j] = k。 k++) { int t = LookupChain(i， k) + LookupChain(k+1， j) + p[i1]*p[k]*p[j]。 for (int k = i+1。 int u = LookupChain(i， i) + LookupChain(i+1， j) + p[i1]*p[i]*p[j]。 2021年 11月 12日 42 備忘錄方法 ?動(dòng)態(tài)規(guī)劃算法是自底向上遞歸的； ?備忘錄方法是自頂向下遞歸的； int LookupChain(int i， int j) { if (m[i][j] 0) return m[i][j]。若已求解，則查表取出相應(yīng)的結(jié)果。在遞歸求解過程中，對(duì)每個(gè)待解子問題，先查看它是否已求解。 ?備忘錄方法同樣用表格來保存已解子問題的信息。但是在遞歸定義中往往是自上而下的描述。 ? 直接遞歸算法的時(shí)間復(fù)雜性隨 n的指數(shù)增長。 2021年 11月 12日 39 直接遞歸中有大量重復(fù)計(jì)算 ?直接遞歸中有大量重復(fù)計(jì)算，如 A[1: 4]計(jì)算中： 1: 4 1: 1 2: 4 1: 2 3: 4 1: 3 4: 4 2: 2 3: 4 2: 3 4: 4 1:1 2: 2 3: 3 4: 4 1: 1 2: 3 1: 2 3: 3 3: 3 4: 4 2: 2 3: 3 2: 2 3: 3 1: 1 2: 2 圖中紅框標(biāo)出的都是重復(fù)計(jì)算。 ?通常不同的子問題個(gè)數(shù)隨問題的大小呈多項(xiàng)式增長。 這種性質(zhì)稱為 子問題的重疊性質(zhì) 。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。 ?在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 } 調(diào)用 Traceback(1, n,s) 即可輸出 A[1:n]的最優(yōu)計(jì)算順序 2021年 11月 12日 36 算法復(fù)雜度分析 ?時(shí)間復(fù)雜性 ?計(jì)算代價(jià)的時(shí)間 ?三層循環(huán) , 循環(huán)體內(nèi)的計(jì)算量 O(1)； ?O(n3) ?構(gòu)造最優(yōu)解的時(shí)間 : O(n) ?總時(shí)間復(fù)雜性為： O(n3) ?空間復(fù)雜性 ?使用數(shù)組 m和 S ?需要空間 O(n2) 2021年 11月 12日 37 動(dòng)態(tài)規(guī)劃算法的基本要素 一、最優(yōu)子結(jié)構(gòu) ?矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。 cout “and A”(s[i][j]+1)“,”j。 Traceback(s[i][j]+1,j,s)。 2021年 11月 12日 35 構(gòu)造最優(yōu)解 void Traceback(int i, int j, int* *s) { if (i = =j) return。 3500 5 類似的，當(dāng) r= 6時(shí)，可以計(jì)算出相應(yīng)的 [i][j]及其相應(yīng)的斷點(diǎn) s[i][j]，如下圖中所示： 9375 3 7125 3 5375 3 11875 3 10500 3 15125 3 由 m[1][6]=15125可知這 6個(gè)矩陣連乘積的最小運(yùn)算次數(shù)為15125。 4375 3 當(dāng) r=3， i=3時(shí)，執(zhí)行 第 (5)句 計(jì)算 [3:3][4:5]， 3] 5][4][5] + p[2]*p[3]*p[5] = 1000 +15*5*20 = 2500 2500 3 執(zhí)行 第 (7)句 計(jì)算 [3:4][5:5]， t = m[3][4] [5][5]+ p[2]*p[4]*p[5] = 750+0+15*10*20 = 3750＞ 2500，所以[3][5]仍為 2500，斷點(diǎn)仍為 3。 15750 2625 750 1000 5000 1 2 3 4 5 當(dāng) r=3， i=1時(shí)，執(zhí)行 第 (5)句 計(jì)算 A[1:1][2:3]， m[1][3] = m[2][3] + p[0]*p[1]*p[3] = 2625 +30*35*5 = 7875 7875 1 執(zhí)行 第 (7)句 計(jì)算 A[1:2][3:3]， t = m[1][2] + m[3][3] + p[0]*p[2]*p[3] = 15750+0+35*15*5 = 18375＞ 7875，所以m[1][3]不變，斷點(diǎn)仍為 1。 0 0 0 0 0 0 當(dāng) r=2，執(zhí)行 第 (5)句 完成了相鄰矩陣 [i][i+1]=p[i–1]*p[i]*p[j] 的計(jì)算，并在 s[i][j]中添入了相應(yīng)的斷點(diǎn)。 i = n。 MatrixChain用矩陣 m[i][j], s[i][j]存放子問題 A[i: j]的最小計(jì)算量以及相應(yīng)的斷點(diǎn)。此處分開是為 了給 m[i][j]賦初值。 s[i][j] = k。 k++) { ? int t = m[i][k] + m[k+1][j] + p[i– 1]*p[k]*p[j]。 //記下斷點(diǎn) i ? (7) for (int k = i + 1。 ? (5) m[i][j] = m[i+1][j] + p[i– 1]*p[i]*p[j]。 i = n – r +1。 r = n。 i++) m[i][i] = 0。 2021年 11月 12日 32 2021年 11月 12日 33 消除重復(fù)的矩陣連乘算法 ? Void MatrixChain(int p, int n, int **m, int **s) ? { for (int i = 1。因此算法的計(jì)算時(shí)間上界為O(n3)。} } } } 獲取構(gòu)造最優(yōu)解的信息：S[i][j]記錄 A[i:j]的最優(yōu)次序的斷開位置 k 2021年 11月 12日 31 A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 ??????????????????????????????1 1 3 7 520213504 3 7 5]5][5[]4][2[7 1 2 5205351 0 0 02 6 2 5]5][4[]3][2[1 3 0 0 02021352 5 0 00]5][3[]2][2[m i n]5][2[541531521pppmmpppmmpppmmm算法復(fù)雜度分析： 算法 matrixChain的主要計(jì)算量取決于算法中對(duì) r， i和 k的 3重循環(huán)。 if (t m[i][j]) { m[i][j] = t。 k j。 s[i][j] = i。 i++) { int j=i+r1。 r++) /* 計(jì)算第 r個(gè)對(duì)角線 */ for (int i = 1。 for (int r = 2。 i = n。在計(jì)算過程中，保存已解決的子問題答案。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。 具有最優(yōu)子結(jié)構(gòu)： 問題的最優(yōu)解包括子問題的最優(yōu)解 2021年 11月 12日 24 分析最優(yōu)解的結(jié)構(gòu) ?子問題重疊性 A1?A2?A3?A4 (A1)?(A2?A3?A4) (A1?A2)?(A3?A4 ) (A1?A2? A3)?(A4 ) (A2?A3) (A3? A4) (A1?A2) (A2?A3) (A3?A4) (A1? A2) (A3 4) (A3? 4) 2 具有子問題重疊性 (A2? 3) (A2 3) 2021年 11月 12日 25 ? 假設(shè) ?m[i][j]=計(jì)算 A[i:j]的最小乘法數(shù) ?設(shè) （ Ai...Ak） （ Ak+1 ...Aj)是最優(yōu)化解 (k實(shí)際上是不可預(yù)知 ) 考慮到所有的 k，最優(yōu)值的遞歸方程為： m[i][ j]= 0 if i=j m[i][ j]= mini?kj{ m[i][ k]+m[k+1][ j]+pi1 pk pj } if ij 其中 , pi1pkpj 是計(jì)算 A[i:k]?A[k+1:j]所需乘法數(shù) ,A[i:k]和 A[k+1:j]分別是 pi1?pk和 pk?pj矩陣 . 這里 的維數(shù)為 iA ii pp ??12021年 11月 12日 26 建立遞歸關(guān)系 ?????????????? jipppjkmkimjijimjki }],1[],[{mi n0],[1jki 的位置只有 種 可能 k ij??可以遞歸地定義 m[i,j]為： k∈ (i,i+1,……j1) 2021年 11月 12日 27 ? 對(duì)于 1≤i≤j≤n不同的有序?qū)?(i,j)對(duì)應(yīng)于不同的子問題。 ? 原理： ?