Traveling Salesman, continued.

Inbetween fighting with my OS's and discovering the wonders of Playonlinux, and my wondrous library of old games I can play again, I suppose I really should get back to this; It's kinda important.

Here I have a diagram of one case that might pop up while you're messing with Geometric Collapse. This is (supposed to be) a grid of points arranged all nice and neat for your convenience. (I blame MSPaint for my horrible art skills)

We do our normal Geometric Collapse first step, wrapping a rubber band around the outer points, and take a look at the closest point - problem is, that's all of them. Choosing one at random to begin, we see that there are two points on the path that are the closest to the new point, this causes much confusion.
Not to worry, we can just take things in order. When you have the choice of which point to hit up next, just take things in stride, and things will work out.
We can't add the point to the path a second time, that's... well, bad. But whatever. In case you're wondering, the point to the left there is now the nearest neighbor and will be connected to the diagonal line now. You'll end up with an H shape, if you follow along correctly.
But now we're going to break Geometric Collapse.

Here's a picture of a path that defeats the algorithm, depending on how you look at it.



It's very easy to see where the outer path will be once you've started, but then you have an interesting conundrum like the one above. You'll start out like that H pattern, creating a square indention in the path, but then you have a very strange problem. The nearest neighbor (well, had I drawn it more appropriately) will actually be very close to dead-even with a path directly outward from the nearest point. This is tricky because If Geometric Collapse worked correctly, we (sorta) know that we'd end up with a large C shape in the end. But I'm not too confident that will actually happen.

Will our hero turn out triumphant in the end? Who knows. Ooh, shiny!

Let's turn our attention (deficit disorder) to a new method: Geometric Explosion.
Geometric Explosion is much like Geometric Collapse in practice, with you building a path from points in space, but the coolest part of Geometric Explosion is that it works in 2d, 3d, and even 4d space (with Time as the 4th dimension).

This time, instead of creating a path around the outer edge and working our way in, we're going to create something out of nothing, beginning with a very simple geometric feature and 'exploding' it outward until it becomes an incredibly complex and beautiful path, which in the end will connect back to its real start and form a loop.

We begin with a cluster of stars, out in space.

No pictures here, since I'm bad enough at 2-dimensional artwork.

What we do first is create an imaginary point in space at the center of gravity/mass of that star cluster.

Then we draw a dotted line from that point to its nearest neighbor. This is our 'starting' point but we haven't even really begun in real space yet, we have an imaginary line and a real point in space.

From there we find the nearest neighbor to the imaginary path, and connect the real point to that point with a real line.

Now at this point I have to stop you because I find this very cool even though it's completely trivial information. We've just created a sort of triangle, only it's a triangle with one side of length ci, where c is a constant and i is the infamous imaginary number, the square root of -1. Our second side is of length c2, a second constant. our third side is of length NaN, or not a number, null, etc. We've effectively just linked together the real, the imaginary, and the nonexistent, and proven that the three are distinctly different. Sweet! I shall hereby dub thee the 'Awesome Triangle!" I'm sure plenty of math professors out there will consider you a waste of time but that, in my opinion, is the best way to use time. Back to the shortest path we go...

From here on we proceed much in the same way as we would with Geometric Collapse, with a nearest-neighbor-to-the-path procession through our stars, which will eventually form a large snake through space, and once all the stars are covered, we simply connect the tail to the head and form our Ouroboros. (Score another point for video game vocabulary!)

But what if those stars are actually moving?
Surely space is not so boring. Well, whatever. In the case of stars it's very easy to calculate what their path will be over the estimated time of your star trek, so we just use that as a guideline. We can give each star a curved vector to describe its path through space, and that gives us a timeline for each star. That means that the first star along the path will be connected to the "earliest" part of its vector, and the last star will be connected to the "latest" part of its vector. Something we might want to keep in mind is what might happen if a star decides "screw this I'm going bowling" and goes nova as we're along that path, all of the stars are going to have their vectors dramatically changed, but we can just roll with it. After all, we're able to calculate this path out so fast that we can do it while we're on the way to the first star. Let's just hope our shields can handle it, Captain.

As was the case before, I welcome any and all commentary on my methods, and encourage you to offer feedback. If you see anything wrong, take a torch to the house of cards and help build a better one! If this does turn out to stand up to scrutiny, that's a wonderful thing because it calls into question the idea that P is not equal to NP. If it fails your tests, that's just as important to know.

Best of luck to you all as you attempt to prove or disprove the theories, and have fun.

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,
173,263,294,742,533,244,359,449,963,403,342,920,304,284,011,984,
623,904,177,212,138,919,638,830,257,642,790,242,637,105,061,926,
624,952,829,931,113,462,857,270,763,317,237,396,988,943,922,445,
621,451,664,240,254,033,291,864,131,227,428,294,853,277,524,242,
407,573,903,240,321,257,405,579,568,660,226,031,904,170,324,062,
351,700,858,796,178,922,222,789,623,703,897,374,720,000,000,000,
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.

Enterprise

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.

Star Trek Online is good.

So I tried out Star Trek Online when it was in beta, fully expecting it to be incomplete, unfaithful, and mediocre.  Five bucks is nothing, I thought, and when I first logged in and played around, it seemed to be exactly as i predicted.

I logged back in a day later, and started messing around with my inventory after i had looted a tribble.  I found two of them, and couldn't spot the romulan ale i had looted earlier... a little while later I check back to see there are now 5 tribbles! I quickly handed them out to my bridge crew, hoping to stem the tide of the epidemic, and beamed down to a planet to investigate some fishy seismic readings. I hear purring, and quickly spin around to see which officer is responsible, when they all hide behind me. Then I calmly turn the camera around slowly and wait, and catch her in the act!

My vulcan engineer is smiling and stroking the tribble, and I just lose it and laugh.

The game is filled with all sorts of Trek stuff, but the best by far are all the little things.  The Wolf 359 fleet graveyard, the Ferengi smugglers, the planets you land on that look like they're straight out of the original series' oil paintings...

Good is just the right word to describe it.