基于粘贴系统求解TSP问题

摘要：

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

关键词： 算法 粘贴系统 旅行商问题 计算方式 抽象模型 赋权图

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

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

会议类型: 国内会议

会议名称: 2006中国科协年会

会议地点: 北京

会议语种:中文

页码: 441-447

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