So, there's this thing called the Traveling Salesman problem. It has nothing to do with farmers' daughters. A salesman has a certain number of different locations he needs to pass through on his sales route. In order to make the most efficient, and therefore profitable, use of his time, he wants to find the shortest possible route among the points.

This is one of those things that people are quite good at working out and computers absolutely suck at. The complexity of the problem increases exponentially with the number of points involved. Somewhere around 23 points (Illuminati take note), even the best algorithm slows to a crawl. As I understand it, if a general solution could be found that doesn't collapse with large numbers of points, it could be very useful in lots of areas, like networking and such.

So, I gave it a shot. With only the problem statement and a shaky, self-taught grasp on C++ and attendant DirectX, I set to work. I wrote a program to scatter a set of up to 100 points on the screen, string them together so that each point is connected to two others in a huge daisy chain, and start examining the connections. I gave it two rules to work with.

First, if the points were connected directly to each other, it compared the lengths of each point's other connection to the potential length of each point's connection to the other point's other connection's other end point. Wow, that's a complex sentence. Think of four points, A, B, C, and D. They are connected with line segments AB, BC, and CD. Considering the points B and C, the program determines if the total length of AB and CD is longer than the length of AC plus BD. If so, it rearranges the connections so that the length is shortened. In this case, the points would wind up being connected AC, CB, BD. Notice that points B and C are still connected to each other, but the direction of the connection is reversed.

Second, if the two points were not directly connected, the program compared the lengths of both connections to each point to the possible connections to each of the points connected to the other point under consideration, and swapped them around if the new configuration would produce a shorter total distance. Get it? Good.

The idea was that, starting from a random configuration, the path would evolve into the ideal path for a given set of points. An ideal path, anyway. Or at least ideal enough.

The good news is, it worked. The bad news is, it only worked about as well as I had heard other efforts did. It can solve a 50 point randomly-generated path. It just takes all night. I haven't had the patience to let a 100-pointer run to completion. I'm convinced that there are other rules I could implement to speed things up, if only I could figure out what they are. I've tried swapping just one leg between a pair of non-adjacent points, but it keeps breaking the path into multiple loops. I've tried detecting where two lines cross and uncrossing them, but again I have the path fracture problem.

I suppose I could run the path to make sure it remains whole whenever I make those changes, but it seems to me that that would take longer than just letting what works now work.

One other problem is that, in order to bump the solution out of local minima, I threw in a small random element to swap two points even if the result wasn't necessarily a shorter path. Balancing that random effect so that it does what it should without stirring the pot so much nothing ever settles down has been a continuing problem.

At some point, I'm going to tidy up the program so it doesn't need to be recompiled whenever a parameter is changed, and put it up here somewhere. Even if it doesn't get the job done all that well, it's still groovy to look at. Very meditative.