Lauren Ipsum and the Wandering Salesman

One of the first characters Lauren Ipsum meets is the Wandering Salesman. His life is governed by two rules: he must a) visit every town before going home, but b) never visit the same place twice. This is a deceptively simple problem. Finding a route which passes through all the towns is easy. Finding a short one is hard.
A story about computer science
and other improbable things.

The Wandering Salesman is happy person who doesn't like to think too much. At every point he just goes to the nearest place he's never been to. This isn't a terrible way to do it. It's better than random but it's not terribly good. Below is an interactive game that shows how it works. Push the "Solve it!" button to see him run around. You can also move the cities around and push the button again to see how his path changes.

You might notice that his path often crosses itself. This is a sign of less than optimal solution. There are many (many) other algorithms to find more efficient paths. A reasonable optimization might be to look ahead, say, three steps, consider the lengths of all of the combinations, and choose the shortest.

My favorite is the one used by a later character named Hugh Rustic, which depends on an army of ants that walk randomly and communicate with each other using pheremones. I'm still learning these new-fangled graphics libraries but I'll write a post about that one soon.