Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (32): 51-52.DOI: 10.3778/j.issn.1002-8331.2009.32.016

• 研究、探讨 • Previous Articles     Next Articles

Approximate algorithm for traveling salesman problem based on graph theory

XU Jin-xing,WU Su-ping   

  1. College of Mathematics and Computer,Ningxia University,Yinchuan 750021,China
  • Received:2008-07-29 Revised:2008-10-21 Online:2009-11-11 Published:2009-11-11
  • Contact: XU Jin-xing

旅行售货员问题的图论近似算法

许金星,吴素萍   

  1. 宁夏大学 数学与计算机学院,银川 750021
  • 通讯作者: 许金星

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

摘要: 讨论了旅行售货员问题和图论中的哈密顿回路之间的关系,在此基础上结合图论中关于完全图最短路径的近似算法得到旅行售货员问题的一种近似算法。通过分析及实例验证了所提出的算法的可行性及有效性。

关键词: 图论, 哈密顿回路, 旅行售货员问题, 近似算法

CLC Number: