Forgotten in our culture of big box stores and internet 'one-clicks' is the Fuller Brush salesman. I know of a leader who supported himself through college by selling the product door-to-door, and Billy Graham tells about his experiences as a Fuller Brush salesman in his autobiography. But I digress.
The traveling salesman problem is essentially, given a list of cities and traveling costs, what is the optimum round-trip route for the salesman? Mathematicians describe this as a NP-hard problem, or non-deterministic polynomial-time (NP) hard. Georgia Tech has an interesting website dedicated to the problem. Computer algorithms for seeking a solution are getting better. In 1954, the dantzig42 algorithm could solve a route for 49 cities. In 1987, 2392 cities, and in 2004, 24,978 cities. As you can expect, the problem gets really hard as the number of cities increases. The exact number of possible routes for a 3038 city tour is computed by Georgia Tech and the number occupies several HTML pages.
One of my favorite software tools, Mathematica, has a demonstration of the problem. The Clay Mathematics Institute, who offers a $1M prize for the solution, also has interesting discussion of the P vs NP problem.
Comments