structural:expansion, linguistic:voice_change
Exact algorithms

The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute-force search). The running time for this approach lies within a polynomial factor of O (n !) {\displaystyle O(n!)}, the factorial of the number of cities, so this solution becomes impractical even for only 20 cities.

One of the earliest applications of dynamic programming is the Held–Karp algorithm, which solves the problem in time O (n 2 2 n) {\displaystyle O(n^{2}2^{n})}. This bound has also been reached by Exclusion-Inclusion in an attempt preceding the dynamic programming approach.

Improving these time bounds seems to be difficult. For example, it has not been determined whether a classical exact algorithm for TSP that runs in time O (1.9999 n) {\displaystyle O(1.9999^{n})} exists. The currently best quantum exact algorithm for TSP due to Ambainis et al. runs in time O (1.728 n) {\displaystyle O(1.728^{n})}.

Other approaches include:

An exact solution for 15,112 German towns from TSPLIB was found in 2001 using the cutting-plane method proposed by George Dantzig, Ray Fulkerson, and Selmer M. Johnson in 1954, based on linear programming. The computations were performed on a network of 110 processors located at Rice University and Princeton University. The total computation time was equivalent to 22.6 years on a single 500 MHz Alpha processor. In May 2004, the travelling salesman problem of visiting all 24,978 towns in Sweden was solved: a tour of length approximately 72,500 kilometres was found, and it was proven that no shorter tour exists. In March 2005, the travelling salesman problem of visiting all 33,810 points in a circuit board was solved using Concorde TSP Solver: a tour of length 66,048,945 units was found, and it was proven that no shorter tour exists. The computation took approximately 15.7 CPU-years (Cook et al. 2006). In April 2006 an instance with 85,900 points was solved using Concorde TSP Solver, taking over 136 CPU-years; see Applegate et al. (2006).