基于最长公共子序列的随机路径选择算法设计  

Random path selection algorithm design based on longest common subsequence

作　　者：王防修[1] 周康[1] 

机构地区：[1]武汉轻工大学数学与计算机学院,湖北武汉430023

出　　处：《计算机工程与设计》2014年第6期2170-2173,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(61179032)

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

关 键 词：最长公共子序列 最优子结构 动态规划 随机路径选择 最优解 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]