Das Traveling-Salesman-Problem
作者： Bernhard Korte , Jens Vygen
DOI: 10.1007/978-3-642-25401-7_21
关键词: Humanities 、 Travelling salesman problem 、 Mathematics
摘要: In Kapitel 15 haben wir das TRAVELING-SALESMAN-PROBLEM (TSP) definiert und bewiesen, dass es NP-schwer ist (Satz 15.43). Das TSP wahrscheinlich am besten untersuchte NP-schwere kombinatorische Optimierungsproblem gibt viele dafur entwickelte verwendete Verfahren. Als erstes werden in den Abschnitten 21.1 21.2 Approximationsalgorithmen betrachten. der Praxis sich fur grose Instanzen so genannte lokale Suchalgorithmen (siehe Abschnitt 21.3) bewahrt, obwohl sie keine endliche Approximationsgute haben.
springer.com
sci-hub.st 参考文章(72)
Eberhard Triesch, Walter Nolles, Jens Vygen, Die Einsatzplanung von Zementmischern und ein Traveling Salesman Problem Springer, Berlin, Heidelberg. pp. 15- 22 ,(1994) , 10.1007/978-3-642-78998-4_3
David Shmoys, Eugene L. Lawler, Alexander H. G. Rinnooy Kan, Jan Karel Lenstra, The traveling salesman problem ,(1985)
Jan Karel Lenstra, David Shmoys, The Traveling Salesman Problem: A Computational Study ,(2007)
Emile Aarts, Wil Michiels, Jan Korst, Theoretical aspects of local search ,(2006)
M Jünger G Reinelt G Rinaldi, G Jünger, G Reinelt, The traveling salesman problem Research Report Series of IASI-CNR, Rome, Italy (ISSN: 1128-3378). ,vol. 375, ,(1994)
Matthias Englert, Heiko Röglin, Berthold Vöcking, Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP Algorithmica. ,vol. 68, pp. 190- 264 ,(2014) , 10.1007/S00453-013-9801-4
The traveling salesman problem and its variations Kluwer Academic. ,(2007) , 10.1007/B101971
Michael Jünger, Gerhard Reinelt, Giovanni Rinaldi, Chapter 4 The traveling salesman problem Handbooks in Operations Research and Management Science. ,vol. 7, pp. 225- 330 ,(1995) , 10.1016/S0927-0507(05)80121-5
David Applegate, Robert Bixby, Vašek Chvátal, William Cook, Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems Mathematical Programming. ,vol. 97, pp. 91- 153 ,(2003) , 10.1007/S10107-003-0440-4
Laurence A. Wolsey, Heuristic analysis, linear programming and branch and bound Mathematical Programming Studies. ,vol. 13, pp. 121- 134 ,(1980) , 10.1007/BFB0120913