travelling salesman problem

(redirected from traveling salesman)
Also found in: Dictionary, Thesaurus, Financial, Wikipedia.

travelling salesman problem

(algorithm, complexity)
(TSP or "shortest path", US: "traveling") Given a set of towns and the distances between them, determine the shortest path starting from a given town, passing through all the other towns and returning to the first town.

This is a famous problem with a variety of solutions of varying complexity and efficiency. The simplest solution (the brute force approach) generates all possible routes and takes the shortest. This becomes impractical as the number of towns, N, increases since the number of possible routes is !(N-1). A more intelligent algorithm (similar to iterative deepening) considers the shortest path to each town which can be reached in one hop, then two hops, and so on until all towns have been visited. At each stage the algorithm maintains a "frontier" of reachable towns along with the shortest route to each. It then expands this frontier by one hop each time.

Pablo Moscato's TSP bibliography. Fractals and the TSP.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
These problems are popularly known as Traveling Salesman Problem.
Gunn, "A two-commodity network flow approach to the traveling salesman problem," vol.
Reinelt, "TSPLIB: A traveling salesman problem library," ORSA Journal on Computing, vol.
A common approach is to transform the MTSP into an equivalent Traveling Salesman Problem, for which solutions can be found by exact methods (e.g., branch-and-bound algorithms and linear programming [26-28]) or approximate algorithms such as Genetic Algorithms, Simulated Annealing, and Ant System [29, 30].
and Branco I.: Exact solution of multiple traveling salesman problems.
The Traveling Salesman Problem (TSP) is one of the most intensively studied problems in computational mathematics.
The bottleneck traveling salesman problem (BTSP) is a variation of the usual traveling salesman problem (TSP).
A sampling of topics: new hierarchical routing protocol for WSNs, novel VNS algorithms on asymmetric traveling salesman problems, electric load forecasting, real-time visual feedback enhances Tower of Hanoi manipulation task, and part-of-speech approach to evaluation of textbook reviews, among many others.
did the traveling salesman approach with his sheep.
In 1872, a traveling salesman named Aaron Montgomery Ward tried something different.