Member Portfolios

[MacHeadCase]

Quote:

Originally Posted by mathogre

Okay I'm now officially stuck. The TSP is an enormous computational problem, and an even more challenging algorithmic problem. In a nutshell, the traveling salesman goes from one place to a series of other places and then back home. The challenge is to find the shortest path for him to take. The problem gets big really quickly.

For instance, 10 points can be connected with just 45 lines. Not much, huh? The problem is finding the right 10 lines to connect everything. You have 3,190,187,286 possibilities. It's really not a lot computationally, but this is only 10 points. I have the means to reduce the number of lines to 23, yielding 1,144,066 possible combinations.

My goal is to connect something like 20,000 points. From those you get 199,990,000 lines. The possible combinations of 20,000 points is a number that has over 88,000 digits in it. I can potentially reduce the number of lines to maybe 100,000. One hundred thousand (or five lines per point) is much better than nearly two hundred million lines. Still, the number of combinations results in a number with nearly 22,000 digits in it. The Gods either laugh or shudder. It's generally accepted that processing something like 10^100 combinations is uncomputable. 10^22,000 is laughable. 10^88,000 may as well be infinity for this problem anyway.

The real experts have worked with point sets in the range of over 80,000, and use supercomputing resources to get answers that are probably good. They use decent approaches to the solution given the enormity of the problem, but the approaches are inelegant and do not yield the definitive answers.

Tossing out most of the irrelevant lines is easy. Tossing out the rest of them is the challenge, and essential to having any chance at solving the problem. I'm stuck today. I'll probably never solve the problem, but I've learned some things along the way, so this is a Good Thing. I just don't like getting stuck on a problem.

Wow! Little did I know it was so challenging! All the more power to you, MO!

[mathogre]

Quote:

Originally Posted by MacHeadCase

Wow! Little did I know it was so challenging! All the more power to you, MO!

Thank you MHC! There's this little flaw in me that says the impossible always has some kind of solution. I've solved some supposedly uncomputable problems in the past, so this "flaw" isn't entirely irrational. This problem will most likely simmer long into the future. That too is a Good Thing.

[MaDDoG]

As you say MO, you have learned something along the way so your time was not wasted.

Power to you brother.

[Brown Study]

Isn't the TSP as old as mathematics? I thought it's along the lines of the prime-number search. Doesn't it go on forever, no matter how powerful the computers, almost like computing pi to a zillion decimal places?

[mathogre]

Quote:

Originally Posted by MaDDoG

As you say MO, you have learned something along the way so your time was not wasted.

Power to you brother.

Thank you MaDDoG!

Quote:

Originally Posted by Brown Study

Isn't the TSP as old as mathematics? I thought it's along the lines of the prime-number search. Doesn't it go on forever, no matter how powerful the computers, almost like computing pi to a zillion decimal places?

Old as math? Certainly. Does it go on forever? It might as well, given how difficult it is to solve. Unlike pi however, the TSP is limited for a given number of points. It's just that solving it for very large point sets is so beyond us as to effectively require an infinite number of trials.

The problem however should be solvable I think (a conclusion I reach with my ever twisted mind). When you take a set of points and take all of the lines connecting them, there's a simple way to eliminate most of the irrelevant lines and keep all of the relevant ones. Even with a very large number of points and lines, removing most of the junk is pretty. It's removing that last set of junk that's a challenge.

[mathogre]

The fire still burns on this one. In the next week or two I'll - hopefully - post a PDF of some sample short paths for small sets of points. I just rewrote one of the programs and now I'm getting all of the legitimate short paths. On one set of 10 randomly selected airports, it looks as if I'm getting 86 unique circuits from one airport through all of the others and back to the starting point.

I need to plot these to see what lines are being used. This is a brute force method that is fast with 10 airports, but because of the nature of the problem it will probably reach its limits at 20. That's okay. My hope is to understand something about which lines are not used and why. If I can eliminate lines I don't need, the computation becomes simpler.

[MacHeadCase]

Go go go MO!

[mathogre]

Thank you MHC!

Here's a working desktop image of what I've been doing. That's Emacs in the background with a plain text procedure/notes file, three Terminal windows (one nearly hidden), and Gnuplot, graphing the distance of each of the paths against the specific number of the path. There are 172 paths total for 10 airports (mostly these are small municipal airports or heliports), ranging in distance from 4,000 miles to nearly 8,000 miles. The upper front terminal window shows the output of the function that searches for complete circuits around the airports. This morning I added the function that calculates and shows the distance.

It's probably pretty boring to almost everyone, but this is what the Mac is to me - a great little number cruncher that also happens to be a fun little machine.

[Rxx]

Such talent