该去找工作了:),把以前看过的一些东西总结下。这次主要是对三个字符串问题的总结,即:最长公共子序(LCS)、最长递增子序(LIS)以及编辑距离(CSD)。这三个问题都出在算法导论动态规划一章,同时后两个问题也出现在编程之美中(编程之美中的一些题都是出自算法导论:))。这篇博客的思路是按着动态规划的“标准思路”一步一步的给出解答,最后给出代码。 动态规划的一般思路是分为四步,即:寻找最有子结构、递归定义最有子结构,自底向上求解最有子结构和构造最优解。其中,在第三步时,我们也可以自顶向下进行求解,但此时需要对解需要进行记录。 一、LCS :求两个序列的最长公共子序。 1、寻找最优子结构 假设待求解的两个序列为Xn和Ym,我们用L{Xn,Ym}表示最长公共子序。我们知道,如果我们已经知道了L{Xn-1,Ym-1}的最长公共子序,则L{Xn,Ym}=L{Xn-1,Ym-1}+1或者L{Xn,Yn}=max{L{Xn-1,Ym},L{Xn,Ym-1}}。也就是说,最长公共子序和其子问题有关。 2、递归定义最优子结构 最有子结构的顶一下如下: 3、自底向上求解最优解,代码如下: - def longest_common_subsequence(lhs,rhs):
- l_len = len(lhs);
- r_len = len(rhs);
- matrix = zeros((l_len,r_len));
- for i in arange(l_len):
- for j in arange(r_len):
- if lhs[i] == rhs[j]:
- if i != 0 and j != 0:
- matrix[i][j] = matrix[i-1][j-1]+1;
- else:
- matrix[i][j] = 1;
- elif i != 0 and j != 0:
- matrix[i][j] = max(matrix[i-1][j],matrix[i][j-1]);
- return matrix;
4、构造最优解,如下: - def print_longest_common_subsequence(lhs,rhs):
- matrix = longest_common_subsequence(lhs,rhs);
- l_len = len(lhs);
- r_len = len(rhs);
- i = l_len-1;j=r_len-1;
- rst = [];
- while j>0 and i >0:
- if matrix[i-1][j] != matrix[i][j] and matrix[i][j-1] != matrix[i][j]:
- rst. insert(0,lhs[i]);
- #print(i,j);
- j = j-1;
- i = i-1;
- elif matrix[i-1][j] == matrix[i][j]:
- i = i-1;
- else:
- j=j-1;
- if j!=0 and i== 0:
- if matrix[i][j-1] != matrix[i][j]:
- rst. insert(0,lhs[i]);
- elif j==0 and 0:
- if matrix[i][j] != matrix[i-1][j]:
- rst. insert(0,lhs[j]);
- return rst;
二、LIS:求序列的最长递增子序。 1、寻找最优子结构 我们设待求的序列为Xn,同样的如果我们已经求得了前n-1个序列的最长递增子序列,那么Xn的最长递增子序列要么等于前n-1个的最长递增子序,要么等于其加1。这里的问题有些复杂,复杂的原因就在于,前n-1个序列的最长递增子序,可能不止一个,设其长度为Ln-1。面对这种情况,我们只需用Xn的最后的元素与递增序列长度为Ln-1的最长序列的最小值进行比较。 2、递归定义最优解结构 我们递归定义最优接结构,如下: 因为序列的每一项,都可以构成长度为1的递增自序列,所以最小值为1. 3、自底向上求解最优解(与算法导论上的方法一样,只是没加记录项),代码如下:
- def longest_increasing_subsequence(tmp_str):
- tmp_len = len(tmp_str);
- LIS = [1 for i in range(tmp_len)];
- for i in range(tmp_len):
- j=0;
- while j = i:
- if (tmp_str[i] > tmp_str[j]) and (LIS[i] LIS[j]+1):
- LIS[i] = LIS[j]+1;
- j = j+1;
- return max(LIS);
注意:这个简单实现,其复杂度为O(n2),我们对其进行改进,使其时间复杂度为 O(nlog(n)),如下: - def binary_search(tmp_str,begin,end,key):
- if begin == end:
- return begin;
- middle = (begin+end)/2;
- if tmp_str[middle]==key:
- return middle;
- elif tmp_str[middle]>key:
- return binary_search(tmp_str,begin,middle,key);
- else:
- return binary_search(tmp_str,middle+1,end,key);
- def improved_LIS(tmp_str):
- tmp_len = len(tmp_str);
- LIS = [1 for i in range(tmp_len)];
- MaxV = [0 for i in range(tmp_len)];
- nMaxLIS = 0;
- for i in range(tmp_len):
- j = binary_search(MaxV,0,nMaxLIS,tmp_str[i]);
- if tmp_str[i] > MaxV[j]:
- LIS[i] = j+1;
- elif j>1:
- LIS[i] = j;
- if LIS[i] > nMaxLIS:
- nMaxLIS = LIS[i];
- MaxV[LIS[i]]=tmp_str[i];
- elif tmp_str[i] > MaxV[j] and tmp_str[i] MaxV[j+1]:
- MaxV[j+1] = tmp_str[i];
- return max(LIS),LIS;
4、构造最优解,如下: - def print_longest_increasing_subsequence(tmp_str):
- nMax,tmp_list = improved_LIS(tmp_str);
- mIndex = index = tmp_list.index(nMax);
- rst = [0 for i in range(nMax)];
- rst[0] = tmp_str[mIndex];
- j = 1;
- for i in range(mIndex):
- if tmp_list[mIndex-i] == nMax-1 and \
- tmp_str[mIndex-i]tmp_str[index]:
- index = mIndex-i;
- rst[j] = tmp_str[index];
- j=j+1;
- nMax = nMax-1;
- if nMax == 1:
- return rst;
- return rst;
三、CSD:编辑距离 1、寻找最优子结构 设两个序列为:Xn和Ym,编辑距离为:L{Xn,Ym},为了简单起见,我们假设每个操作的代价都是相同的。在进行操作的第一步时,我们可以进行如下操作,即: 1)删除Xn的一个字符,此时需要求解的是L{Xn-1,Ym}; 2)删除Ym的一个字符时需要求解的是L{Xn,Ym-1}; 3)在Xn前面添加一个和Ym第一个相同的字符,此时需要求解的是L{Xn,Ym-1}; 4)在Ym前面添加一个和Xn第一个相同的字符,此时需要求解的是L{Xn-1,Ym}; 5)修改Xn的第一个字符为Ym的第一个字符,此时需要求解的是Ln{Xn-1,Ym-1}; 6)修改Ym的第一个字符为Xn的第一个字符,此时需要求解的是Ln{Xn-1,Ym-1}; 从上面的分析中,我们可以看到,第一步之后只会存在三种情况,即:L{Xn,Ym-1}、L{Xn-1,Ym}和L{Xn-1,Ym-1} 2、递归定义最优解结构 3、我们这次不再用自顶向上的求解法,而是采用带备忘录的解法,如下:
- def longest_common_subsequence(lhs,rhs):
- l_len = len(lhs);
- r_len = len(rhs);
- matrix = zeros((l_len,r_len));
- for i in arange(l_len):
- for j in arange(r_len):
- if lhs[i] == rhs[j]:
- if i != 0 and j != 0:
- matrix[i][j] = matrix[i-1][j-1]+1;
- else:
- matrix[i][j] = 1;
- elif i != 0 and j != 0:
- matrix[i][j] = max(matrix[i-1][j],matrix[i][j-1]);
- return matrix;
通过寻找最优子结构我们知道,有些操作会得到相同结果,所以具体的求出怎么操作的比较困难,如果每个操作所花费的代价不同的话,求解具体的操作会容易些。 本文出自:http://blog./uid-28311809-id-4251024.html
|