旅行商问题的DNA算法

旅行商问题的DNA算法

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

作 者： 王兆才 肖冬梅 贺林 WANG Zhao-cai XIAO Dong-mei HE Lin   作者单位：   刊 名： 计算机工程与应用  ISTIC PKU 英文刊名： COMPUTER ENGINEERING AND APPLICATIONS  年，卷(期)： 2006 42(30)  分类号： Q811.211  关键词： 旅行商问题   Adleman-Lipton模型   DNA计算  

【旅行商问题的DNA算法】相关文章：

旅行商问题的一个新算法:堵子回路法04-27

有时间约束旅行商问题的启发式遗传算法04-29

DNA电脑04-26

扩展旅行商问题模型研究04-26

DNA聚合酶与DNA复制的忠实性04-26

硫化铋纳米粒子标记DNA及DNA特定序列的检测04-29

dna粗提取与鉴定06-27

枸杞线粒体DNA的提取04-26

数学算法04-28

IRA码最小和译码算法的改进算法04-28