travelling salesman problem n.
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.
Please subscribe or login to access full text content.
If you have purchased a print title that contains an access token, please see the token for information about how to register your code.
For questions on access or troubleshooting, please check our FAQs, and if you can''t find the answer there, please contact us.
