基于粘贴系统求解TSP问题

摘要：

旅行商问题,简称为TSP问题,是困难的NP完全问题,在工程实践中具有广泛的应用.利用常规的计算方法求解这个问题,计算所需的时间是随着问题规模的增大以指数形式增加的,因而无法有效的解决此类问题.DNA计算是一种新兴的计算方式,粘贴系统模型是其中基于粘贴运算的一种DNA计算的抽象模型.通过将旅行商问题转化为求赋权图中权值最小的Hamilton圈,利用粘贴系统模型的巨大并行性,可以有效的求解旅行商问题.

关键词： 粘贴系统 NP完全问题 TSP问题 DNA计算

作者: 董亚非 谭刚军 张社民

作者单位: 华中科技大学控制科学与工程系(武汉);陕西省气象科学研究所(西安) 华中科技大学控制科学与工程系(武汉)

会议类型: 国内会议

会议名称: 全球化制造高级论坛暨21世纪仿真技术研讨会

会议地点: 贵阳

会议语种:中文

页码: 299-303

在线出版日期: 2004-10-20（万方平台首次上网日期，不代表论文的发表时间）