TSP的DNA算法  

DNA algorithm of TSP

作　　者：彭镇静[1] 王建中[1] 赵永耀[1] 

机构地区：[1]中北大学,太原030051

出　　处：《电子测试》2012年第2期20-22,38,共4页Electronic Test

摘　　要：由于Adleman和Lipton的开创性工作,最近DNA计算引起了人们的极大兴趣,他们提出的分子算法解决了图形的表示方法,但是没有给出如何处理图中节点的弧线的信息。本文的目的是通过提出在图中城市间的距离用简单的弧线代表,延伸了Adleman和Lipton提出的基本的分子算法。并提出只有当算法步骤由当前的需要人工干预被可执行的可在试管中操作的DNA链代替,解决计算难题的真正可行DNA计算可以实现。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。DNA computing has recently generated much interest as a result of pioneering work by Adleman and Lipton.Their DNA algorithms worked on graph representations but no indication was provided as to how information on the arcs between nodes on a graph could be handled.The aim of this paper is to extend the basic DNA algorithmic techniques of Adleman and Lipton by proposing a method for representing simple arc information-in this case,distances between cities in a simple map.It is also proposed that the real potential of DNA computing for solving computationally hard problems will only be realized when algorithmic steps which currently require manual intervention are replaced by executable DNA which operates on DNA strands in test-tubes.The innovation of the algorithm is the choice of the city string and weight string＇s length,which can reduce the solution of the problem involving in an fixed interval and simplify the computation.

关 键 词：旅行商问题 DNA算法 生化实验 

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