期刊论文

中文

计算机工程与设计

1000-7024

2014

35

6

2170-2173

10.16208/j.issn1000-7024.2014.06.046

国家自然科学基金项目

本校为第一机构

针对传统算法只能求出一个最长公共子序列而无法求出多个最长公共子序列,设计了一种可求多个最长公共子序列的算法。简述了最长公共子序列的算法原理,描述了求最长公共子序列长度的动态规划算法,在此基础上求出一个最长公共子序列,通过对算法改进得到可求多个最长公共子序列的随机路径选择算法。该算法具有计算速度快、占用内存小、计算机易于实现等优点。其核心是寻优路径的选择,提出了寻找最优解的路径选择问题,讨论并给出了搜索多个可行解的快速算法,该算法充分利用了动态规划算法计算过程中提供的寻优方向信息得到最优路径的随机选择算法,与传统算法相比可求多个最长公共子序列。

In view of the traditional algorithm could only calculate one longest common subsequence and could not find out more longest common subsequences,an algorithm was proposed to seek a plurality of the longest common subsequences.It first introduced the principle of the algorithm.Then it described the dynamic programming algorithm to culate the length of the longest common subsequence,and on the basis of this,a longest common subsequence was found out.At last,it get a plurality of the longest common subsequence by the improved random path selection algorithm.The improved algorithm hae the advantag...