| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 一种改进的最大团问题DNA计算机算法 |
| 作者 | 李肯立1),2) 周旭1) 邹舒婷1) |
| 作者单位 | 1)(湖南大学计算机与通信学院 长沙 410082) 2)(华中科技大学分子生物计算机研究所 武汉 430074) |
| 发表年份 | 2008 |
| 发表月份 | 12期(2173—2181) |
| 文章摘要 | 摘要 随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法.算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成.与已有文献同类算法的对比分析表明:文中算法在保持多项式操作时间的条件下,将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O(2n)减少至O(3n),同时文中算法还具有高效的空间利用率及容错能力的优点. 关键词 DNA超级计算;最大团问题;剪枝技术;NP完全问题 |