follow Dictionary.com

It’s about time. We are now on Instagram!

traveling salesman problem

noun
1.
any mathematical problem that involves determination of the shortest path through several points.
Origin
1950-1955
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
traveling salesman problem in Technology

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 Article for 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

Word of the Day

Difficulty index for traveling salesman problem

Few English speakers likely know this word

Word Value for traveling

13
17
Scrabble Words With Friends