## traveling salesman problemGiven 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 | |||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |