I've just read that bees out-perform our best traveling salesman algorithms, and it's not entirely clear why. I think the abstraction of the problem doesn't directly translate into physical space all the time, and that could skew the results. A computer needs to travel the graph in a specified manner, only following connections that are given between nodes. How do you model, for a bee, that flower A can be reached from flower B, but never directly from flower C? No matter how you lay them out, you can never exclude a particular route between two points without completely constraining the results.
As observed, however, this indicates one of two things: tiny clusters of neurons are more powerful computers than anything we have ever built, or we have drastically misunderstood this problem. Given how often nature outsmarts us, I'm going with option 2, but either way is a pretty big failure on the part of us humans. Either we can't build a computer as powerful as a few bee neurons or decades of programming has never yielded the shortcut.
Mokalus of Borg
PS - Apparently I have trouble explaining why this is a difficult problem.
PPS - If it wasn't difficult, quite frankly, it wouldn't be a problem at all.