0399: "Travelling Salesman Problem"
Moderators: Moderators General, Prelates, Magistrates
Re: "Travelling Salesman Problem" Discussion
I saw the right frame first. Punchline'd.
Re: "Travelling Salesman Problem" Discussion
As shown in the Wikipedia article: http://en.wikipedia.org/wiki/Traveling_salesman_problem#Special_cases, there are usable polynomial algorithms that under some reasonable assumptions (Triangle Inequality), approximate the TSP solution (only 1.5 times worse than the optimal solution, at worst).
This leads to the question: What realworld problems are not solved reasonably by the above? What practical problems do not have the Triangle Inequality?
This leads to the question: What realworld problems are not solved reasonably by the above? What practical problems do not have the Triangle Inequality?
Re: "Travelling Salesman Problem" Discussion
MysticTerminator wrote:WHOA GUYS
there appears to be a vertex of very high degree in between the first and second panels, located in what would seem to be the midwest? What might this indicate! PERHAPS it is to be the next point of a reallife XKCD meeting?!
That would seem to be St. Louis. The other dots, as far as I can tell are Boston, New York, Philadelphia, Washington DC, Jacksonville(?), Miami, New Orleans/Houston, Dallas, San Antonio(?), Phoenix, LA, SF, Seattle, Denver, Chicago/Detroit, and somewhere out in the middle of South Dakota/Nebraska... Omaha? Rapid City? WALL DRUG!?!?!?!

 Posts: 26
 Joined: Thu Aug 02, 2007 11:58 am UTC
Re: "Travelling Salesman Problem" Discussion
While both of the guys are salesmen, only one is traveling.
Re: "Travelling Salesman Problem" Discussion
ב is used, and apparently ג and ד occasionally are too (also in the theory of transfinite cardinals). I have never heard of ש being used for anything  was there a particular reason you asked about that letter?zinder wrote:Don't forget the Hebrew alphabet. We use that from time to time... though really only א (Aleph) as far as I know. (Do any of the others get used? What does שּ (Shin) stand for?)
This is a placeholder until I think of something more creative to put here.
Re: "Travelling Salesman Problem" Discussion
Jesus, n^{2}2^{n}? Just an increase by 1 sounds nasty as it gets bigger and bigger.
Re: "Travelling Salesman Problem" Discussion
Quite frankly I'm just surprised anyone has managed to take the MasterCard advertisement format this far.
Re: "Travelling Salesman Problem" Discussion
glitter wrote:...
It is wrong to measure the space complexity (as according to the wikipedia article) as O(n) in units of rods. Each rod is length m. The space complexity is clearly O(nm). However, the input takes at most n log m bits to write down. This makes the space complexity exponential in the size of the input.
However, log() is monotonically increasing, so a less inefficient spacial encoding is replacing an original rod of length m with a rod of length log(m). Thus providing O(n log(m)) spatial encoding. One could recurse this recoding indefinitely, taking logs of logs of ..., leaving an O(n epsilon) encoding. However, the limit of this reencoding might make comparisons a bit trickier...
Re: "Travelling Salesman Problem" Discussion
I read XKCD each morning before going to class, and this week has been finals week for me. Guess what problem showed up on my Algorithm test today? Thanks XKCD, I'm pretty sure I got that one right

 Posts: 1
 Joined: Fri Mar 21, 2008 1:58 pm UTC
Re: "Travelling Salesman Problem" Discussion
It cries out to be a haiku:
Bruteforce solution:.............O(n!)
Try dynamic programming:...O(n^2 2^n)
Selling on Ebay:....................O(1)
Anyone else have this thought, or am I in the wrong place?
Bruteforce solution:.............O(n!)
Try dynamic programming:...O(n^2 2^n)
Selling on Ebay:....................O(1)
Anyone else have this thought, or am I in the wrong place?
Re: "Travelling Salesman Problem" Discussion
Damnit Randal! You just *had* to go and solve the Traveling Salesman Problem! Now all encryption is worthless, because it all depends on NPcomplete problems being *hard*.
The problem I have with rocketsocks (admittedly academically 100% correct) explanation is that, IMHO, O(2^n) is very deterministic  it's deterministically timeconsuming. As such, I tend to think of NP as meaning Nonpolynomial aka Exponential (and while n! doesn't actually look exponential, it's actually even worse.)
The problem I have with rocketsocks (admittedly academically 100% correct) explanation is that, IMHO, O(2^n) is very deterministic  it's deterministically timeconsuming. As such, I tend to think of NP as meaning Nonpolynomial aka Exponential (and while n! doesn't actually look exponential, it's actually even worse.)
 theyranos
 Posts: 16
 Joined: Fri Mar 21, 2008 2:28 pm UTC
 Location: About 30 minutes southwest of the armpit of nowhere.
 Contact:
