Click for larger, clearer.
But what are all such gaieties to me Whose thoughts are full of indices and surds?
x² + 7x + 53
= 11/3
-- Lewis Carroll
Like Yo --
(I have to stop hanging on IRC, chatting with Youth is degenerating my language skills.)
I'd already solved the 7-Node Santa Problem when the mysterious mathematical mystic ramanuJohn submitted his totally unexpected and awesomely correct answer. The Travelling Santa Problem was a go-to-kitchen-get-a-cup-of-coffee run. The Travelling Easter Bunny Problem is a little less speedy.
I have a very robust core program ("very robust" means it hasn't blown up so far), and attached please find a whilst-sleeping run. Very roughly,
7 hours = 1.05 % of all 13! paths
so even more roughly, the whole job should take an eerily Satanic 666 hours, or about 28 days. In the New Yorker article about the Chudnovsky Brothers' world-record-breaking pi expansion (billion+ digits) with their homebrew mail-order supercomputer (cooled by hardware-store fans purchased in winter, at their cheapest) in their Spanish Harlem slum down the block from the sidewalk corpse, one top-tier professor told the reporter that all mathematics is essentially about aesthetic preferences.
Expanding pi to world-record distances races the brothers' pulses and gives the brothers stiffies, while other equally accomplished mathematicians look on this task as though it were an above-ground swimming pool full of swine vomit and elimination. When told about the Chudnovskys' pi computations, one distinguished number theorist authentically recoiled in horror and yelled, "What for?"
Well, of course the purpose of this kind of massive computation is clear. Supercomputer manufacturers traditionally enjoy testing new machines by stretching pi, and most of the recent world records are held by a Japanese guy and his latest-model Hitachi xTremeSoroban. The Chudnovskys showed the reporter lots of amazing stats about these unimaginable distances of the pi expansion, and enthusiastically proclaimed that the farther you compute the expansion, the less you know or understand about pi.
(The reporter asked where they kept pi, and they handed him a hard disk. "It's in here," one brother explained.)
A retired telephone company guy has an antenna and dish farm at the corner of F******* Road and B**** P** Road. His ham specialty: He bounces radar signals off the Moon. I told a friend this, and she asked: "Why?" I was at a loss to answer her, but I know Why.
Actually, I don't know Why, but I'm just totally kookoo for cocoapuffs about massive computation, and the tiny morsels of it I can cram into whatever outdated wheezing PC I've got plugged in under the desk [more about which later]. I guess at least half the proggies I write are Really Silly Things to murder mosquitos with a hydrogen bomb -- or more precisely, to murder an elephant by poking it with a sewing needle 4.55 x 10^40 times, while S.W.M.B.O. and I go out to dinner.
I think a lot of it is that I'm a really shitty mathematician and a worse math student, and my grasp on actual sophistication is so thready that I started substituting massive computation for the textbook elegance and straightforwardness I don't have and probably never will.
(When I can't find an antidifferential, I love to carve an area into a gazillion skinny rectangles and sum their areas; I go to the kitchen for coffee, I come back, the answer awaits. You have a problem with this?)
I took a first-gen Toshiba laptop with me to Europe once, and when I got to Communist Prague -- and even attended their lollapalooza Soviet Bloc Komputer Expo '88 -- it dawned on me that I was schlepping around the 2nd or 3rd most powerful computer in Czechoslovakia.
And a computer you buy for your kid at Wal-Mart has more punch in it than all the digital computers of all the combatants during World War II. Turing would have begged to borrow my Toshiba laptop, or would have had MI6 whack me for it. The computers the Poles first devised to crack the Germans' Enigma Code were electromechanical and went tik-tik-tik-tik, so they called them bombes. But they cracked the early Enigma codes. ENIAC, also largely electromechanical, reminded one visitor of a room full of knitting grandmothers.
The more I futz around with it, this Easter Bunny Problem turns out to be sincerely interesting (to me). Like Tantulus, I can see delicious grapes -- The Answer -- just out of my reach. But just a little bit out of reach, not an infinite, unimaginable out of reach. And it's just out of my pathetic programming reach so far, but the Answer is certainly easily within my PC's reach if I just keep running the dumb proggie for 28 days.
There are, apparently, well-known techniques to furp back excellently short paths within a very short time. But only an exhaustive search of all paths can guarantee finding The Shortest Path. The overnight runs furp back
PATH WORD and PATH LENGTH
REDACTED & CLASSIFIED
by order of
VLEEPTRON MINISTRY OF SECRETS
in about 2 hours, and then can't find a shorter path for the rest of the night; after this one, then the serious 28-day thermonuclear mosquito hunt begins. REDACTED & CLASSIFIED
by order of
VLEEPTRON MINISTRY OF SECRETS
One particularly appealing aspect of TSP is that nobody's (yet) much smarter about TSP than I am, at least insofar as any shortcuts to actually find the shortest path. There are no shortcuts yet. Bob's Thinking into this problem is about as advanced as the Cal Tech Combinatorics professor's thinking. TSP is officially classified as NP-Hard. [see Wikipedia thing below] More than that, there's a buzz that there's a proof of This:
IF a shortcut to TSP can be found,
THEN such a shortcut will apply
to ALL NP-Hard problems.
So the humble, low-rent, trailer-park TSP is or can be the key to simplifying/shortening all NP-Hard problems. THEN such a shortcut will apply
to ALL NP-Hard problems.
The Near Future of the Easter Bunny Problem
1. As hinted above, I'm about to buy a new Dell, probably with an Intel Core 2 Duo, whatever the fudge that is. So from a HARDWARE standpoint, everything's coming up roses with the Easter Bunny, it's all Win-Win and Optimism and The Sun'll Come Out Tomorrow. I can see the Light At The End of the Tunnel. The Boys'll Be Home By Christmas.
2. Not so rosey with the SOFTWARE, me being Mister QuickBASIC FOR NEXT IF GOTO Guy. But I got me this Automatic Repeating Hammer and the sucker actually works. I suspect I'm a cinch to set the Guinness World Record for Slowest Solution ever found for a 13-Node [Euclidean / Planar] TSP. Maybe the Core 2 Duo thingie will cut it down to 24 days.
3. I have these 2.5 brainstorms:
A. add a Yank-Off-Save-and-Resume (YOSaR) routine, so BUNNY doesn't really have to run continuously for a month on a system where the cat likes to play with the red button on the power strip. Maybe I won't get the answer in time for Easter Sunday, but I would find it deeply pleasing to know that every time I power up or re-start the PC, BUNNY chugs toward the Summit for another 16 hours. YOSaR would prevent against a total-loss catastrophe that occurred when the program had analyzed 83 percent of all possible paths.
B. The Distributed Computing Thang
13! = 6,227,020,800
but 13!/13 = 12! = a mere 479,001,600
so I could carve the Bunny Problem into 13 13ths, and e-mail BUNNY and a bloc of 1/13th of all paths to 13 different PC users. This suggests each PC would only have to run BUNNY for 2.2 days. Each block of sequential paths would e-mail me its local minimum path, and the winner would be the shortest of the 13.
This way, if I could manipulate or finesse 12 other PC-owning suckers, I could actually get the damn thing solved before Easter, mirabilu visu.
Setting up the START path of each bloc, I am unhappy to report, exceeds my current Understanding of Combinatorics and the crappy IF-based method I'm using to generate all paths. It apparently won't be as falling-off-log simple as
Bloc . Start Path
================
01 ABCDEFGHIJKLM
02 B............
03 C............
04 D............
05 E............
06 F............
etc.
11 K............
12 L............
13 M............
================
more's the pity. But maybe a Flash Of Insight might come to me and I'll figure out a scheme to partition the Bunny into 13 distributed parts.
[UPDATE: I got the Flash Of Insight,
I can partition the Bunny into
13 equal parts now!]
I can partition the Bunny into
13 equal parts now!]
C. Much Smarter Combinatorics You saw the Horror of my path-generator. Surely there's a path-generator which mechanically chugs out all paths, new path issuing mechanically from old path, with no IF statements. Just eliminating the IF delays in generating all paths would be a tremendous time-saver. I've been playing around with generating few-node path sets like ABCDE. I haven't got very far yet (and I've misplaced my Schaum's Combinatorics), but my early thinking uses the model of Refrigerator Magnets.
[see Figure 1.]
So then the trick is to find an algorithm that uses these primitive magnet manipulating functions to generate all possible paths. I had to cook up something very much like this to automate the Towers of Hanoi with large numbers of disks. (Also not Elegant, but if my PC isn't busy for a day or two, it can shift a stack of 64 disks from one pole to another one disk at a time.)
Okay, all this thinking is exhausting me, and I'm not very smart. I would be very appreciative of ramanuJohn's thoughts on these profound matters. Maybe you'll be stuck now and then in Wait Mode, and the Bunny might save you from having to read about Anna Nicole Smith in People magazine. Please carry a pad of graph paper and a calculator with you at all times.
Bob
============
from Wikipedia:
============
Euclidean TSP
Euclidean TSP, or planar TSP, is the TSP with the distance being the ordinary Euclidean distance. Although the problem still remains NP-hard, it is known that there exists a subexponential time algorithm for it. Moreover, many heuristics work better. Euclidean TSP is a particular case of TSP with triangle inequality, since distances in plane obey triangle inequality. However, it seems to be easier than general TSP with triangle inequality. For example, the minimum spanning tree of the graph associated with an instance of Euclidean TSP is a Euclidean minimum spanning tree, and so can be computed in expected O(n log n) time for n points (considerably less than the number of edges). This enables the simple 2-approximation algorithm for TSP with triangle inequality above to operate more quickly. In general, for any c > 0, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/c) times the optimal for geometric instances of TSP (Arora); this is called a polynomial-time approximation scheme. This result is an important theoretical algorithm but is not likely to be practical. Instead, heuristics with weaker guarantees are often used, but they also perform better on instances of Euclidean TSP than on general instance
===============
NP-Hard
NP-Hard (Nondeterministic Polynomial-time hard), in computational complexity theory, is a class of problems informally "at least as hard as problems in NP." A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H, i.e. L \leq_T H. In other words, L can be solved in polynomial time by an oracle machine with an oracle for H. Informally we can think of an algorithm that can call such an oracle machine as subroutine for solving H, and solves L in polynomial time if the subroutine call takes only one step to compute. NP-hard problems may be of any type: decision problems, search problems, optimization problems. As consequences of such definition, we have (note that these are claims, not definitions):
* problem H is at least as hard as L, because H can be used to solve L;
* since L is NP-complete, and hence the hardest in class NP, also problem H is at least as hard as NP, but H does not have to be in NP and hence does not have to be a decision problem;
* since NP-complete problems transform to each other by polynomial-time many-one reduction (also called polynomial transformation), therefore all NP-complete problems can be solved in polynomial time by a reduction to H, thus all problems in NP reduce to H; note however, that this involves combinig two different transformations: from NP-complete decision problems to NP-complete problem L by polynomial transformation, and from L to H by polynomial Turing reduction;
* if there is a polynomial algorithm for any NP-hard problem, then there are polynomial algorithms for all problems in NP, and hence P = NP; * if P \neq NP, then NP-hard problems have no solutions in polynomial time, while P = NP does not resolve whether the NP-hard problems can be solved in polynomial time; * if an optimization problem H has an NP-complete decision version L, then H is NP-hard;
* if H is in NP, then H is also NP-complete because in this case the existing polynomial Turing transformation fulfills the requirements of polynomial time transformation; A common mistake is to think that the "NP" in "NP-hard" stands for "non-polynomial". Although it is widely suspected that there are no polynomial-time algorithms for these problems, this has never been proven.
Examples
An example of an NP-hard problem is the decision problem SUBSET-SUM which is this: given a set of integers, does any non empty subset of them add up to zero? That is a yes/no question, and happens to be NP-complete. Another example of an NP-hard problem is the optimization problem of finding the least-cost route through all nodes of a weighted graph. This is commonly known as the Traveling Salesman Problem.
There are also decision problems that are NP-hard but not NP-complete, for example the halting problem. This is the problem "given a program and its input, will it run forever?" That's a yes/no question, so this is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. For example the Boolean satisfiability problem can be reduced to the halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, while the halting problem, in general, is not.
Alternative definitions
An alternative definition of NP-hard that is often used restricts NP-Hard to decision problems and then uses polynomial-time many-one reduction instead of Turing reduction. So, formally, a language L is NP-hard if \forall L^\prime\in \mathbf{NP}, L^\prime \leq_p L\!. If it is also the case that L is in NP, then L is called NP-complete.
NP-naming convention
The NP-family naming system is confusing: NP-hard problems are not all NP, despite having 'NP' as the prefix of their class name! However the names are now entrenched and unlikely to change. On the other hand, the NP- naming system has some deeper sense, because the NP- family is defined in relation to the class NP: NP-complete - means problems that are 'complete' in NP, i.e. the most difficult to solve in NP; NP-hard - stands for 'at least' as hard as NP (but not necessarily in NP); NP-easy - stands for 'at most' as hard as NP (but not necessarily in NP); NP-equivalent - means equally difficult as NP, (but not necessarily in NP);
No comments:
Post a Comment