Heuristics trade the guarantee of a shortest tour for speed. The nearest neighbor algorithm
is a greedy algorithm that repeatedly visits
the closest unvisited city and finally returns to its starting city. It constructs
a tour in
distance comparisons, but can return a tour longer than the optimum. For symmetric
distances satisfying the triangle inequality,
its worst-case tour-length ratio grows logarithmically with (Rosenkrantz et al. 1977). Trying different starting
cities can improve the result without certifying that it is optimal. Other heuristics,
such as the ant colony algorithm, search for
good tours rather than guaranteeing the shortest one.
The traveling salesman problem is mentioned by the character Larry Fleinhardt in the Season 2 episode "Rampage"
(2006) of the television crime drama NUMB3RS.
Applegate, D.; Bixby, R.; Chvatal, V.; and Cook, W. "Finding Cuts in the TSP (a Preliminary Report)." Technical Report 95-05, DIMACS. Piscataway,
NJ: Rutgers University, 1995.Applegate, D.; Bixby, R.; Chvatal, V.;
and Cook, W. "Solving Traveling Salesman Problems." http://www.tsp.gatech.edu/.Hoffman,
P. The
Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical
Truth. New York: Hyperion, pp. 168-169, 1998.Kruskal, J. B.
"On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."
Proc. Amer. Math. Soc.7, 48-50, 1956.Lawler, E.; Lenstra,
J.; Rinnooy Kan, A.; and Shmoys, D. The
Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.
New York: Wiley, 1985.Lin, S. "Computer Solutions of the Traveling
Salesman Problem." Bell System Tech. J.44, 2245-2269, 1965.Platzman,
L. K. and Bartholdi, J. J. "Spacefilling Curves and the Planar Travelling
Salesman Problem." J. Assoc. Comput. Mach.46, 719-737, 1989.Reinelt,
G. "TSPLIB--A Traveling Salesman Problem Library." ORSA J. Comput.3,
376-384, 1991.Rosenkrantz, D. J.; Stearns, R. E.; and Lewis,
P. M., II. "An Analysis of Several Heuristics for the Traveling Salesman
Problem." SIAM J. Comput.6, 563-581, 1977. https://doi.org/10.1137/0206041.Skiena,
S. "Traveling Salesman Tours." §5.3.5 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 199-202, 1990.Skiena, S. S. "Traveling
Salesman Problem." §8.5.4 in The
Algorithm Design Manual. New York: Springer-Verlag, pp. 319-322, 1997.Steinhaus,
H. Mathematical
Snapshots, 3rd ed. New York: Dover, pp. 120-121, 1999.
cities. The problem is NP-hard,
and no exact algorithm running in polynomial
time is known. The Held-Karp algorithm
solves finite instances exactly using dynamic
programming in 
time.
distance comparisons, but can return a tour longer than the optimum. For symmetric
distances satisfying the triangle inequality,
its worst-case tour-length ratio grows logarithmically with 
(Rosenkrantz et al. 1977). Trying different starting
cities can improve the result without certifying that it is optimal. Other heuristics,
such as the ant colony algorithm, search for
good tours rather than guaranteeing the shortest one.
if it returns a list with first element equal to the vertex
count of 
.
