计算最短公共超串的贪婪算法  

Greedy algorithm of computing shortest common superstring

作　　者：申时凯[1] 吴绍兵[1] 申浩如[1] 王付艳[1] 管彦庆[1] 

机构地区：[1]昆明学院计算机系,云南昆明650031

出　　处：《计算机工程与设计》2007年第8期1757-1758,1761,共3页Computer Engineering and Design

基　　金：云南省教育厅自然科学基金项目(02ZY093;6Y0070D);昆明学院校管科研基金项目(2006Z002)

摘　　要：最短公共超串问题就是对给定的子串集合找到包含每个子串的可能的串。这个问题是一个NP-完全问题。目前已有一些方法对此进行了研究。通过对各子串的分析和研究,提出了一种近似于贪婪算法的求最短公共超串问题算法,该算法可应用于解决DNA片段组装和数据压缩问题。最后给出了几个实例。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.

关 键 词：最短公共超串 覆盖 算法 贪婪算法 哈密尔顿路 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]