Editing Travelling salesman problem (section)

===Exact algorithms===

The most direct solution would be to try all [[permutation]]s (ordered combinations) and see which one is cheapest (using [[brute-force search]]). The running time for this approach lies within a polynomial factor of <math>O(n!)</math>, 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&ndash;Karp algorithm]], which solves the problem in time <math>O(n^2 2^n)</math>.<ref>{{harvp|Bellman|1960}}, {{harvp|Bellman|1962}}, {{harvp|Held|Karp|1962}}</ref> This bound has also been reached by Exclusion-Inclusion in an attempt preceding the dynamic programming approach.
[[File:Bruteforce.gif|framed|right|Solution to a symmetric TSP with 7 cities using brute force search. Note: Number of permutations: (7&minus;1)!/2 = 360]]

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 <math>O(1.9999^n)</math> exists.{{sfnp|Woeginger|2003}} The currently best quantum [[exact algorithm]] for TSP due to Ambainis et al. runs in time <math>O(1.728^n)</math>.<ref>{{cite book | chapter-url=https://epubs.siam.org/doi/10.1137/1.9781611975482.107 | doi=10.1137/1.9781611975482.107 | chapter=Quantum Speedups for Exponential-Time Dynamic Programming Algorithms | title=Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | year=2019 | last1=Ambainis | first1=Andris | last2=Balodis | first2=Kaspars | last3=Iraids | first3=Jānis | last4=Kokainis | first4=Martins | last5=Prūsis | first5=Krišjānis | last6=Vihrovs | first6=Jevgēnijs | pages=1783–1793 | isbn=978-1-61197-548-2 | s2cid=49743824 }}</ref>

Other approaches include:
* Various [[Branch and bound|branch-and-bound]] algorithms, which can be used to process TSPs containing thousands of cities.
[[File:Branchbound.gif|framed|right|Solution of a TSP with 7 cities using a simple Branch and bound algorithm. Note: The number of permutations is much less than Brute force search]]
* Progressive improvement algorithms, which use techniques reminiscent of [[linear programming]]. This works well for up to 200 cities.
* Implementations of [[Branch and bound|branch-and-bound]] and problem-specific cut generation ([[Branch and cut|branch-and-cut]]{{sfnp|Padberg|Rinaldi|1991}});<ref>{{YouTube|id=1FEP_sNb62k|title=Traveling Salesman Problem - Branch and Bound}}. How to cut unfruitful branches using reduced rows and columns as in [[Hungarian algorithm|Hungarian matrix algorithm]]</ref> this is the method of choice for solving large instances. This approach holds the current record, solving an instance with 85,900 cities, see {{harvp|Applegate|Bixby|Chvátal|Cook|2006}}.

An exact solution for 15,112 German towns from TSPLIB was found in 2001 using the [[cutting-plane method]] proposed by [[George Dantzig]], [[D. R. Fulkerson|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&nbsp;years on a single 500&nbsp;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.<ref>{{cite web
 |first1=David |last1=Applegate  |first2=Robert |last2=Bixby
 |first3=Vašek |last3=Chvátal  |first4=William |last4=Cook
 |first5=Keld |last5=Helsgaun
 |title=Optimal Tour of Sweden
 |date=June 2004 |access-date=2020-11-11
 |url=http://www.math.uwaterloo.ca/tsp/sweden/
}}</ref> 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<!-- Is this with a 500&nbsp;MHz processor. Please make clear what you mean by CPU year. --> (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 {{harvp|Applegate|Bixby|Chvátal|Cook|2006}}.