| 旅行售货员问题的图论近似算法 |
| |
| 引用本文： | 许金星,吴素萍. 旅行售货员问题的图论近似算法[J]. 计算机工程与应用, 2009, 45(32): 51-52. DOI: 10.3778/j.issn.1002-8331.2009.32.016 |
| |
| 作者姓名： | 许金星 吴素萍 |
| |
| 作者单位： | 宁夏大学,数学与计算机学院,银川,750021;宁夏大学,数学与计算机学院,银川,750021 |
| |
| 摘 要： | 讨论了旅行售货员问题和图论中的哈密顿回路之间的关系，在此基础上结合图论中关于完全图最短路径的近似算法得到旅行售货员问题的一种近似算法。通过分析及实例验证了所提出的算法的可行性及有效性。
|
| 关 键 词： | 图论 哈密顿回路 旅行售货员问题 近似算法 |
| 收稿时间： | 2008-07-29 |
| 修稿时间： | 2008-10-21 |
Approximate algorithm for traveling salesman problem based on graph theory |
| |
| XU Jin-xing,WU Su-ping. Approximate algorithm for traveling salesman problem based on graph theory[J]. Computer Engineering and Applications, 2009, 45(32): 51-52. DOI: 10.3778/j.issn.1002-8331.2009.32.016 |
| |
| Authors: | XU Jin-xing WU Su-ping |
| |
| Affiliation: | College of Mathematics and Computer，Ningxia University，Yinchuan 750021，China |
| |
| Abstract: | The relationship between the Hamilton circuit and the Traveling Salesman Problem is discussed.On the basis of this and the approximate algorithm of shortest path of the complete graph theory,a new approximate algorithm of TSP is proposed. Analyses and examples show that the approximate algorithm is effective. |
| |
| Keywords: | graph theory Hamilton circuit Traveling Salesman Problem(TSP) approximate algorithm |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
