摘要
旅行商问题,简称为TSP问题,是困难的NP完全问题,在工程实践中具有广泛的应用。利用常规的计算方法求解这个问题,计算所需的时间是随着问题规模的增大以指数形式增加的,因而无法有效的解决此类问题。DNA计算是一种新兴的计算方式,粘贴系统模型是其中基于粘贴运算的一种DNA计算的抽象模型。通过将旅行商问题转化为求赋权图中权值最小的Hamilton圈,利用粘贴系统模型的巨大并行性,可以有效的求解旅行商问题。
The traveling salesman problem (TSP) is a hard NP complete problem, which has wide applications in the engineering. The similar questions aren't solved effectively by using current calculation method, because the time needed for computation is increasing exponentially with the problems scale. DNA computing is a new calculation method, and the sticker system is an abstract DNA computing model that based on sticking operations. The traveling salesman problems are availably solved by being transformed to solve the Hamilton circle of the minimal weight value in the evaluate graph, and using the massive parallelism of sticker system.
出处
《系统仿真学报》
EI
CAS
CSCD
北大核心
2005年第6期1299-1302,1306,共5页
Journal of System Simulation
基金
国家自然科学基金(30370356
60274026)
华中科技大学博士后基金。
