文献类型：期刊文章

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

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

出　　处：《计算机工程与设计》

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

年　　份：2007

卷　　号：28

期　　号：8

起止页码：1757-1758

语　　种：中文

收录情况：AJ、BDHX、BDHX2004、CSA、CSA-PROQEUST、CSCD、CSCD_E2011_2012、IC、INSPEC、JST、RCCSE、ZGKJHX、核心刊

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

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

分 类 号：TP301.6]