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

作     者：王防修 周康 WANG Fang-xiu;ZHOU Kang

作者机构：武汉轻工大学数学与计算机学院湖北武汉430023 

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

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2014年第35卷第6期

页      码：2170-2173页

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

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

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1000-7024.2014.06.055

馆 藏 号：203139642...