Imagine a bunch of cities, say, the
35 largest cities in Minnesota. Your job is to visit each city once and only once covering the fewest total
miles possible. (Visiting a city more than once will never improve your solution. Consider why that might be
true.) That's the Travelling Salesman Problem
^{
*
}.

- More about the Travelling Salesman Problem at Wikipedia
- More about WillyLoman at Github

...or add
random points.

^{*}This is just one variation of the TSP. There are many others. For example, instead of cities on a
map, consider visiting points in three dimensional space or four dimensions or five. Consider other costs.
Distance (mileage) may not be important. Maybe the important costs are tolls or travel time or path quality
(road conditions, error rates in a computer network, etc) or some combination. What makes these problems
similar is that they can all be represented as a
graph. Graph nodes are cities, computers, neurons, etc. and edges are roads, fiber optic cable, or synapses.
Each edge has a cost. A TSP algorithm traverses the graph with the smallest possible cost.

For the politically curious, the Travelling Sales
*man* Problem is no more about men than breakfast cereal or socks or air travel. We could just as easily
call it the Pollinating Bee Problem. We don't, though. Instead, we call it the Travelling Salesman Problem
because that's what everyone else calls it and that helps us find things on the internet and in the library.