旅行商问题的DNA算法

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

DNA Algorithm for Solving the Traveling Salesman Problem

The traveling salesman problem is given by a set of some cities,and asks for a shortest tour of visiting all cities only once from one city and back to this city.It is a classical NP-complete problem in graph theory.It needs exponential time to solve the problem by the electronic computer.In this paper,the DNA algorithm for the traveling salesman problem is provided by the technology of the molecule biology and the Adleman-Lipton model.It is showed that the problem can be solved in the polynomial time.We use a graph with vertexes and edges to denote these cities and roads.The vertex,weight and direction of the graph are encoded by the DNA strings.Putting these DNA strings into the tube to produce,the solution of the traveling salesman problem can be obtained by a series of basic biology operations.The algorithm is highly parallel.For a traveling salesman problem with n cities,the complicacy of computation is O(n).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.