| 关于旅行推销员问题的一个算法 |
| |
| 引用本文： | 段禅伦,斯勤夫. 关于旅行推销员问题的一个算法[J]. 内蒙古大学学报(自然科学版), 2001, 32(6): 695-696 |
| |
| 作者姓名： | 段禅伦 斯勤夫 |
| |
| 作者单位： | 内蒙古大学计算机学院;内蒙古财经学院计算机信息管理系 |
| |
| 基金项目： | 内蒙古自然科学基金资助项目 (2 0 0 1 0 90 1 ) |
| |
| 摘 要： | 通过圈上结点下标自足方法,给出了一个关于旅行推销员问题的算法,尽管该算法实质上无法改变问题的NP－完全性的难度,但较分支定界法的执行速度快,比一些近拟算法要好。
|
| 关 键 词： | 赋权完全图 Hamilton圈 圈下标是自足的 |
| 文章编号： | 1000-1638(2001)06-0695-02 |
| 修稿时间： | 2001-08-30 |
An Algorithm on Traveling Salesman Problem |
| |
| DUAN Chan lun ,SI Qin fu. An Algorithm on Traveling Salesman Problem[J]. Acta Scientiarum Naturalium Universitatis Neimongol, 2001, 32(6): 695-696 |
| |
| Authors: | DUAN Chan lun SI Qin fu |
| |
| Affiliation: | DUAN Chan lun 1,SI Qin fu 2 |
| |
| Abstract: | We present an algorithm about Traveling Salesman problem through the method of Self saturated Subscript in Cycle. Even if we cannot improve the time complexity of this problem in essence, in which the time complexity is a NP hard, however, this algorithm is faster than the method of Branch Delimitation and other approximation algorithms in speed. |
| |
| Keywords: | weighted complete graph Hamilton cycle self saturated subscript on cycle |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
