| 基于状态压缩的最长公共上升子序列快速算法 |
| |
| 引用本文： | 郭冬梅.基于状态压缩的最长公共上升子序列快速算法[J].计算机技术与发展,2014(5):40-43. |
| |
| 作者姓名： | 郭冬梅 |
| |
| 作者单位： | 安徽理工大学计算机科学与工程学院,安徽淮南232001 |
| |
| 基金项目： | 基金项目：安徽省高等学校省级优秀青年人才基金项目（2011SQRL040）;安徽理工大学青年教师科学研究基金（2012QNY31） |
| |
| 摘 要： | 探讨了最长公共上升子序列（LCIS）问题，在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题，分别使用最长公共子序列（LCS）和最长上升子序列（LIS）相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计，并对后两种算法进行了实现。设计的状态压缩的动态规划算法，实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度，最终提出了时间复杂度为O（mn）、空间复杂度为O（m）或O（n）的基于状态压缩的快速LCIS算法。
|
| 关 键 词： | 最长公共上升子序列 最长公共子序列 最长上升子序列 动态规划 状态压缩 |
A Longest Common Increasing Subsequence Algorithm Based on State Compression |
| |
| GUO Dong-mei.A Longest Common Increasing Subsequence Algorithm Based on State Compression[J].Computer Technology and Development,2014(5):40-43. |
| |
| Authors: | GUO Dong-mei |
| |
| Affiliation: | GUO Dong-mei ( College of Computer Science and Engineering, Anhui University of Science and Technology, Huainan 232001, China) |
| |
| Abstract: | Discussed the problem of a Longest Common Increasing Subsequence （ LCIS） ,put forword a fast dynamic algorithm for LCIS. For the LCIS problem,used respectively the algorithm of a Longest Common Subsequence （ LCS） combined a Longest Increasing Subse-quence （LIS） algorithm,dynamic programming algorithm,improved dynamic programming algorithm through state to design,and per-formed the second and the third algorithm. The designed state compressed dynamic programming algorithm realized a fast solution for LCIS. According to analyze the time and space complexity of the three algorithms,presented a fast algorithm for delivering a longest com-mon increasing subsequence in O（ mn） time and O（ m） or O（ n） space finally. |
| |
| Keywords: | LCIS LCS LIS dynamic programming state compression |
| 本文献已被 维普 等数据库收录！ |
