This is a script that just kind of grew over time. Having been out of college for a decade and a half, I thought it might be fun to go back and play with the old Traveling Salesman problem and see graphically what kinds of results various algorithms would produce. There was a lot of generic interface stuff that I had to do before I even got to the algorithms - buttons, drawing code, generation of random sample sets - but as a full-time kernel hacker I actually find that kind of stuff refreshing. The script may in fact be more interesting as an example of how to do certain things using Tkinter (the module which allows you to use Tk from Python) than as an exercise in computer science.

For the most part the various algorithms are described in the script itself, but here are some comments on the results I've found:

• The Short1, Short2, and Longest algorithms all produce fairly similar results, that don't look too terrible on screen. They all tend to produce reasonable paths except for a few long and/or crossing lines (often the last line to close the loop). Of the three, Short2 seems to be just barely better than the others.
• All three of the above algorithms do better than Euler, but not by a whole lot. However, even lowly Euler does much better than a totally random path.
• The Additive algorithm, which is actually the simplest even though it was the last to be implemented, almost always produces the shortest paths. They're certainly the best looking paths, never involving the long "across the whole board" lines of the others and rarely involving lines that cross. Detecting crossed lines, though easy for us, is a real pain algorithmically and in general provides little benefit.
• The two genetic algorithms are hideously expensive computationally. The Rotate algorithm also converges very slowly and hence yields terrible results at the small generation counts that are all I feel like waiting for. The Reverse algorithm, which superficially seems like it would be just about equal with Rotate, seems to converge on a reasonable solution much more quickly, providing results comparable to the more traditional algorithms (just slightly worse). This is one of the most interesting results I found, and provides a better demonstration than I've seen anywhere else of how a seemingly meaningless choice of mutators can affect the results when deploying genetic algorithms.

For the Additive algorithm only, the script also has Restart and Step capability so you can actually watch the path being built piece by piece. If anyone ever asks me, I might add this functionality to (some of) the other algorithms.

Well, that's all I can think of. Thank you for reading, and now...on with the show!