【摘要】 介绍了求解货郎问题的 4个算法 :贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解 ,并对各个算法的性能进行了分析比较。贪心算法的运行速度较快 ,但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题 ,其近似性能比(即精确度 )分别为 :RMST(I) <2 ,RMM(I) <3 / 2。回溯搜索算法可以求出货郎问题的最优解 ,但随着城市数目的增加 ,其搜索效率会下降更多还原

【Abstract】 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.更多还原