| 货郎问题求解算法分析 |
| |
| 引用本文： | 潘玉奇,王潍,康健,王永燕.货郎问题求解算法分析[J].济南大学学报(自然科学版),2002,16(4):336-339,358. |
| |
| 作者姓名： | 潘玉奇 王潍 康健 王永燕 |
| |
| 作者单位： | 1. 济南大学信息科学与工程学院
2. 机械工程学院,山东,济南,250022 |
| |
| 摘 要： | 介绍了求解货郎问题的4个算法：贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解，并对各个算法的性能进行了分析比较。贪心算法的运行速度较快，但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题，其近似性能比（即精确度）分别为：RMST（I）＜2，RMM（I）＜3／2。回溯搜索算法可以求出货郎问题的最优解，随着城市数目的增加，其搜索效率会下降。
|
| 关 键 词： | 算法分析 货郎问题 最小生成树 最小对集 贪心算法 近似算法 回溯搜索算法 |
| 文章编号： | 1671-3559(2002)04-0336-04 |
Algorithmic Analysis of Travelling Salesman Problem Solving |
| |
| Pan Yuqi ,Wang Wei ,Kang Jian ,Wang Yongyan.Algorithmic Analysis of Travelling Salesman Problem Solving[J].Journal of Jinan University(Science & Technology),2002,16(4):336-339,358. |
| |
| Authors: | Pan Yuqi Wang Wei Kang Jian Wang Yongyan |
| |
| Institution: | Pan Yuqi 1,Wang Wei 2,Kang Jian 1,Wang Yongyan 1 |
| |
| 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. |
| |
| Keywords: | traveling salesman problem minimum spanning tree minimum matching greedy algorithm approximation algorithm backtracking search algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
