【文章內容簡介】 n–1 = 1 + (n – 1) +∑(T(k) + T(n–k)) k=1 n–1 n–1 = n +∑T(k) + ∑T(n–k) k=1 k=1 ? 可用數(shù)學歸納法證明 T(n)≥2n–1 = Ω(2n)。 ? 直接遞歸算法的時間復雜性隨 n的指數(shù)增長。 n–1 = n + 2∑T(k) k=1 2021年 11月 12日 41 ?動態(tài)規(guī)劃中采用自底向上的方式。但是在遞歸定義中往往是自上而下的描述。備忘錄方法就采用與遞歸定義一致的自上而下的方式。 ?備忘錄方法同樣用表格來保存已解子問題的信息。每個子問題初始化時都標記為尚未求解。在遞歸求解過程中，對每個待解子問題，先查看它是否已求解。若未求解，則計算其解并填表保存。若已求解，則查表取出相應的結果。 ?備忘錄方法同樣避免了子問題的重復計算，因而和動態(tài)規(guī)劃算法具有同樣效率。 2021年 11月 12日 42 備忘錄方法 ?動態(tài)規(guī)劃算法是自底向上遞歸的； ?備忘錄方法是自頂向下遞歸的； int LookupChain(int i， int j) { if (m[i][j] 0) return m[i][j]。 if (i == j) return 0。 int u = LookupChain(i， i) + LookupChain(i+1， j) + p[i1]*p[i]*p[j]。 s[i][j] = i。 for (int k = i+1。 k j。 k++) { int t = LookupChain(i， k) + LookupChain(k+1， j) + p[i1]*p[k]*p[j]。 if (t u) { u = t。 s[i][j] = k。} } m[i][j] = u。 return u。 } int MemoizedMatrixChain (int n, int **m, int **s) { for(int i=1。 i=n。 i++) for(int j=I。 j=n。 j++) m[i][j]=0。 return LookupChain(1, n)。 } 2021年 11月 12日 43 備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。 2021年 11月 12日 44 提綱 一、動態(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的子序列是指存在一個嚴格遞增下標序列 {i1,i2,…,i k}使得對于所有j=1,2,…,k 有： zj=xij。例如，序列 Z={B,C,B,A}是序列 X={A,B,C,B,D,A,B}的子序列，相應的遞增下標序列為 {2,3,5,7}。 ?定義二： 一個給定序列的 子序列 是在該序列中刪去若干元素后得到的序列。 2021年 11月 12日 46 ?給定 2個序列 X和 Y，當另一序列 Z既是 X的子序列又是 Y的子序列時，稱 Z是序列 X和 Y的 公共子序列 。 ?例如： 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} ?最長公共子序列 :公共子序列中長度最長的子序列。 2021年 11月 12日 47 ?最長公共子序列問題 ? 給定兩個序列 X={x1,x2,…,xm} 和Y={y1,y2,…, yn} ，找出 X和 Y的一個最長公共子序列 2021年 11月 12日 48 例子 X = ?A, B, C, B, D, A, B? X = ?A, B, C, B, D, A, B? Y = ?B, D, C, A, B, A? Y = ?B, D, C, A, B, A? ??B, C, B, A?和 ?B, D, A, B?都是 X和 Y 的最長公共子序列 (長度為 4) ?但是 ,?B, C, A?就不是 X和 Y的最長公共子序列 2021年 11月 12日 49 窮舉法 ?對于每一個 Xm的子序列 ,驗證它是否是 Yn的子序列 . ? Xm有 2m個子序列 ?每個子序列需要 ?(n)的時間來驗證它是否是 Yn的子序列 . ? 從 Yn的第一個字母開始掃描下去 ,如果不是則從第二個開始 ?運行時間 : ?(n2m) 2021年 11月 12日 50 問題定義 ?最長公共子序列（ LCS）問題 ?輸入： X = (x1,x2,...,xm)， Y = (y1,y2,...yn) ?輸出： Z = X與 Y的一個最長公共子序列 ? 步驟： 1. 最長公共子序列 (LCS) 結構分析 。 2. 建立求解 LCS長度的遞歸方程 。 3. 自底向上計算 LCS的長度 。 4. 構造最優(yōu)解。 2021年 11月 12日 51 LCS結構分析 ?第 i前綴定義： ?設 X=(x1, x2, ..., xm)是一個序列 ， X的第 i前綴 Xi是一個序列 ， 定義為 Xi=(x1, ..., xi ) 例 . X=(A, B, D, C, A), X1=(A), X2=(A, B), X3=(A, B, D) 2021年 11月 12日 52 遞歸方程 第 1種情況 : xi = yj 例如 : Xi = ?A, B, D, E? Yj = ?Z, B, E? ?把 xi=yj 添加到 Xi1和 Yj1最長共同子序列中 . ?一定可以找到 Xi1和 Yj1的最長共同子序列 ? 一個問題的最優(yōu)解 一定包含了子問題的 最優(yōu)解 . ?????????????????. a nd 0, if])1,[],1[m a x(, a nd 0, if1]1,1[,0or 0 if0],[jijiyxjijicjicyxjijicjijic2021年 11月 12日 53 遞歸解法 第 2種情況 : xi ? yj 例子 : Xi = ?A, B, D, G? Yj = ?Z, B, D? ? 需要解決兩個問題 ?找到 Xi1和 Yj的一個最長共同子序列 : Xi1 = ?A, B, D?,Yj = ?Z, B, D? ?找到一個 Xi和 Yj1的一個最長共同子序列 : Xi = ?A, B, D, G?, Yj1 = ?Z, B? ?一個問題的 最優(yōu)解 一定包含了子問題的 最優(yōu)解 c[i, j] = max { c[i 1, j], c[i, j1] } 2021年 11月 12日 54 重疊子問題 ?找 Xm和 Yn的最長共同子序列 ? 我們可能需要在 Xm和 Yn1中找最長共同子序列 ,或者是在 Xm1和Yn中 . ? 上面的問題都有一個在 Xm1和 Yn1中找最長共同子序列的子問題 . ?子問題又有子子問題 2021年 11月 12日 55 LCS結構分析 ?最優(yōu)子結構： 設 X=(x1, ..., xm)、 Y=(y1, ..., yn) 是兩個序列， Z=(z1, ..., zk)是 X與 Y的一個 LCS，則有 ： ⑴ 如果 xm=yn, 則 zk=xm=yn, Zk1是 Xm1和 Yn1的 LCS， 即 ， LCS(X,Y) = LCS(Xm1,Yn1)+ xm=yn. ⑵ 如果 xm?yn， 且 zk?xm， 則 Z是 Xm1和 Y的 LCS， 即， LCS(X,Y) = LCS(Xm1,Y) ⑶ 如果 xm?yn,且 zk?yn,則 Z是 X與 Yn1的 LCS， 即， LCS(X,Y) = LCS(X,Yn1) 由此可見， 2個序列的最長公共子序列包含了這 2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有 最優(yōu)子結構性質 。 2021年 11月 12日 56 LCS結構分析 ?子問題重疊性 LCS(X,Y) LCS(Xm1,Yn1) LCS(Xm1,Y) LCS(X,Yn1) LCS(Xm2,Yn2) LCS(Xm2,Yn1) LCS(Xm1,Yn2) …… LCS問題具有子問題重疊性 2021年 11月 12日 57 LCS的遞歸方程 ? C[i][j] = Xi與 Yj 的 LCS的長度 ? LCS長度的遞歸方程 : ?????????????????jijiyxjiyxjijijicjicjicjic。0,。0,0,0]}][1[],1][[m a x {1]1][1[0]][[或2021年 11月 12日 58 LCS的長度 ?基本思想： C[i1][ j1] C[i1][j] C[i][ j1] C[i][ j] ?計算過程： C[0][0] C[0][1] C[0][3] C[0][2] C[0][4] C[1][0] C[2][0] C[3][0] C[1][1] C[2][1] C[3][1] C[1][2] C[1][3] C[1][4] C[2][2] C[2][3] C[2][4] C[3][2] C[3][3] C[3][4] 2021年 11月 12日 59 LCS的長度 void LCSLength(int m， int n， char *x，char *y， int **c， int **b) { int i， j。 for (i = 1。 i = m。 i++) c[i][0] = 0。 for (i = 1。 i = n。 i++) c[0][i] = 0。 for (i = 1。 i = m。 i++) for (j = 1。 j = n。 j++) { if (x[i]==y[j]) { c[i][j]=c[i1][j1]+1。 b[i][j]= “↖ ”。} else if (c[i1][j]=c[i][j1]) { c[i][j]=c[i1][j]。 b[i][j]= “↑”。} else { c[i][j]=c[i][j1]。 b[i][j]= “←”。 } } } c[i][j]存儲 Xi和 Yj的最長公共子序列的長度； 獲取構造最優(yōu)解的信息：b[i][j]是指針，指向計算c[i][j]時所選擇的子問題的最優(yōu)解所對應的 c表的表項。 2021年 11月 12日 60 例子 X = ?A, B, C, B, D, A,B? Y = ?B, D, C, A, B, A? 0 當 i=0或者 j=0 c[i, j] = c[i1, j1] + 1 當 xi = yj max(c[i, j1], c[i1, j]) 當 xi ? yj 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