| 基于粘贴系统求解TSP问题 |
| |
| 引用本文： | 董亚非,谭刚军,张社民.基于粘贴系统求解TSP问题[J].系统仿真学报,2005,17(6):1299-1302,1306. |
| |
| 作者姓名： | 董亚非 谭刚军 张社民 |
| |
| 作者单位： | 1. 华中科技大学控制科学与工程系,武汉,430074;陕西省气象科学研究所,西安,710015
2. 华中科技大学控制科学与工程系,武汉,430074 |
| |
| 基金项目： | 国家自然科学基金(30370356,60274026)，华中科技大学博士后基金。 |
| |
| 摘 要： | 旅行商问题，简称为TSP问题，是困难的NP完全问题，在工程实践中具有广泛的应用。利用常规的计算方法求解这个问题，计算所需的时间是随着问题规模的增大以指数形式增加的，因而无法有效的解决此类问题。DNA计算是一种新兴的计算方式，粘贴系统模型是其中基于粘贴运算的一种DNA计算的抽象模型。通过将旅行商问题转化为求赋权图中权值最小的Hamilton圈，利用粘贴系统模型的巨大并行性，可以有效的求解旅行商问题。
|
| 关 键 词： | TSP问题 粘贴 求解 Hamilton圈 旅行商问题 DNA计算 NP完全问题 系统模型 工程实践 计算方法 指数形式 计算方式 抽象模型 问题转化 赋权图 并行性 时间 运算 |
| 文章编号： | 1004-731X(2005)06-1299-04 |
Algorithm of TSP Based on Sticker Systems of DNA computing |
| |
| DONG Ya-fei,TAN Gang-jun,ZHANG She-min.Algorithm of TSP Based on Sticker Systems of DNA computing[J].Journal of System Simulation,2005,17(6):1299-1302,1306. |
| |
| Authors: | DONG Ya-fei TAN Gang-jun ZHANG She-min |
| |
| Institution: | DONG Ya-fei1,2,TAN Gang-jun1,ZHANG She-min1 |
| |
| Abstract: | |
| |
| Keywords: | algorithm sticker system NP-complete problem TSP DNA computing |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
