Traveling Salesman Problem
Problem
Given any complete (or near-complete) weighted graph, find a minimum-weight Hamilton cycle.
Discussion
Every complete graph of order $3$ or greater is Hamiltonian.
In this context, near-complete is taken to mean a graph in which the condition for Ore's Theorem is fulfilled, and to spare.
So the problem is not to just find a Hamilton cycle (for large graphs there will be plenty) but to find the best Hamilton cycle.
It is clear that, for a finite graph, there will be a finite number of Hamilton cycles to check.
However, as the number of vertices increases, then the number of Hamilton cycles increases exponentially (in fact, factorially). (See Number of Hamilton Cycles in Complete Graph). Therefore, checking every path and comparing their weights by exhaustion is, indeed, exhausting.
There is no known efficient algorithm that can be guaranteed to produce the minimum-weight Hamilton cycle required.
There are known to be some relatively efficient approximate solutions, some of which work pretty well.
The Traveling Salesman Problem is NP-Complete. This makes finding an efficient algorithm for the solution unlikely.
Note
The problem gets its name from the practical application of a salesman, traveling to a number of cities, looking for the optimum route that will keep the distance travelled to a minimum. It is understood that the distance between each pair of cities is known (thereby establishing that the game plan is a complete weighted graph).
Linguistic Note
The UK English spelling of the Traveling Salesman Problem is Travelling Salesman Problem.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 3.2$: The Salesman's Problem: An Introduction to Hamiltonian Graphs
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): travelling salesman problem
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): travelling salesman problem
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): travelling salesman problem