算法设计-LEC8(4)

Applicability of dynamic programming(动态规划的适用性)– Optimal substructure: an optimal solution contains within it optimal solutions to subproblems.(优化子结构)– Overlapping subproblem: a recursive algorithm revisits the same problem over and over again; onlyθ(n2) subproblems.(迭代的解)37

38

构造最优相乘顺序(Constructing an Optimal Solution) s[i, j]: value of k such that the optimal parenthesization of Ai Ai+1… Aj splits between Ak and Ak+1.(s[i, j]:记录了Ai Ai+1… Aj的最优分割顺序位置) Optimal matrix A1..n multiplication: A1..s[1, n]As[1, n]+ 1..n. Exp: call Matrix-Chain-Multiply(A, s, 1, 6): ((A1 (A2 A3))((A4 A5) A6)).Matrix-Chain-Multiply(A, s, i, j) 1. if j> i 2. X← Matrix-Chain-Multiply(A, s, i, s[i, j]); 3. Y← Matrix-Chain-Multiply(A, s, s[i, j]+1, j); 4. return Matrix-M

ultiply(X, Y); 5. else return Ai;

最长共同子序列(Longest Common Subsequence)The sequence Z= (B, C, A) is a subsequence of X= (A, B, C, B, D, A, B). (子序列的概念) It is also a subsequence of Y= (B, D, C, A, B, A). It is a common subsequence of X and Y. (共同子序列) It is not a longest common subsequence (最长共同子序列) because Z′= (B, D, A, B) is a longer common subsequence.39

最长共同子序列例 Exp: X=<a, b, c, b, d, a, b> and Y=<b, d, c, a, b, a> LCS=<b, c, b, a> (also, LCS=<b, d, a, b>). Exp: DNA sequencing:– S1= ACCGGTCGAGATGCAG;– S2= GTCGTTCGGAATGCAT; LCS S3= GTCGGATGCA

蛮力法求LCS Brute-force method:– Enumerate all subsequences of X and check if they appear in Y.(穷举X的所有子序列，检查其是否在Y中出现，然后选出LCS)– X= (x1, x2,…, xm)有2m个子序列。

41

42

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

LCS的最优结构(Optimal Substructure of LCS)Given two sequences X= (x1, x2,…, xm) and Y= (y1, y2,…, yn) and an LCS Z= (z1, z2,…, zk) of X and Y.(给定两个序列X= (x1, x2,…, xm)和Y= (y1, y2,…, yn)他们的LCS Z= (z1, z2,…, zk) ) If xm= yn, then zk= xm andZk– 1 is an LCS of Xm– 1 and Yn– 1. (如果xm= yn,则有zk= xm,和 Zk– 1是Xm– 1和Yn– 1的LCS) If xm≠ yn, then zk≠ xm implies Z is an LCS of Xm– 1 and Y. (如果xm≠ yn,则 zk≠ xm意味Z是Xm– 1和Y的LCS) If xm≠ yn, then zk≠ yn implies Z is an LCS of X and Yn– 1. (如果xm≠ yn,则 zk≠ yn意味Z是X和Yn– 1的LCS)

LCS递归解(A Recursive Formulation of LCS)

C= length of LCS of X and Y.(C: X和Y最长共同子序列的长度) c(i, j)= length of LCS of Xi and Yj; ( c(i, j):Xi和 Yj最长共同子序列的长度) that is, C= c(m, n).

LCS算法 To compute c[i, j], we need c[i-1, j-1], c[i-1, j], and c[i, j-1]. b[i, j]: points to the table entry w.r.t. the optimal subproblem solution chosen when computing c[i, j]. ( b[i, j]:记录求解过程信息) LCS-Length(X,Y)1. m← length[X]; 2. n← length[Y]; 3. for i← 1 to m 4. c[i, 0]← 0; 5. for j← 0 to n 6. c[0, j]← 0; 7. for i← 1 to m 8. for j← 1 to n 9. if xi= yj 10. c[i, j]← c[i-1, j-1]+1 11. b[i, j]←“⊥” 12. else if c[i-1,j]≥ c[i, j-1] 13. c[i,j]← c[i-1, j] 14. b[i, j]←``↑ '' 15. else c[i, j]← c[i, j-1] 16. b[i, j]←“←“ 17. return c and b

算法分析 it simply fills in the table.(填表) Computing one table entry costs O(1) time.(一个格子的计算量) There are n· m table entries.( n· m个格子) The cost of the algorithm is O(nm).(总计算开销)

45

华中科技大学管理学院