Solving traveling salesman problem in the Adleman–Lipton model

摘要

The traveling salesman problem is to find a minimum cost (weight) path for a given set of cities (vertices) and roads (edges). The path must start at a specified city and end there after going through all the other given cites only once. It is a classical NP-complete problem in graph theory. In this paper, we consider a DNA procedure for solving the traveling salesman problem in the Adleman–Lipton model. The procedure works in O(n) steps for the traveling salesman of an edge-weighted graph with n vertices.