Scatterbright

Solving a Traveling Salesman Problem with WillyLoman

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 * .

Click on the canvas to add cities.

...or add random points.
Your browser does not support the canvas element. Sorry.
Cities: 0
Distance:
Iteration:
Improvements:
This algorithm visits each city in the order they were added to the problem. It doesn't change or improve.
Generates a random solution and quits.
Generates a random solution. If it's better than the current solution, it keeps it. If not, it runs again. This algorithm runs until you stop it.
Moves to the nearest neighbor from the current city until it's visited every city. Repeats this process starting from every city. Keeps the best result.

This is a good baseline to test against other algorithms.
This algorithm tries every single possibility to determine the shortest route. As such, it's very slow. For tours larger than a dozen cities, you'll be waiting for a long time. Much larger than that and you'll be waiting forever.
Similar to a brute force algorithm except it tries to determine when a partial solution is hopeless. If the best it can hope for is worse than its current best, it tries something else.
Uses dynamic programming to determine the solution. That means you won't see progress until it's done. It just thinks and thinks and ... boom, gives you a solution. It's pretty good at solving small tours, but will eat up all your memory and more as the tours grow.
Imagine that a solution is a gene. Create a bunch, determine which are best, breed them, and repeat forever. "Breeding" a solution means a chance of mutation (cities jump to a new location) or crossing two solutions (taking a subtour from one and merge it with another) or both. More here.
Just the mutation process of a genetic algorithm.
Just the crossover process of a genetic algorithm.
A 2-opt algorithm picks two edges (in the graph world) and determines if swapping their endpoints will improve the solution. If it does, it keeps it. This version keeps the first improvement and starts again.
Another 2-opt algorithm. This one tries all possible swaps and keeps the best.

*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.