Re: "Travelling Salesman Problem" Discussion
If you're selling stuff on ebay, isn't the traveling salesman problem still O(vertices) since you have to prepare that many boxes for the postman?
_{Had enough arguing about xkcd? Perhaps I can refer you to a crappy comic of my own.}

 Posts: 5
 Joined: Wed Aug 29, 2007 8:56 am UTC
Re: "Travelling Salesman Problem" Discussion
Peaker wrote:As shown in the Wikipedia article: http://en.wikipedia.org/wiki/Traveling_salesman_problem#Special_cases, there are usable polynomial algorithms that under some reasonable assumptions (Triangle Inequality), approximate the TSP solution (only 1.5 times worse than the optimal solution, at worst).
This leads to the question: What realworld problems are not solved reasonably by the above? What practical problems do not have the Triangle Inequality?
The hubandspoke system of many airlines. Very often it is cheaper to fly from Boston to Chicago to Washington D.C. than to fly directly if the airline has a hub in Chicago.

 Posts: 105
 Joined: Mon Aug 20, 2007 11:30 am UTC
Re: "Travelling Salesman Problem" Discussion
crypticgeek wrote:Paiev wrote:Alttext: What's the complexity class of the best linear programming cuttingplane techniques? I couldn't find it anywhere. Man, the Garfield guy doesn't have these problems ...
Ummm, that Garfield guy has plenty of his own problems. Have you ever read Garfield strips while imagining that Garfield is a cat that can't talk back to Jon? Jon Arbuckle is clinically depressed, not to mention stark raving mad.
http://garfieldminusgarfield.tumblr.com/
Ever seen the fandrawn comic where Garfield, as a regular cat, don't talk at all?
It's bordering between downright (what you said) and cat abuse (the best example is the comic where Garfield is trapped in solidified mud, and Jon smash him to free him. The original comic is funny, the one where Garfield doesn't talk just look as if Jon beat his own cat.)
"Travelling Salesman Problem" Discussion
theyranos wrote:If you're selling stuff on ebay, isn't the traveling salesman problem still O(vertices) since you have to prepare that many boxes for the postman?
If you assume that you prepare one box for each vertex, yes. (Typically, the problem scales with the number of vertices visited, rather than having any notion of how many items are sold).
I think a more direct problem is that the shipping cost will increase as the number of vertices a particular shipping company services increases, making the cost much higher than O(1). Intuitively I feel like shippingandhandling per package should scale with the log of the number of vertices serviced, but that's just my feeling. Then the cost would be O(n log n) to ship one package to each vertex.
(I'm assuming here that there's a unified notion of "cost", which is linearly related to both time and money. The amount of wages you can earn is only slightly superlinear in the amount of time spent, so I think this is reasonable).
 OfficiallyHaphazard
 Age=postcount/60
 Posts: 209
 Joined: Tue Aug 28, 2007 2:56 pm UTC
Re: "Travelling Salesman Problem" Discussion
And to think I took my final on BigO two days ago
this makes it all worth it
this makes it all worth it
"Who are you, how did you get in my house?"  Donald Knuth

 Posts: 37
 Joined: Wed Aug 22, 2007 5:12 pm UTC
 Location: New York City
 Contact:
