旅行商问题的闭环DNA算法

旅行商问题TSP是NP完全问题，在工程实践中有着广泛的应用，利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式，与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA 计算模型及其改进；随后提出了一种基于改进的闭环模型求解TSP问题的算法，并对算法的实验过程进行了详细的描述；最后运用该算法解决了一个小规模的TSP问题算例，结果表明，该算法能在较低的时间复杂度内有效地解决TSP问题。

Closed circle DNA algorithm of traveling salesman problem

Traveling Salesman Problem (TSP) is a hard NP complete problem, which has wide applications in the engineering. It is very difficult to solve TSP problem in polynomial time by using regular algorithms. DNA computing is a new computing pattern; its inherent huge parallel computing power makes it show a huge advantage in solving many NP problems. We try to solve the TSP problem by the improved closed circle model. Firstly, the closed circle model and its improved version are introduced. Secondly, a closed circle DNA algorithm based on the improved model is proposed, which can solve the TSP problem. And the procedure is described in detail. Finally, a small case is solved by the algorithm. Experimental results show that the proposed algorithm can solve the TSP problem effectively in a lower time complexity.