5 ms·
Using A Slime-Mold To Calculate Minimum Spanning Trees
- lucian1900 14y agoVery interesting. I don't think slime-molds are fast enough to build a useful NP-oracle, though.
- pmiller2 14y agoMST is polynomial, so you can't use it as an NP oracle, anyway.
- hythloday 14y agoAnd the fact that the slime molds didn't create the same layout every time implies they don't provide an optimum answer.
- ganley 14y agoNot necessarily true. There could be multiple, equal-valued optima.
- pmiller2 14y agoExactly. Consider the case of all equal weights. In that case, every spanning tree is a MST. For the extreme cases (labeled complete graph, and a tree) of order n, those numbers are $n^{n-2}$ and 1, respectively, so the answer can be far from unique.
- davidw 14y agoSo what kind of algorithm does the slime mold use?
- tocomment 14y agoAnd 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_Ab 14y agoMy naive guess is hill climbing based on chemical gradients. I have a strong hunch that large networks settle at local optimums.
- ghoul2 14y agoI'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 14y agoRelated: http://news.ycombinator.com/item?id=1071093 http://news.ycombinator.com/item?id=1071093 http://news.ycombinator.com/item?id=1071533 http://news.ycombinator.com/item?id=1071533 http://news.ycombinator.com/item?id=1071568 http://news.ycombinator.com/item?id=1071568 http://news.ycombinator.com/item?id=1072876 http://news.ycombinator.com/item?id=1072876 http://news.ycombinator.com/item?id=3406446 http://news.ycombinator.com/item?id=3406446 http://news.ycombinator.com/item?id=3477746 http://news.ycombinator.com/item?id=3477746 http://news.ycombinator.com/item?id=3728933 http://news.ycombinator.com/item?id=3728933 http://news.ycombinator.com/item?id=3757527 http://news.ycombinator.com/item?id=3757527 http://news.ycombinator.com/item?id=3853748 http://news.ycombinator.com/item?id=3853748 Very few have comments, but the stories are varied.
- scott_s 14y agoI'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-highway.html http://phys.org/news/2012-03-slime-mold-mimics-canadian-high...
- tocomment 14y agoAnother 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 14y agoArxiv 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 http://arxiv.org/pdf/1203.2851.pdf Take a look at page 4.
- majmun 14y agoNext step : connect slime-mold to virtual reality , and expose API for it.
- deleted 14y ago[deleted]
- mjn 14y agoIf 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 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/ http://slimoco.ning.com/
- rfreytag 14y agoSoap films approximate minimum spanning trees. See: http://csunplugged.org/sites/default/files/activity_pdfs_full/unplugged-15-steiner_trees_0.pdf 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 https://en.wikipedia.org/wiki/Steiner_tree_problem EDIT: replaced 'find' and 'solve' with 'approximate.' EDIT: added '(NP-complete)'.
- VMG 14y agoAlso featured in this video: http://www.youtube.com/watch?v=dAyDi1aa40E http://www.youtube.com/watch?v=dAyDi1aa40E
- jerf 14y agoOnly for sufficiently small definitions of "solve": http://arxiv.org/pdf/quant-ph/0502072v2 http://arxiv.org/pdf/quant-ph/0502072v2 Definitions which turn out to be very small indeed.
- Dn_Ab 14y agoHarder 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 14y agoMy 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.