Re: "Travelling Salesman Problem" Discussion
Someone else has already pointed out that ב is used. I'll point out that you didn't write a shin, you wrote a shin with a dagesh. A regular shin looks like ש, with no dot (dagesh) in it.zinder wrote:Don't forget the Hebrew alphabet. We use that from time to time... though really only א (Aleph) as far as I know. (Do any of the others get used? What does שּ (Shin) stand for?)
I wonder if Israeli mathematicians use Hebrew letters more.
It's still substantially better than n!. That's approximately equal to sqrt(2πn)e^{n log n − n}, as opposed to n² e^{n log 2}.jouva wrote:Jesus, n^{2}2^{n}? Just an increase by 1 sounds nasty as it gets bigger and bigger.
Actually, hmm. If you divide those you get sqrt(2π/n³)e^{n log n − (1 + log 2)n}. Put the square root in an exponent and you get e^{n log n − 1.5 log(n) − (1 + log 2)n + 0.5 ln(2π)}. How fast is that? My quick scribbling indicates it's still superpolynomial, even with the subtractions in the exponent.
Re: "Travelling Salesman Problem" Discussion
photosinensis wrote:As for underused symbols, I nominate 'n̈'. As in "Spın̈al Tap". It's not even in Unicode, which disappoints me greatlyyou've got to merge the unicode for 'n' and the one for the diaeresis.
I second this. Of course, it has a limit: it cannot describe algorithms with an order higher than n̈(n^11).
Re: "Travelling Salesman Problem" Discussion
sorry, i live under and/or have the intelligence of, a rock; please explain the punchline..

 Posts: 28
 Joined: Fri Jan 11, 2008 5:33 am UTC
