traveling salesman problem
- traveling salesman problem
-
any mathematical problem that involves determination of the shortest path through several points.
[1950-55; from the idea that a traveling salesman would face such a problem in making rounds within a territory]
* * *
an
optimization problem in
graph theory in which the nodes (cities) of a graph are connected by directed edges (routes), where the weight of an edge indicates the distance between two cities. The problem is to find a path that visits each city once, returns to the starting city, and minimizes the distance traveled. The only known general solution
algorithm that guarantees the shortest path requires a solution time that grows exponentially with the problem size (i.e., the number of cities). This is an example of an
NP-complete problem (from
non
polynomial), for which no known efficient (i.e., polynomial time) algorithm exists.
* * *
Universalium.
2010.
Look at other dictionaries:
Traveling Salesman Problem — [engl.], Handlungsreisendenproblem … Universal-Lexikon
Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein … Deutsch Wikipedia
Traveling Salesman Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein … Deutsch Wikipedia
traveling salesman problem — any mathematical problem that involves determination of the shortest path through several points. [1950 55; from the idea that a traveling salesman would face such a problem in making rounds within a territory] … Useful english dictionary
Euklidisches Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… … Deutsch Wikipedia
Metrisches Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… … Deutsch Wikipedia
Rectilinieares Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein … Deutsch Wikipedia
Bottleneck traveling salesman problem — The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. It is stated as follows: Find the Hamiltonian cycle in a weighted graph with the minimal weight of the most weighty edge of the… … Wikipedia
Traveling-Salesperson-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein … Deutsch Wikipedia
Traveling Salesperson Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein … Deutsch Wikipedia
