Travelling salesman problem

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 NP-hard 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 sub-problem 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 NP-complete 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
P-adic number
Lambda calculus
Riemann integral
Group theory
Lie group
Lebesgue integration
Formal power series
Combinatorics
Class (computer science)
Banach–Tarski paradox
Red-black 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