Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Travelling salesman problem
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
===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–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−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 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.<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 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}}.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)