Show Summary Details

Page of

PRINTED FROM OXFORD REFERENCE (www.oxfordreference.com). (c) Copyright Oxford University Press, 2023. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single entry from a reference work in OR for personal use (for details see Privacy Policy and Legal Notice).

date: 13 September 2024

# travelling salesman problem n.

Source:
A Dictionary of Psychology

The problem of finding the shortest path that passes through a given set of points once and only once, as when a travelling salesman needs to visit a number of specified cities exactly once, using the shortest possible route. The problem is notoriously difficult to solve, because the number of possible tours rises rapidly with the number of cities. For 10 cities, there are 3,628,800 different tours from which to choose, because there are ten cities available for the first visit, and for each of these there are nine possibilities left for the second, hence there are 10 × 9 = 90 different ways in which the tour can begin with the first two cities, and for each of these there are eight possibilities left for the third visit, and so on, the total number of tours through the ten cities therefore being 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3,628,800 tours. For 20 cities, the number of possible tours is 2,432,902,008,176,640,000, and for 30 cities it exceeds 265 thousand billion billion billion. Even the world’s fastest supercomputer would take many billions of years to solve the travelling salesman problem for a tour of the 52 county towns of England and Wales or the 50 state capitals of the United States, but no efficient method of solving the problem has been found, and mathematicians have come very close to proving that it is impossible in principle to find an efficient solution to a problem of this type. US ... ...

Access to the complete content on Oxford Reference requires a subscription or purchase. Public users are able to search the site and view the abstracts and keywords for each book and chapter without a subscription.