作者：董亚非; 谭刚军; 张社民tsp问题粘贴求解hamilton圈旅行商问题dna计算np完全问题系统模型工程实践计算方法指数形式计算方式抽象模型问题转化赋权图并行性时间运算
摘要：旅行商问题,简称为TSP问题,是困难的NP完全问题,在工程实践中具有广泛的应用.利用常规的计算方法求解这个问题,计算所需的时间是随着问题规模的增大以指数形式增加的,因而无法有效的解决此类问题.DNA计算是一种新兴的计算方式,粘贴系统模型是其中基于粘贴运算的一种DNA计算的抽象模型.通过将旅行商问题转化为求赋权图中权值最小的Hamilton圈,利用粘贴系统模型的巨大并行性,可以有效的求解旅行商问题.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
