基于格代数的最长公共子序列近似求解

摘要：

多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等.求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题.一些近似算法虽然时间复杂度较低,但只能求出单解,对于有多解的序列集合,求得的结果信息量损失较大.因此提出一个新的近似算法来解决最长公共子序列问题.算法引入了代数结构“格”,通过动态规划求解出两条序列的公共格,并递归求解当前格与当前序列的公共格.公共格中的路径保存了多条公共子序列使得最终求解出的最长公共子序列为多个.对算法的相关定理给出了理论证明,并通过实验验证了算法的正确性.

关键词：最长公共子序列、格、近似算法、贪心算法

所属期刊栏目：44

分类号：TP391.4(计算技术、计算机技术)

在线出版日期：2017-04-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：270-274