再议LCS(最长公共子序列)

上次在实验室作《从分治到动归 – 最优问题解法》的讲座的时候,举了LCS(最长公共子序列)作为例子。当时讲的是传统的动态规划解法。下面先提一下这个解法作为铺垫。

LCS问题

LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列。

例如:

X={A,B,C,B,D,A,B}

Y={B,D,C,A,B,A}

则X和Y的最长公共子序列(之一)是{B,C,B,A}

传统动归解LCS

设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有:

f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}

其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”,否则为“0”。

初值:f[i][0]=0 f[0][i]=0 f[1][1] = same(1,1)

这个动归方程乍看可能不好理解。它的思想是这样的。

对于已知f[i][j]的值,要往后拓展,有这两种情况:其末位i和j相同,或不相同。

考虑相同情况。因为i和j相同,它们必然已被记入最长公共子序列的部分。此时要想延长这个公共子序列,只得令i和j都向后移,看看它们后一位是否也相同。这就是f[i][j]+same(i+1,j+1)。

而对于不同情况,有这几种可能: 虽然第i和j位不相同,但i和j+1是相同的。此时要想延长,便是f[i][j+1]的情况。当然也可能i+1和j相同,便是f[i+1][j]的情况。

综上,写成递归式,因为不知道前一个状态的情况,所以便在这三种可能中取最大值。此时f[i][j]变为f[i-1][j-1],f[i][j+1]变为f[i-1][j],f[i+1][j]变为f[i][j-1]。便得到了上面的递归式。而初值很好理解,这里就不赘述了。

不难算出,这个算法的时间复杂度是O(n^2),空间复杂度也是O(n^2),但因为状态只与上一行有关,所以可以将空间复杂度优化至O(n)。

另一种解法?(以下内容有误,13/10/25勘误)

网络上还能找到另一种解决这个问题的方法:

(1)将两个字符串分别以行和列组成矩阵。

(2)计算每个节点行列字符是否相同,如相同则为1。

(3)通过找出值为1的最长对角线即可得到最长公共子串本方法只能得到最长连续公共子串,下列讨论关于最长公共子串全部应替换为最长连续公共子串。

为进一步提升该算法,我们可以将字符相同节点的值加上左上角(d[i-1,j-1])的值,这样即可获得最大公共子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。

这个方法非常好理解,直观易懂。而不难发现它的时间复杂度,竟然也是O(n^2),空间复杂度也可以由O(n^2)优化到O(n)!

这是巧合吗?

我们来分析一下这个做法。首先我们能总结出这个方法的递推式:d[i][j]=d[i-1][j-1]+same(i,j)。是不是很眼熟?但和上面的还不大一样啊?缺了两种情况呢。

别急,这个方法还需要在全矩阵中找出最大的值。而上面的动归方程,分散在各个状态求max的过程,合并起来,不就是求全矩阵的最大值吗?这段也有错误。详见下方勘误。

殊途同归!

动归解法通过记录各个不同截取位置的方法,避免朴素解法中的重复比较,从而提升了效率。而这个方法中的矩阵,其作用不难发现,也是一种记录的行为。

思想只存于我们的脑子中,我们的思维使算法发生了变化。但其结果,却殊途同归。

算法,是一种哲学。

2013年10月25日勘误

Leave a Reply

Your email address will not be published. Required fields are marked *