The traveling salesman problem (TSP) is a classic combinatorial problem: given a set of cities, what is the path that visits each city once and only once, while covering the minimum distance?
For a small set of cities, the solution is trivial and can be discovered by simple inspection; however, the solution for even a moderate number of cities is out of reach for most home computers. For example, to exhaustively check all possible paths for a 48 city instance—assuming you could check one million paths a second—would take approximately 1047 years.
Despite all the research, there is still no known general solution to the TSP.
