> <i>I don’t know if this means I should not trust American Scientist in areas that are not my specialty. On something I know a bit about, the magazine has failed miserably.</i><p>I forget the term for this - when we see media cover something we know about badly, but continue to assume that they cover other topics that we're relatively ignorant about fairly and correctly.
The title makes it sounds much worse than it actually is. I mean, this isn't <i>that</i> bad:<p>> But what about going to 100 different cities? A computer would have to check 100x99x98x….x2x1 possible routes.<p>Yes, the sentence should have included "In case of a brute-force search", but still it conveys the basic idea of TSP and why it gets exponentially harder as N increases.
If you are offended by a pop science magazine's over simplification of a topic that resides in a field you have some specialty understanding of, you clearly haven't been reading pop-sci magazines for very long. You have all the right in the world to be angry when this happens in a journal article, but you are reading American Scientist, not SODA.
Bill Cook, mentioned in this post, has written an excellent and entertaining book on the TSP that is accessible to non-experts: <a href="http://www.amazon.com/Pursuit-Traveling-Salesman-Mathematics-Computation/dp/0691152705" rel="nofollow">http://www.amazon.com/Pursuit-Traveling-Salesman-Mathematics...</a><p>If you're not interested in reading an entire book on the topic, Cook's webpage provides a summary and includes several examples: <a href="http://www.math.uwaterloo.ca/tsp/" rel="nofollow">http://www.math.uwaterloo.ca/tsp/</a><p>Finally, here's a simple version of the TSP showing route optimization in San Francisco using local businesses: <a href="https://forio.com/app/showcase/route-optimizer/" rel="nofollow">https://forio.com/app/showcase/route-optimizer/</a>
It's weird, I remember reading a very informative article about SAT from American Scientist when I was an undergrad:<p><a href="http://sjcomp.com/files/compsci9703.html" rel="nofollow">http://sjcomp.com/files/compsci9703.html</a><p>I will have to reread it to see if it still makes sense.
As an aside, an algorithm based on ant pheromones is a clever way to solve the traveling salesman problem.<p><a href="http://people.idsia.ch/~luca/acs-bio97.pdf" rel="nofollow">http://people.idsia.ch/~luca/acs-bio97.pdf</a>
I'm confused by this post. I was under the impression NP-complete problems could not be solved efficiently, but the author is saying that TSP, the most well known NP-complete problem, <i>can</i> be solved practically. I read what he wrote but did not understand what he was saying. Why is TSP famously hard if it's actually tractable in practice?
That Hilbert Curve solution is really handy to know about. If you were writing a game where the player competes with an AI at traveling salesman (Pacman without the ghosts race), a fast 75% optimal algorithm sounds perfect.<p>I think you can do the Hilbert Curve in n log n time by loading all the cities into a quad tree and traversing it in a Hilberty order. Is that the fastest way?
This magazine (and its similarly-named rival) sometimes calls to mind Nelson Muntz's comment: "I can think of at least two things wrong with that title."
I remember the same feeling, a long time ago. I would read the Dutch 'NRC' science page, and be annoyed that they really did not understand the Schrödinger cat problem. Of course, since then I strayed away from my physics career (entering IT with a PhD in physics), and now I can read those same science pages and think, wow they really know their stuff....
Cixin Liu's The Dark Forest has the alien enemy ship solve the traveling salesman problem for a moderate n in real time as a way of demonstrating the aliens' superior level of science. That must upset the original poster almost as much...
How does one know one has an optimal solution for the travelling salesman problem?<p>Any experts out there that can explain this, or point to some accessible literature on this?
"I will get my favorite spaghetti meal served on my birthday."<p>In an otherwise run-of-the-mill rant, this struck me as a truly weird, passive, and ungrammatical (to my ear) assertion. The lack of any agent makes me wonder if he's insisted on his parents and then various friends or significant others over the years to serve him this meal. Or does he hire someone to perform this task for him? The lack of the mention of "cooking" and the phrasing "spaghetti meal" make me envision dumping a cold can of Chef Boy-Ar-Dee spaghetti out in a bowl. Just an odd, unrelatable insistence. Weird.
Yes! One politic is found to be corrupt, all politicians must be corrupt! One businessman implemented a fraud, down with captalism! One autistic child took several vaccine before being diagnosed. VAccine are the culprit!<p>I see, read, and hear these kind of argument all the times and they sadden me. I'm sure Snake-oil salesman, con artist and populist politicans salivates when reading how easily people dismiss things so easily.<p>Is the American Scientist article entirely wrong? No. Is even just that sideboard entirely off-track? No. It's probably a case of vulgarization gone too far.<p>But hey, baby, water, bath, plumbing, out the window you go.