Improvements of the Held-Karp algorithm for the symmetric traveling-salesman problem.
作者： Keld Helbig Hansen , Jakob Krarup
DOI: 10.1007/BF01585505
关键词:
摘要: A highly efficient algorithm (HK) devised by Held and Karp for solving the symmetric traveling-salesman problem was presented at 7th Mathematical Programming Symposium in 1970 published 1971. Its outstanding performance is due to a clever exploitation of relationship between minimum spanning trees. However, various improvements their method have led version (IHK) which tends be some 25 times faster than original one. Experiments with data selected random, ranging size up 80 cities, show that computing time IHK roughly doubled as number cities increased 10.
springer.com
sci-hub.se 参考文章(7)
Joseph B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem Proceedings of the American Mathematical Society. ,vol. 7, pp. 48- 50 ,(1956) , 10.1090/S0002-9939-1956-0078686-7
Michael Held, Richard M. Karp, The Traveling-Salesman Problem and Minimum Spanning Trees Operations Research. ,vol. 18, pp. 1138- 1162 ,(1970) , 10.1287/OPRE.18.6.1138
R. C. Prim, Shortest Connection Networks And Some Generalizations Bell System Technical Journal. ,vol. 36, pp. 1389- 1401 ,(1957) , 10.1002/J.1538-7305.1957.TB01515.X
Michael Held, Richard M. Karp, The traveling-salesman problem and minimum spanning trees: Part II Mathematical Programming. ,vol. 1, pp. 6- 25 ,(1971) , 10.1007/BF01584070
M. H. van Emden, Algorithms 402: Increasing the efficiency of quicksort Communications of The ACM. ,vol. 13, pp. 693- 694 ,(1970) , 10.1145/362790.362803
M. H. van Emden, Increasing the efficiency of quicksort Communications of the ACM. ,vol. 13, pp. 563- 567 ,(1970) , 10.1145/362736.362753
E. W. Dijkstra, A note on two problems in connexion with graphs Numerische Mathematik. ,vol. 1, pp. 269- 271 ,(1959) , 10.1007/BF01386390