Abstract:

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.

Key words: TSP problem;DNA computing;closed circle model;DNA algorithm