Using A Slime-Mold To Calculate Minimum Spanning Trees

https://www.nytimes.com/2012/05/13/opinion/sunday/the-wisdom-of-slime.html?_r=1

by rfreytag • 14 years ago

68 20 14 years ago

nytimes.com

lucian1900• 14 years ago

Very interesting. I don't think slime-molds are fast enough to build a useful NP-oracle, though.

pmiller22• 14 years ago

MST is polynomial, so you can't use it as an NP oracle, anyway.

hythloday• 14 years ago

And the fact that the slime molds didn't create the same layout every time implies they don't provide an optimum answer.

davidw• 14 years ago

So what kind of algorithm does the slime mold use?

tocomment2• 14 years ago

And what is the time complexity of its algorithm? Seems like you could measure it by using larger and larger problems and then determining whether the time increases exponentially.

That, to me seems like the most interesting problem. Kickstarter project anyone?

Dn_Ab2• 14 years ago

My naive guess is hill climbing based on chemical gradients. I have a strong hunch that large networks settle at local optimums.

ghoul2• 14 years ago

I'd say more likely its equivalent to particle filters. Mold probably shoots spores all around the petri dish, and the spores that have better access to nutrients grow more, thus putting out larger proportion of spores in the next generation. A few generations later, all organisms that are either directly next to the nutrients, or next to another organism which has good access to nutrients survive.

ColinWright• 14 years ago

http://news.ycombinator.com/item?id=1071093

http://news.ycombinator.com/item?id=1071533

http://news.ycombinator.com/item?id=1071568

http://news.ycombinator.com/item?id=1072876

http://news.ycombinator.com/item?id=3406446

http://news.ycombinator.com/item?id=3477746

http://news.ycombinator.com/item?id=3728933

http://news.ycombinator.com/item?id=3757527

http://news.ycombinator.com/item?id=3853748

Very few have comments, but the stories are varied.

scott_s• 14 years ago

I'm calling out this one because it has video, which I think people who read the NY Times article would like to see: http://phys.org/news/2012-03-slime-mold-mimics-canadian-high...

tocomment2• 14 years ago

Another one of those articles where they really should include a picture of the network the mold came up with. A picture really would say 1000's of words in this case; they spend the whole article describing what the mold did :-(

royhodgman• 14 years ago

Arxiv has a paper by Andrew Adamatzky (one of the authors of the nytimes article) called "Are motorways rational from slime mould’s point of view?", from 13 Mar 2012, which has pictures:

http://arxiv.org/pdf/1203.2851.pdf

Take a look at page 4.

majmun• 14 years ago

Next step : connect slime-mold to virtual reality , and expose API for it.

mjn• 14 years ago

If we view slime molds as a sort of computing machine, which responds differently to different inputs, an intriguing angle is to use it for generative art, the way people use other computing formalisms like context-free grammars (http://www.contextfreeart.org), cellular automata, and other things.

The tricky thing is that slime mold tends to either die or gunk everything up if you aren't careful, but there are some artists "collaborating" with it in producing paintings, which makes for interesting outcomes sometimes because the mold seems to carry pigments around, and responds differently to different pigments and preparations of surfaces: http://slimoco.ning.com/

rfreytag• 14 years ago

Soap films approximate minimum spanning trees. See: http://csunplugged.org/sites/default/files/activity_pdfs_ful... (see page 7 [aka, page 157]).

Actually, these films approximate Steiner Trees; which is harder (NP-complete): https://en.wikipedia.org/wiki/Steiner_tree_problem

EDIT: replaced 'find' and 'solve' with 'approximate.' EDIT: added '(NP-complete)'.

VMG• 14 years ago

Also featured in this video: http://www.youtube.com/watch?v=dAyDi1aa40E

jerf• 14 years ago

Only for sufficiently small definitions of "solve": http://arxiv.org/pdf/quant-ph/0502072v2

Definitions which turn out to be very small indeed.

Dn_Ab2• 14 years ago

Harder is an understatement =)

The bubbles don't solve Steiner Trees per se, they just give decent approximations. They are susceptible to local minimums. Scott Aaronson has given demonstrations against these claims.

danpalmer• 14 years ago

My Tutor at university (Computer Science) is one of the leading experts on using Slime-Molds in computation. He makes robots controlled by them. Very interesting stuff I think, although biological computing isn't normally my area of interest.

Using A Slime-Mold To Calculate Minimum Spanning Trees

Related Stories