Re: "Travelling Salesman Problem" Discussion
Kalos wrote:Big O notation, because despite having 26 english letters, 24 greek letters, and the ability to make up symbols, we STILL choose the one letter easiest confused with a zero
what about capitals and lowercase? 52 english letters, 48 greek letters. I agree with you wholeheartedly. If it would be easier to use, say, a t, it ends up being a greek letter or new symbol. If it is extraordinarily important that the symbol doesn't get confused with others, it is either a 0 or an O. Ah, this font actually has a difference! oooh! OOOOH! 0000H!
Re: "Travelling Salesman Problem" Discussion
Ashbash wrote:After all this time, I still don't understand, P, NP, and NPcomplete, except that I know NPcomplete is hard/impossible. Maybe because I still don't get polynomial time? What the hell.
It's actually not that difficult to understand.
First, take a problem. Next, devise an algorithm to solve that problem. That algorithm takes some amount of operations. The amount of operations it takes is dependent upon the size of the problem. If you make the problem bigger (add more numbers, add more points on the salesman's graph), then the number of operations increases by some amount. This is how you derive the bigO value. The big O value describes a scaling factor. O(1) is solvable in constant time, no matter how many inputs. O(N) is solvable in linear time, adding more inputs makes the problem take longer in a direct relation to the number of inputs. O(N^2) is solvable on a squared level, adding more inputs makes it take much longer because it's relative to the square of the number of inputs. That sort of thing.
If the BigO value for a solution to a problem is a polynomial expression, then the problem fits into the set known as "P". These are problems that are solvable in polynomial time.
Now, for every problem, finding the answer is one thing. But once you have the answer, how do you know that it's the correct answer? Sometimes, this is easy, you simply plug the answer in and check that it works. Checking the answer is a problem in itself, isn't it? As such, you can devise an algorithm to take an answer and check that it's correct. If that algorithm for checking the answer has a BigO value which is a polynomial expression, then the problem fits into the set of problems known as "NP". All "P" problems are also in the "NP" set. However, there are some problems that we don't have polynomial time solutions. The Traveling Salesman is one of these. N! is not a polynomial. But, just because we don't *know* a solution in polynomial time doesn't mean that there is not one.
NPComplete is a somewhat trickier concept. NPComplete problems are problems that can be changed into all other NP problems by a transformation of some type. In other words, if instead of thinking of points on a graph and think of numbers or whatever, then the algorithm to solve the problem would work for this other problem. NPComplete problems have solutions that work for *all* problems in NP. The Traveling Salesman is also one of these, you can represent any NP problem as points on a graph in which you need to find the shortest path. It's not always the best way to do it, but it's at least possible.
So, what's the P=NP problem? Well, basically, if P=NP, then that means that all problems in NP have ways to solve them in polynomial time. We may not know how to do that, but it would at least be possible.
Now, remember, NPComplete solutions can be turned into solutions for all other NP problems. So, logically, if somebody was to solve an NPComplete problem with a Polynomial solution, they'd prove that P=NP. They'd also make a cool million bucks from the Clay Mathematics Institute, and solve one of the most difficult problems in mathematics.
In other words, we think that P != NP, but we have no actual proof of that. Finding a counterexample by solving an NPComplete problem in P time would, of course, prove it the other way, but proving that P != NP is ridiculously difficult, maybe impossible.
Ashbash wrote:Is big O notation about finding the solution or the optimum time it takes to find a solution? And what, in seconds? Gah this is confusing.
BigO notation is about finding how long a solution to a problem takes in relation to the size of the problem set. It doesn't give any sort of "real" time measurement, just a relative time measurement. You can say with confidence that a O(N) solution will take less time than an O(N^2) solution for the same problem, and that an O(log N) solution will be faster than them both. But that's all, it's only relative to each other and to the same problem.
Re: "Travelling Salesman Problem" Discussion
This would've been funnier if the ebay guy had been the classhole.
Re: "Travelling Salesman Problem" Discussion
Otto wrote:You can say with confidence that a O(N) solution will take less time than an O(N^2) solution for the same problem, and that an O(log N) solution will be faster than them both.
Although you can say it with confidence, it's not necessarily always true. A O(N) solution can be slower than an O(N^2) solution for small enough vales of N. It's not likely but it happens. For a real world example, it's often faster to do an insertion sort if you have less than 10 or so elements in a list than to do a merge sort. For a contrived but fairly obvious example, consider an insertion sort vs. a merge sort that, before each merge operation, sleeps for 5 seconds for no apparent reason. Until you get to sorting fairly large lists, the insertion sort will be faster. All that having a "faster" BigO algorithm means is that after a certain problem size (which could be the whole problem space, or start fairly late), the "faster" algorithm really will be faster, always, and will keep gaining as the problem size grows. But it's possible that the "slower" algorithm is faster for rather a lot of small problem sizes. So if you know about what your problem size is going to be before hand, and your "faster" algorithm is for some reason insanely complicated, it's worth looking into a "slower" algorithm, as it might end up faster in real life. Not likely, but stranger things have hapenned.
Sorry for the pedantry, just thought it was an interesting tidbit to point out.
Re: "Travelling Salesman Problem" Discussion
As for the best cutting plane ILP methods:
ILP is generally solved with a Branch and Bound technique, using normal LP relaxation to find the bounds. Branch and Bound has worst case 2^n time (or possibly infinite by exploring the entire possibility graph, which depending on how your problem is formulated, could be Rspace), but in practice will be much faster than that. Also, the way that branch and bound works, solutions are saved as you go so if you run it for some large period of time, get tired of waiting and stop, it will end up with the best solution you've got so far. This means letting it run a couple days will often get you a very close solution, almost certainly closer than any approximation algorithms (although without the guarantee).
ILP is generally solved with a Branch and Bound technique, using normal LP relaxation to find the bounds. Branch and Bound has worst case 2^n time (or possibly infinite by exploring the entire possibility graph, which depending on how your problem is formulated, could be Rspace), but in practice will be much faster than that. Also, the way that branch and bound works, solutions are saved as you go so if you run it for some large period of time, get tired of waiting and stop, it will end up with the best solution you've got so far. This means letting it run a couple days will often get you a very close solution, almost certainly closer than any approximation algorithms (although without the guarantee).
Re: "Travelling Salesman Problem" Discussion
noheat wrote:sorry, i live under and/or have the intelligence of, a rock; please explain the punchline..
You have to be familiar with Computer Science to get this. Not super familiar, but familiar.
The Traveling Salesman Problem is a very famous problem in computer science. Basically, imagine you're a traveling salesman, and you've got a list of cities to visit. You need to find the shortest route that visits every city. It turns out there's no really good way to come up with the shortest route other than basically trying every single route, and there are tons of possibilities. There are fairly fast ways of getting a pretty good answer, but no good way of getting the definitive answer. And there are slightly faster ways of getting the definitive answer, but there's no way that isn't categorically terrible.
The first two panels discuss different approaches to the problem, and how much time they take: both are pretty terrible. In the punchline, the guy neatly sidesteps the problem. Rather than finding the shortest route between all the cities, he just stays home and sells thing on eBay.
Re: "Travelling Salesman Problem" Discussion
*hangs head in shame*
I just thought I was a geek until I read this.... It took me reading most of the first page of posts and clicking on almost all of the side links to get it....
*ashamed*
I just thought I was a geek until I read this.... It took me reading most of the first page of posts and clicking on almost all of the side links to get it....
*ashamed*
Re: "Travelling Salesman Problem" Discussion
Horsman wrote:As for the best cutting plane ILP methods:
ILP is generally solved with a Branch and Bound technique, using normal LP relaxation to find the bounds. Branch and Bound has worst case 2^n time (or possibly infinite by exploring the entire possibility graph, which depending on how your problem is formulated, could be Rspace), but in practice will be much faster than that. Also, the way that branch and bound works, solutions are saved as you go so if you run it for some large period of time, get tired of waiting and stop, it will end up with the best solution you've got so far. This means letting it run a couple days will often get you a very close solution, almost certainly closer than any approximation algorithms (although without the guarantee).
I should clarify that ILP mean "Integer Linear Programming" (or "Integer Programming" to technical students) and LP means Linear Programming.TSP is ILP since Linear programming solves for continuous variables and the TSP is a discrete problem (you can't take half a route). Also, to the above post, it's important to note that TSP also requires not visiting the same place twice (if you could you could do a Euler Tour, O(n^2) solution. If any of you are interested in solving semi large TSP's, say, up to about 1000 nodes, it's quite possible in most cases using the GNU Linear Programming Kit (glpk). Post back here if you need help or the provided sample for TSP isn't fast enough (there are better constraints).
Also, I've seen some rather good genetic algorithms.
Re: "Travelling Salesman Problem" Discussion
Because none of the Greek capital letters could ever be confused with Latin ones.MarioMaster151 wrote:what about capitals and lowercase? 52 english letters, 48 greek letters.
This is a placeholder until I think of something more creative to put here.

 Posts: 52
 Joined: Mon Jan 08, 2007 10:03 pm UTC
Re: "Travelling Salesman Problem" Discussion
Robin S wrote:Because none of the Greek capital letters could ever be confused with Latin ones.
Hell, even the latin letters are internally confusing  I don't even bother trying to differentiate k and K when I'm writing. And then lowercase l (L) looks just like 1 unless you stick the serif and/or base on there.
That said, if you add latin cursive to the mix you can easily exceed 100 distinguishable letters total.

 Posts: 37
 Joined: Wed Aug 22, 2007 5:12 pm UTC
 Location: New York City
 Contact:
Re: "Travelling Salesman Problem" Discussion
Your.Master wrote:And then lowercase l (L) looks just like 1 unless you stick the serif and/or base on there.
That's why we have the magic of \ell.
Re: "Travelling Salesman Problem" Discussion
Peaker wrote:there are usable polynomial algorithms that under some reasonable assumptions (Triangle Inequality), approximate the TSP solution (only 1.5 times worse than the optimal solution, at worst).
Under reasonable assumptions about the problem the guy in the comic is solving (the graph is the U.S. and therefore euclidean distance holds), there exists a PolynomialTime Approximation Scheme, discovered independently by two different people at the same time. This means you can get as close to the optimal solution as you are willing to spend the time to get. It's not an easy algorithm though.
Horsman wrote:Also, I've seen some rather good genetic algorithms.
A local beam search is always superior to a genetic algorithm.
Re: "Travelling Salesman Problem" Discussion
quintopia wrote:A local beam search is always superior to a genetic algorithm.
I'm interested to look this up (Does beam search outperform ILP?). Thanks!
Edit: looks like another pruning technique.
Re: "Travelling Salesman Problem" Discussion
i feel like i am slipping... when i looked at the comic last night i didn't really get. the big "O" especially threw me off fortunately upon looking at it again this morning during my physics class i got it and was quite amused. of course i could always blame it on my primarily engineering background with only a secondary knowledge of programing. meh i guess it means its time for me to find and extra class in computer programing to take.
They who can give up essential liberty to obtain a little temporary safety, deserve neither liberty nor safety.  Benjamin Franklin

 Posts: 37
 Joined: Wed Aug 22, 2007 5:12 pm UTC
 Location: New York City
 Contact:
Re: "Travelling Salesman Problem" Discussion
quintopia wrote:Under reasonable assumptions about the problem the guy in the comic is solving (the graph is the U.S. and therefore euclidean distance holds)
Euclidean distance doesn't hold in the U.S. if you're using roads. The relevant metric in that case is vastly more complicated. It also doesn't hold if you're going by air: the Euclidean metric becomes a poor approximation at those scales, and you need to use an elliptic metric.
Plus, as someone above pointed out, in practice there are economical concerns. You likely don't have your own private airplane, and if you do you can't afford to build a runway at every destination. Therefore you often don't want to go "directly" to your destination at all, if you want the shortest transit time. You may want to go to the nearest major airport and then drive, for instance, or take a flight that makes multiple stops that take you out of your way.
Re: "Travelling Salesman Problem" Discussion
i was just looking at the comic again and i realized how ridiculously terrible the second algorithm must be if it is (n^2)(2^n). Even if you have a set of 1 location it could still take 2 tries... one wonders what type of algorithm could produce such results and what you get for the other potential solution. Kinda like having a multiple choice question between a, b, and c and then choosing F
They who can give up essential liberty to obtain a little temporary safety, deserve neither liberty nor safety.  Benjamin Franklin

 Posts: 3
 Joined: Sat Dec 29, 2007 7:33 pm UTC
Re: "Travelling Salesman Problem" Discussion
pyroman wrote:i was just looking at the comic again and i realized how ridiculously terrible the second algorithm must be if it is (n^2)(2^n). Even if you have a set of 1 location it could still take 2 tries... one wonders what type of algorithm could produce such results and what you get for the other potential solution. Kinda like having a multiple choice question between a, b, and c and then choosing F
Actually not, O notation strips things down to the fundamental growth rate, it does not take into consideration constant factors. It's possible that an O(n^2*2^n) algorithm could actually take much less than 1 tries for n = 1 or any arbitrary number of tries more than that. What matters is that the scaling between, say, n = 10 and n = 20 matches the scaling of n^2*2^n over the same range.
 Lazy Tommy
 Posts: 89
 Joined: Sat Dec 15, 2007 3:55 pm UTC
 Location: New Jersey, USA
Re: "Travelling Salesman Problem" Discussion
tgape wrote:Damnit Randal! You just *had* to go and solve the Traveling Salesman Problem! Now all encryption is worthless, because it all depends on NPcomplete problems being *hard*.
Not to worry. Even if P = NP, there will still be problems with wildly impractical complexities out there... For example, in college I once had to write some code that used an iterative linear equation solver to numerically solve a fairly simplelooking discretized partial differential equation. In terms of result accuracy, it had O(n^9) memory complexity and O(n^11) time complexity  in other words, to get 1 extra digit of precision, you needed one billion times more memory and 100 billion times more patience. Totally impractical, yet clearly P.

 Posts: 9
 Joined: Fri Mar 21, 2008 11:17 pm UTC
Re: "Travelling Salesman Problem" Discussion
tgape wrote:The problem I have with rocketsocks (admittedly academically 100% correct) explanation is that, IMHO, O(2^n) is very deterministic  it's deterministically timeconsuming. As such, I tend to think of NP as meaning Nonpolynomial aka Exponential.
Registered to post and clear this up.
"Nondeterministic" refers to the kind of computer you're using, not the amount of time it takes for that computer to solve the problem. NP stands for nondeterministicpolynomial, but that is itself an abbreviationfor polynomial time on a nondeterministic Turing machine. An NTM is a computer that's sort of infinitely parallelin a multithreaded algorithm, you can increase the number of threads without decreasing the amount of processing power devoted to each one individually. To the (so far, very limited) extent that quantum computers work at all, they're nondeterministic (well, that's only true if either the Copenhagen or multiverse interpretations of quantum theory are correct).
"Can be solved in polynomial time on a nondeterministic Turing machine" and "Possible solution can be verified in polynomial time on a standard Turing machine" turn out to be equivalent because if you have a nondeterministic machine, you can just spawn a new thread to try verifying every possible solution. Even if the verification process can't itself be optimized for a nondeterministic machine, it'll still run in polynomial time, so you can just wait that long and see which thread returns "true."
Furthermore, there are plenty of problems that are even harder than those in NP. Playing Go on an n x n board is certainly a "nonpolynomial" problem, but is not an NP problem.
Re: "Travelling Salesman Problem" Discussion
Simetrical wrote:That's why we have the magic of ℓ.
Fixed.
Return to “Individual XKCD Comic Threads”
Who is online
Users browsing this forum: No registered users and 106 guests