算法设计与分析研讨chap8(dynamic programming2014y).ppt

* zhengjin,Central South University * * * Edit Distance Problem: Given two strings, how to get the edit distance? Strategy 1: get all possible alignments between two strings; search through all of them for the best one. Strategy 2: Dynamic programming * zhengjin,Central South University * * * Edit Distance Dynamic Programming for Edit Distance Given two strings x[1..m], y[1..n], find the Edit Distance between x and y ：E(m, n). What are the subproblems? How about the edit distance between some prefix of strings（字符串前缀）: E X P O N E N T I A L P O L Y N O M I A L x[1..i], y[1..j] subproblem E(i, j) * zhengjin,Central South University * * * Edit Distance Subproblem E(7, 5) subproblem E(i, j): express E(i, j) in terms of smaller subproblems * zhengjin,Central South University * * * Edit Distance subproblem E(i, j): express E(i, j) in terms of smaller subproblems What do we know about the best alignment between x[1..i], y[1..j]? rightmost column（最右边那列有4种比对可能） * zhengjin,Central South University * * * Edit Distance rightmost column E(i, j) E(i-1, j) E(i,j)=1+E(i-1,j) Relationship E(i, j) E(i, j-1) E(i,j)=1+E(i,j-1) Relationship E(i, j) E(i-1, j-1) E(i,j)=1/0+E(i-1,j-1) Relationship * zhengjin,Central South University * * * Edit Distance（递推关系式） If x[i]=x[j] then diff(i, j)=0, otherwise diff(i, j)=1. E(0, j)=j. E(i, 0)=i. * zhengjin,Central South University * * * Edit Distance The answers to all the subproblems E(i, j) form a two-dimensional table（用二维表格记录所有子问题的最优解）. * zhengjin,Central South University * * * Edit Distance Edit distance of EXPONENTIAL and POLYNOMIAL * zhengjin,Central South University * * * Edit Distance DPEditDis(x[1..m], y[1..n]) For i=0 to m do E(i, 0)=i; 2. For j=1 to n do E(0,j)=j; //初始化 3. For i=1 to m do //以行序计算 for j=1 to n do E(i,j)=min{E(i-1,j)+1, E(i,j-1)+1, E(i-1,j-1)+diff(i, j)} 4. Return E(m,n). Running time: O(mn) * zheng