Solving traveling salesman problem in the Adleman-Lipton model
详细信息 查看全文
- 作者：Zhaocai Wang ; Yiming Zhang ; Weihua Zhou ; Haifeng Liu
- 关键词：DNA computing ; The traveling salesman problem ; Adleman&ndash ; Lipton model ; NP-complete problem
- 刊名：Applied Mathematics and Computation
- 出版年：2012
- 出版时间：1 November, 2012
- 年：2012
- 卷：219
- 期：4
- 页码：2267-2270
- 全文大小：183 K
文摘
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 steps for the traveling salesman of an edge-weighted graph with n vertices.