Solving the Traveling Salesman Problem

The Traveling Salesman Problem (TSP for short) is a classic problem in computer science. Wikipedia succinctly states the problem like so:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

First formalized in 1930, the TSP has been studied and fiddled with ever since. There are lots of ways to try solving the problem, but the devil is in the details. Most of us start with a simple assumption: Let's pick a starting city, then just start walking around the map, choosing the nearest city every time. Rinse, repeat. This algorithm is called "Greedy," and while it does a reasonable job for very short routes, it often fails to make the overall route the shortest, because it doesn't consider the entire route. (It "greedily" chooses the optimal choice in each leg of the route, at the possible expense of the larger route.)

Take a look at this video, illustrating several algorithms for solving the TSP, and compare the complexity of the solutions. Computers are rad.

Read more about this video from its creator, James "poprhythm" Kolpack. For a lot more on this problem and why it matters, check out this lecture.

[h/t: Kottke.]