最长公共子序列

✍ dations ◷ 2025-06-08 15:16:36 #算法,动态规划,组合数学,多项式时间问题,NP完全问题

最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是:子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题,也是数据比较(英语:data comparison)程序,比如Diff工具,和生物信息学应用的基础。它也被广泛地应用在版本控制,比如Git用来调和文件之间的改变。

一个数列 S {\displaystyle S} ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 S {\displaystyle S} 称为已知序列的最长公共子序列。

对于一般性的LCS问题(即任意数量的序列)是属于NP-hard。但当序列的数量确定时,问题可以使用动态规划(Dynamic Programming)在多项式时间内解决。

最长公共子序列问题存在最优子结构:这个问题可以分解成更小,更简单的“子问题”,这个子问题可以分成更多的子问题,因此整个问题就变得简单了。最长公共子序列问题的子问题的解是可以重复使用的,也就是说,更高级别的子问题通常会重用低级子问题的解。拥有这个两个属性的问题可以使用动态规划算法来解决,这样子问题的解就可以被储存起来,而不用重复计算。这个过程需要在一个表中储存同一级别的子问题的解,因此这个解可以被更高级的子问题使用。

动态规划的一个计算最长公共子序列的方法如下,以两个序列 X {\displaystyle X} Y {\displaystyle Y} 为例子:

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

其中, s a m e ( a , b ) {\displaystyle same(a,b)} X {\displaystyle X} 的第 a {\displaystyle a} 位与 Y {\displaystyle Y} 的第 b {\displaystyle b} 位完全相同时为“1”,否则为“0”。

此时, f {\displaystyle f} 中最大的数便是 X {\displaystyle X} Y {\displaystyle Y} 的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。

该算法的空间、时间复杂度均为 O ( n 2 ) {\displaystyle O(n^{2})} ,经过优化后,空间复杂度可为 O ( n ) {\displaystyle O(n)}


下面算法计算了所有子问题的最长公共子序列长度C

相关

  • 证书广义上的证书,用来证明某些特殊专长所使用,或身份证明使用。 证书(Certificate)可以指:
  • 赛尔基因赛尔基因公司(Celgene Corporation),或译新基公司,是一家总部位于美国新泽西州萨米特的生物科技公司,主要生产抗癌和消炎药。它本是塞拉尼斯公司旗下一部门,1986年独立出来自成门
  • 沧龙科沧龙超科(Mosasauroidea),Mosa在拉丁语意为荷兰的默兹河(Meuse river),sauros在希腊文意为蜥蜴。沧龙类是种如蛇般弯曲的海生爬行动物。第一个沧龙类化石在1780年于默兹河流域的马
  • オリコンOricon(日语:オリコン Orikon */?)是以提供音乐排行榜(英语:Record chart)等娱乐资讯服务为主要业务的日本企业,其名称来自英文“Original Confidence”(绝对的信赖)的缩写,也因此该
  • 湖州市湖州市(吴语湖州音:Ghẽw Cieu),简称湖,古称乌程、吴兴,是中华人民共和国浙江省下辖的地级市,位于浙江省北部。市境东邻嘉兴市,南接杭州市,西界安徽省宣城市,北临太湖与江苏省无锡市、
  • 牟中原牟中原(1949年-),台湾化学研究者、教育工作者,中央研究院院士,现任国立台湾大学化学系教授、教育部国立教育研究院筹备处《自然与生活科技领域部编本教科书》研发编辑委员会主任委
  • 雷德河红河可以指:
  • 人口死亡率死亡率是用来衡量一部分人口中,一定规模的人口大小、每单位时间的死亡数目(整体或归因于指定因素)。死亡率通常以每年每一千人为单位来表示;因此在死亡率为9.5的10万人口中,表示
  • 新潍高速公路新河-潍坊高速公路,简称新潍高速,高速公路网编号为S21,是青岛平度市的一条连接线高速公路。该公路全长26km,起于平度市郭家埠立交桥、止于明村西立交桥,连接了荣乌高速公路和荣潍
  • 玛利亚·金布塔斯玛利亚·金布塔斯 (立陶宛语:Marija Gimbutienė,1921年1月23日 - 1994年2月2日)为美国籍的立陶宛考古学家,以研究古欧洲新石器时代和青铜时代文化的学术成就而闻名于世,而她的坟