旅行商问题的闭环DNA算法  

Closed circle DNA algorithm of traveling salesman problem

作　　者：徐京雷 赵洪超[1] 刘希玉[1] 

机构地区：[1]山东师范大学管理科学与工程学院,山东济南250014

出　　处：《计算机工程与科学》2014年第1期111-114,共4页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(61170038)

摘　　要：旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题。Traveling Salesman Problem （TSP） is a hard NP-complete problem, which has wide appli- cations 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.

关 键 词：TSP问题 DNA计算 闭环模型 DNA算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]