Traveling Salesman in Polynomial Time

I had considered posting this on April Fools' Day, but it would have been very cruel.

Many years ago, as I was playing Mario Kart, I inadvertently solved a very difficult math problem in a very important way. Just for fun, I tried visualizing the absolute slowest way to go around a racetrack, and realized that in the game, aiming directly at the wall would either result in your go-cart stopping completely or moving very slowly perpendicular to your aim. That's when I realized that the racetrack could easily be used to find its solution. It's not something you can see from the point of view of the driver, but looking at the situation from above, the solution to the racetrack is as simple as the path of a rubber band that you stick down and wrap around the inner barriers of the course. The rubber band of course will automatically stretch out, going from one turn to another and showing you the exact location to make a turn, and when to shift from turning left to right, or vice versa.
Here's a visual representation of 3 racetracks:You'll notice I took the liberty of showing the shortest path for each of them as a red line. for the first track, there's no need, the track itself is its solution.

The second course's solution is a near-exact replica of the first course.

The third track, however, is where things get interesting. Although the solution isn't exactly like the second course, we can see that there's a mathematical relationship between these three tracks. Much like the derivative of a function, each step to the left represents a simplification of the course. This presents us with the ability to solve more complex problems, in much the same way.

Here we have a more complex racetrack, which I've taken the liberty of showing the solution for, to the right.

Down here I do something more interesting. I highlighted the curves where the driver has to go around and put dots where the racetrack doesn't allow the driver to take a shortcut. So these are the points on the graph that matter, they describe the path itself.On the right here, I did something really interesting. I deleted the barriers and the track itself, creating a representation of the dots that would be a traveling salesman problem. I have, essentially, gone from the solution to the problem to the problem itself. Thing is, I took the liberty of deleting the barriers, because I like randomness and want to see if there's a shorter path around these points. If you choose not to, you'll get the exact same path as before when we work the next few steps, but this is like doing it with training wheels or a bumper in bowling. We don't need it, we'd rather do a harder problem, and actually see some impressive results. After all, this is one of the hardest problems in math, so let's go ahead and be a badass.

K, here we go:This is a process I call Geometric Collapse. Basically we're taking a complex geometric shape (a rubber band-like circle-ish shape) and we're collapsing it into a series of much simpler shapes: lines. the first thing we do is wrap it around our little path, which you could visualize as oddly-shaped thumbtacks on a board, or perhaps as a delivery route, in which case you're now going to visualize adding stops to. turns out since the outermost points are necessary, they describe the extremes of the graph. Since we know we have to include them, and the path can't be any shorter, this is where we start. This can be very annoying to those of you who want to solve this programmatically, since there's no quick and easy way to get that other than starting off with it. However, and this is the big part:

We can, from this point, solve the problem correctly, and as quickly as a nearest-neighbor algorithm. All we have to do is remember that we want the nearest unconnected neighbor to the path itself, not the last point we visited. so if you're thinking of it as thumbtacks on a board, you're just stretching the band to the nearest unconnected thumbtack and pinning it down to the board. We proceed, as above, until all points are connected.

If you're visualizing it as a delivery route, you're thinking, "Where along my route can I get this delivery done so that it interferes the least with my schedule?"

The real reason this works so well is because of how powerful networks are. Visualizing the problem from the point of view of a single person, you're doomed to fail. It's too complex a task for one eye to do it (which is neat, since we have two eyes, perhaps our bodies go through this process naturally? food for thought!). Yet, when the delivery guy thinks about how to work something into his route, the problem becomes very easy.

But supposing he already has his route set up and he gets 4 new stops because he's operating so efficiently? Would adding them to his path work out just as well as starting from scratch and creating a path that includes all the old and new stops? Definitely worth testing.

But it's important, because it means you can solve a traveling salesman problem with 200 points in a matter of minutes, instead of 788,657,867,364,790,503,552,363,213,932,185,062,295,135,977,687,
000,000,000,000,000,000,000,000,000,000,000,000,000 calculations. (computers can do billions or trillions of these a second.)

That is to say, this is a way of actually doing it.

To put things in perspective, if you started a program today to calculate that problem, and the program was flawless, and the computer it was running on was upgraded every time it could be, and you moved it out of the way when earth blew up, and when our sun died, and when our galaxy went out, it would still be running when the universe ended of heat-death.

So solving this problem quickly is a good thing. :)
And I have no intentions of patenting the technology. It's a mathematical truth and it belongs to the world!

Join me next time when I describe another way of solving it, which is more programmatically-friendly. I call it "Geometric Explosion." It's also nice in that it can be done in three dimensions, which is a nice plus. I'll also discuss the most difficult situations in which geometric collapse is tested, namely on grid-like structures where the points are equidistant and it's difficult to choose how to proceed from where you are.

Until then, I can be reached via email, I am kingrames of gmail.
I can also be reached via twitter, if your scathing rebuttals are 140 characters or less. http://twitter.com/Kingrames

I welcome all comments, especially the derogatory hateful stuff, and especially if you prove me wrong. That's what this whole process is about. Please offer criticism of all kinds, I welcome it.


Feeling better now. Can't wait to be fully healthy again.

With most of the crap I was dealing with behind me now, all that's left is an impending hernia surgery, which will be quite fun. My, I'm cheerful, aren't I?

I was shopping on Amazon on Saturday, and after a purchase, Amazon felt it was appropriate to remind me of some stuff on my wish list. I went ahead and grabbed one, a game I already own the sequel to, and then amazon recommended "Record of Agarest War." my first reaction was something along the lines of "come on, amazon, you should know I hate Record of Lodoss War." Then I noticed that it clearly did not say Lodoss. Then, I looked at the cover of the game, and saw what looked like two girls in a bathtub. I said, "what the heck kind of war is that?" and immediately googled the game's name. I must say the trailer was hilarious. Deciding it was worth a look, I checked out the game to see what came with the preorder, and - it comes with one of those stupid japanese mousepads with the boobies-shaped wrist rests. I instinctively reached up to facepalm, and knocked my own hockey puck wrist rest onto the floor. "Dammit, I hate when that ..." I caught myself mid-sentence.

Well played, gentlemen. Well played.



My infection is gone, but I'm still feeling something from the medication. Perhaps it's just the withdrawal, but whatever it is, I'm miserable. What I wouldn't give for a star-trek-style medical miracle device.

I started watching Star Trek: Enterprise recently, and have seen most of season 1. Other than a few glaringly bad lines of dialogue I've found it acceptable. Perhaps I should go back and watch it one of these days when I'm not medicated.

Writing a blog is somewhat uplifting. Perhaps I should begin updating more than once a week.


So I have a deadly infection.

I'm infected with some sort of bacteria strain, close to my brain.  The nurse says it could be fatal.  I may have only minutes to live - and the fate of the world rests in my hands.  Or I could be exaggerating. Slightly. As much as this sucks, I find it isn't too bad. It could certainly be much worse.

The weather in Texas is never predictable, but lately it's been pretty crappy.  Probably just due to it being winter, but the rain and the snow (yes, it happened) really made going to work miserable.

I'm having trouble focusing on anything worthwhile, and thank God for caffiene or I'd be dead asleep. Perhaps tomorrow would be better for writing.