traveling salesman problem
traveling salesman problem
1950–55; from the idea that a traveling salesman would face such a problem in making rounds within a territory
Based on the Random House Dictionary, © Random House, Inc. 2012.
Cite This Source
00:10
00:09
00:08
00:07
00:06
00:05
00:04
00:03
00:02
00:01
| a scrap or morsel of food left at a meal. |
| a fool or simpleton; ninny. |
traveling salesman problem definition
spellingUS spelling of travelling salesman problem.
(1996-12-13)
traveling salesman problem
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 nonpolynomial), for which no known efficient (i.e., polynomial time) algorithm exists.
Learn more about traveling salesman problem with a free trial on Britannica.com.
Cite This Source
