旅行商问题的DNA算法

• 作者: 王兆才 肖冬梅 贺林
• 来源期刊: 计算机工程与应用
• 学科: 生物学
• 关键词: 旅行商问题 Adleman-Lipton模型 DNA计算
• 年，卷（期）: 2006,（30）
• 所属期刊栏目: 学术探讨
• 页码范围: 81-83,94
• 页数: 4页
• 分类号: Q811.211
• 字数: 5651字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.30.023

摘要

旅行商问题是求仅一次遍访指定城市并返回出发城市的最短旅行路线的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间才能得到解决,该文基于分子生物技术并利用Adleman-Lipton模型给出旅行商问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题.具体地对n个城市的旅行商问题,首先将它视为一个具有顶点和边的图,并将顶点、边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到旅行商问题的解,其过程的复杂度为O(n).该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理小的范围内寻找旅行商问题的解,较大地简化了问题的复杂度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	肖冬梅	上海交通大学理学院数学系	5	11	2.0	3.0