摘要
针对传统算法只能求出一个最长公共子序列而无法求出多个最长公共子序列,设计了一种可求多个最长公共子序列的算法。简述了最长公共子序列的算法原理,描述了求最长公共子序列长度的动态规划算法,在此基础上求出一个最长公共子序列,通过对算法改进得到可求多个最长公共子序列的随机路径选择算法。该算法具有计算速度快、占用内存小、计算机易于实现等优点。其核心是寻优路径的选择,提出了寻找最优解的路径选择问题,讨论并给出了搜索多个可行解的快速算法,该算法充分利用了动态规划算法计算过程中提供的寻优方向信息得到最优路径的随机选择算法,与传统算法相比可求多个最长公共子序列。
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 advantages of faster calculation speed,small memory space,and easy realized by computers.The optimal path selection was the core of the improved algorithm.It proposed the optimal solution of routing finding problem,discussed and gave a solution algorithm for fast searching.The algorithm made full use of the dynamic programming algorithm to provide direction information in the optimization for obtaining the optimal path.The algorithm had higher efficiency compared with the traditional algorithm in finding the feasible solutions.
出处
《计算机工程与设计》
CSCD
北大核心
2014年第6期2170-2173,共4页
Computer Engineering and Design
基金
国家自然科学基金项目(61179032)
关键词
最长公共子序列
最优子结构
动态规划
随机路径选择
最优解
the longest common subsequence
optimal substructure
dynamic programming
random path selection
optimal solution
