Home
TSP is an NP-hard problem in combinatorial optimization. That's a term academics use to classify its complexity. When a problem is NP-hard, we cannot (yet) prove that a polynomial time solution exists.
A problem is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(nk). Polynomial-time algorithms are said to be "fast."
BUT WHAT DOES IT MEAN‽
In layman's terms, when a problem is described as "NP-hard", that means it belongs to a class of problems that very quickly become computationally expensive to solve as the input size grows. These problems are in fact rather easy to solve by enumerating all possible solutions and testing them, but solving them takes a long time on larger instances of the problems.
TSP is one of the most intensively studied problems in optimization. It's used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of error.
TSP can be modelled as an undirected weighted graph.
- vertices = cities
- edges = paths
- edge weight = path distance
It's a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph (i.e. each pair of vertices is connected). If no path exists between two cities, adding an arbitrarily long edge will complete the graph.
Note that the symmetry which undirected graphs provide is often an oversimplification. Traffic collisions, construction, one-way streets, and paid routes are examples of how this symmetry could break down. In such cases a directed graph will be more accurate.
