What is Travelling salesman problem?
[[File:Salesman.PNG|thumb|A salesman wants to visit all cities,A, B, C and D. What is the best way to do this (cheapest airline tickets, and minimal travel time)?]] [[File:TSP Deutschland 3.png|thumb|Optimal route of a salesman visiting the 15 biggest cities in Germany. The route shown is the shortest of the 43,589,145,600 possible ones.]] The '''Traveling Salesman Problem''' (often called '''TSP''') is a classic algorithmic problem in the field of [[computer science]] and [[:en:Operations_research|operations research]].<ref>{{Cite web|url=http://www.universalteacherpublications.com/univ/ebooks/or/ch6/travsales.htm|title=Travelling Salesman Problem, Operations Research|website=www.universalteacherpublications.com|language=en-US|accessdate=2017-11-13|archive-date=2017-11-21|archive-url=https://web.archive.org/web/20171121231500/http://www.universalteacherpublications.com/univ/ebooks/or/ch6/travsales.htm|url-status=dead}}</ref> It is focused on [[Optimization (computer science)|optimization]]. In this context, ''better solution'' often means ''a solution that is cheaper, shorter, or faster''. TSP is a mathematical problem. It is most easily expressed as a [[graph theory|graph]] describing the locations of a set of [[node]]s. [[File:William Rowan Hamilton painting.jpg|thumb|William Rowan Hamilton]]The traveling salesman problem was defined in the 1800s by the Irish mathematician [[William Rowan Hamilton|W. R. Hamilton]] and by the British mathematician [[Thomas Kirkman]]. Hamilton’s [[Icosian Game]] was a recreational puzzle based on finding a [[Hamiltonian cycle]].<ref>A discussion of the early work of Hamilton and Kirkman can be found in Graph Theory 1736–1936</ref> The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by [[Karl Menger]]. Menger defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the [[Nearest neighbour algorithm|nearest neighbour]] [[heuristic]]:<blockquote>We denote b