
related topics 
{math, number, function} 
{line, north, south} 
{album, band, music} 
{@card@, make, design} 
{system, computer, user} 
{rate, high, increase} 
{city, population, household} 
{city, large, area} 
{work, book, publish} 
{specie, animal, plant} 
{math, energy, light} 
{theory, work, human} 
{town, population, incorporate} 

The Travelling Salesman Problem (TSP) is an NPhard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.
The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is 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.
The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a subproblem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.
In the theory of computational complexity, the decision version of the TSP belongs to the class of NPcomplete problems. Thus, it is likely that the worst case running time for any algorithm for the TSP increases exponentially with the number of cities.
Contents
Full article ▸


related documents 
Discrete cosine transform 
Binomial coefficient 
Grothendieck topology 
Pythagorean triple 
Original proof of Gödel's completeness theorem 
Μrecursive function 
Determinant 
Padic number 
Lambda calculus 
Riemann integral 
Group theory 
Lie group 
Lebesgue integration 
Formal power series 
Combinatorics 
Class (computer science) 
Banach–Tarski paradox 
Redblack tree 
Dedekind domain 
Orthogonal matrix 
Hilbert's tenth problem 
Algebraic geometry 
Logarithm 
Big O notation 
Fast Fourier transform 
Closure (computer science) 
Continued fraction 
Singleton pattern 
Linear programming 
Serialization 
