| 计算最短公共超串的贪婪算法 |
| |
| 引用本文： | 申时凯,吴绍兵,申浩如,王付艳,管彦庆. 计算最短公共超串的贪婪算法[J]. 计算机工程与设计, 2007, 28(8): 1757-1758,1761 |
| |
| 作者姓名： | 申时凯 吴绍兵 申浩如 王付艳 管彦庆 |
| |
| 作者单位： | 昆明学院,计算机系,云南,昆明,650031;昆明学院,计算机系,云南,昆明,650031;昆明学院,计算机系,云南,昆明,650031;昆明学院,计算机系,云南,昆明,650031;昆明学院,计算机系,云南,昆明,650031 |
| |
| 基金项目： | 云南省教育厅资助项目 , 昆明学院校管科研基金 |
| |
| 摘 要： | 最短公共超串问题就是对给定的子串集合找到包含每个子串的可能的串.这个问题是一个NP-完全问题.目前已有一些方法对此进行了研究.通过对各子串的分析和研究,提出了一种近似于贪婪算法的求最短公共超串问题算法,该算法可应用于解决DNA片段组装和数据压缩问题.最后给出了几个实例.
|
| 关 键 词： | 最短公共超串 覆盖 算法 贪婪算法 哈密尔顿路 |
| 文章编号： | 1000-7024（2007）08-1757-02 |
| 修稿时间： | 2006-03-28 |
Greedy algorithm of computing shortest common superstring |
| |
| SHEN Shi-kai,WU Shao-bing,SHEN Hao-ru,WANG Fu-yan,GUAN Yan-qing. Greedy algorithm of computing shortest common superstring[J]. Computer Engineering and Design, 2007, 28(8): 1757-1758,1761 |
| |
| Authors: | SHEN Shi-kai WU Shao-bing SHEN Hao-ru WANG Fu-yan GUAN Yan-qing |
| |
| Affiliation: | Department of Computer Science, Kunming College, Kunming 650031, China |
| |
| Abstract: | The shortest common superstring problem(SCS) is to find the shortest possible string that contains every string in a given set as substrings.As the problem is NP-complete.This days,there are many methods to deal with it.An approximation algorithm based on greedy algorithm and Hamiltonian path is proposed to deal with the shortest common superstring problem by analyzing the every substring.One obvious application for the problem is sequenced DNA fragments.Another is data compression.Finally,some examples are given. |
| |
| Keywords: | shortest common superstring overlap algorithm greedy algorithm hamiltonian path |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
