货郎问题求解算法分析  

Algorithmic Analysis of Travelling Salesman Problem Solving

作　　者：潘玉奇[1] 王潍 康健[1] 王永燕[1] 

机构地区：[1]济南大学信息科学与工程学院 [2]机械工程学院,山东济南250022

出　　处：《济南大学学报（自然科学版）》2002年第4期336-339,358,共5页Journal of University of Jinan(Science and Technology)

摘　　要：介绍了求解货郎问题的 4个算法 :贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解 ,并对各个算法的性能进行了分析比较。贪心算法的运行速度较快 ,但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题 ,其近似性能比(即精确度 )分别为 :RMST(I) <2 ,RMM(I) <3 / 2。回溯搜索算法可以求出货郎问题的最优解 ,但随着城市数目的增加 。Four algorithms of traveling salesman problem(i.e. TSP) solving are introduced,including: greedy algorithm?MST approximation algorithm?MM approximation algorithm and backtracking search algorithm. We solve an instance of TSP with these different algorithms,and analyze different algorithmic performances.The running speed of greedy algorithm is fast,but in most cases greedy algorithm find a second-best solution,not an optimal solution.MST and MM approximationalgorithms are used to solve TSP which conform to trianglar inequality,their approximation performance ratios(i.e.precision) are listed as follows:R MST(I)<2,R MM(I)<3/2 . Backtracking search algorithm can find an optimal solution,but with the increase of the number of city, search efficiency will decline.

关 键 词：算法分析 货郎问题 最小生成树 最小对集 贪心算法 近似算法 回溯搜索算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]