计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (32): 51-52.DOI: 10.3778/j.issn.1002-8331.2009.32.016
• 研究、探讨 • 上一篇 下一篇
许金星，吴素萍
收稿日期:
修回日期:
出版日期:
发布日期:
通讯作者:
XU Jin-xing，WU Su-ping
Received:
Revised:
Online:
Published:
Contact:
摘要： 讨论了旅行售货员问题和图论中的哈密顿回路之间的关系，在此基础上结合图论中关于完全图最短路径的近似算法得到旅行售货员问题的一种近似算法。通过分析及实例验证了所提出的算法的可行性及有效性。
关键词: 图论, 哈密顿回路, 旅行售货员问题, 近似算法
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.
Key words: graph theory, Hamilton circuit, Traveling Salesman Problem（TSP）, approximate algorithm
中图分类号:
TP311
许金星，吴素萍. 旅行售货员问题的图论近似算法[J]. 计算机工程与应用, 2009, 45(32): 51-52.
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.
0 / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://cea.ceaj.org/CN/10.3778/j.issn.1002-8331.2009.32.016
http://cea.ceaj.org/CN/Y2009/V45/I32/51
