traveling salesman problem

traveling salesman problem

noun
any mathematical problem that involves determination of the shortest path through several points.

Origin:
1950–55; from the idea that a traveling salesman would face such a problem in making rounds within a territory

Dictionary.com Unabridged
Based on the Random House Dictionary, © Random House, Inc. 2014.
Cite This Source Link To traveling salesman problem
FOLDOC
Computing Dictionary

traveling salesman problem definition

spelling
US spelling of travelling salesman problem.
(1996-12-13)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Encyclopedia Britannica
Encyclopedia

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.

Encyclopedia Britannica, 2008. Encyclopedia Britannica Online.
Cite This Source
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;