Quantcast

Maximum PC

It is currently Fri Apr 18, 2014 10:56 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Bees solve NP-Hard Travelling Salesman Problem
PostPosted: Wed Oct 27, 2010 3:07 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24218
Location: Granite Heaven
That's right .. we've been outsmarted by bees.

Linkage

Apologies for the quality of the 'reporting'. The author of that article claims that bees are smart than a computer because a computer can't solve this problem. He seems to be having trouble putting his cart and his horse in the correct order.

Another link

I suppose that when the Communication Officer for the university that published the research makes the same mistake, you can't blame the reporter.


Top
  Profile  
 
 Post subject: Re: Bees solve NP-Hard Travelling Salesman Problem
PostPosted: Thu Oct 28, 2010 8:10 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24218
Location: Granite Heaven
Dwood15 sent me the following quote from the comments of a similar article on Gizmodo. It makes some excellent points and further demonstrates the failing of the media's 'explanation' of this interesting discovery:

Quote:
Time for the usual corrections to a wildly misleading story (not really Giz's fault, but PopSci- you're earning that "Pop").

There is absolutely nothing in the university press release (the paper isn't out yet) that says that the bees solved this problem in any way faster or more efficiently than a computer. All they really said is that bees solved a small example of the Travelling Salesman problem. Period.

They say that bees solved the Traveling Salesman problem, which "can" keep a supercomputer busy for days. That is one of the most misleading statements I've read for a while. The traveling salesman problem is a general class of problems. There are an infinite number of examples of that problem. The version that the bees solved is not one that would take a supercomputer days; a computer could solve it in a tiny fraction of the time the bees could.

The reason this problem is important is that NP-hard problems *scale* at a worse-than-polynomial slowdown according to any known algorithm. A version of the problem with just a few cities, like the bees dealt with, can be solved very quickly by a computer, but as the number of cities and routes grows, the problem rapidly becomes infeasible to solve- it doesn't take that many cities before no known computer could solve it in the lifetime of the universe.

The versions of the problem that take a supercomputer days to solve, are much bigger examples that the bees would never solve.

Now, if they had shown by plotting the slowdown in the bee's algorithm, which is unknown, that the algorithm scales at a polynomial rate, then they would deserve a Nobel Prize, Field Medal, and Turing Award all at the same time, because knowing whether a polynomial-time solution can even exist to an NP-hard problem is one of the very most important open questions in science. But they didn't.


Top
  Profile  
 
 Post subject: Re: Bees solve NP-Hard Travelling Salesman Problem
PostPosted: Mon Nov 01, 2010 1:41 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
This first article is really bad. Clearly, the people who wrote the article have no idea WTF they're talking about in it. There is just so much ignorance of computation that I wouldn't know where to begin criticizing it.

Perhaps, they could spare a few bees? =)

Quote:
Earlier this year, researchers showed that bees recognize individual faces because they can make out the relative patterns that make up a face. The new research further suggests bees are highly sophisticated problem solvers, and that better understanding of their brains could improve our understanding of network problems like traffic flows, supply chains and epidemiology.

Those "busy bees" seem to be quite the resourceful thinkers. I need to send Ray Kurzweil a letter; The singularity is very near -- I can hear it buzzing next door!


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group