TSP的DNA算法

由于Adleman和Lipton的开创性工作,最近DNA计算引起了人们的极大兴趣,他们提出的分子算法解决了图形的表示方法,但是没有给出如何处理图中节点的弧线的信息。本文的目的是通过提出在图中城市间的距离用简单的弧线代表,延伸了Adleman和Lipton提出的基本的分子算法。并提出只有当算法步骤由当前的需要人工干预被可执行的可在试管中操作的DNA链代替,解决计算难题的真正可行DNA计算可以实现。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。

DNA algorithm of TSP

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.