算法导论15-5编辑距离解答(含程序代码).doc

15-5 编辑距离 a)Given two sequences x[1 ‥ m] and y[1 ‥ n] and set of transformation-operation costs, the edit distance from x to y is the cost of the least expensive operation sequence that transforms x to y. Describe a dynamic-programming algorithm that finds the edit distance from x[1 ‥ m] to y[1 ‥ n] and prints an optimal operation sequence. Analyze the running time and space requirements of your algorithm. First,,set X[i]=x[1..i]、Y[j]=y[1..j].The edit distance‘s child problem is actually from X [i] to Y [j] optimal conversion, We will call it X [i] - Y [i] problem 。Obviously，The original problem is actually X [m] - Y [n].Set c[i, j] Said that resolution of the X [i] - Y [j] problem of the optimal cost，Then under settlement X[i]-Y[j] On the last step of the operation，The following recurrence relations can be： If the last step of the operation is COPY，Then there must be x [i] = y [j].The optimal solution to this problem depends on the X [i-1] - Y [j-1] the optimal solution, so there is c [i, j] = c [i-1, j-1] + cost (COPY); If the last step is to REPLACE, then there must be x [i]! = y [i]. (This assumes that the implementation can not use the same letters replace operation.) optimal solution to this problem also depends on x [i-1] - Y [j-1] the optimal solution, so there is c [i, j] = c [i-1, j-1] + cost (REPLACE); If the last step is TWIDDLE, then there must be x [i] = y [j-1] and x [i-1] = y [j], and asked i, j = 2. At this time, the optimal solution of this problem depends on the X [i-2] - Y [i-2] the optimal solution, so there is c [i, j] = c [i-2, j-2] + cost (TWIDDLE);  If the last step of the operation is DELETE, the operation on the x or y is not restricted. Optimal solution to this problem depends on the X [i-1] - Y [j] the optimal solution, so there is c [i, j] = c [i-1, j] + cost (DELETE); If the last step of the operation is INSERT, as there is no limit on the x and y. Optimal solution to this problem depends on the X [i] - Y [j-1] the optimal solution,