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.
