Traveling Salesman Problem

img_lrg/deutschland.jpg not found

© Wikipedia, Creative Commons Attribution-ShareAlike License.

The traveling salesman problem, originally called the "Knight's tour problem" by Euler, is a classic example of a simple optimization problem that is extremely difficult to solve in a reasonable amount of time. The blue line on this map of Germany shows the optimal path for a traveling salesman touring the fifteen most populous cities. This seemingly simple solution is one of over 43 billion possible routes. (Unit: 9)