Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

traveling salesman problem




Given a number n of cities, along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to the starting point. This is equivalent to finding the Hamilton circuit of minimum weight in a weighted complete graph. Mathematical problems related to the traveling salesman problem (TSP) were treated in the 19th century by William Hamilton, for example in his Icosian Game, and by Thomas Kirkman. The general form of the TSP appears to be have been first studied by mathematicians in the 1930s, notably by Karl Menger in Vienna and Harvard, and later promoted by Hassler Whitney and Merrill at Princeton. It has become a classic challenge to computer scientists seeking fast algorithms to complex problems. An approximate solution to the TSP for 15,112 cities, towns, and villages in Germany was found in 2001 by Princeton researchers using 110 computer processors and the equivalent of more than 22 years computer time on a 500 MHz machine.


Related category

   • GRAPHS AND GRAPH THEORY