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 Traveling Salesman Problem
^{
*
}.

- More about the Traveling 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.