Physarum can compute shortest paths
Copyright policy )Physarum can compute shortest paths
Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0 - s1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by the biologists and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years.
Accepted in SODA 2012
FOS: Computer and information sciences, Movement, Computer Science - Emerging Technologies, FOS: Physical sciences, Systems and Control (eess.SY), Dynamical Systems (math.DS), Electrical Engineering and Systems Science - Systems and Control, Models, Biological, Computational Engineering, Finance, and Science (cs.CE), Physarum polycephalum, Computer Science - Data Structures and Algorithms, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Data Structures and Algorithms (cs.DS), Physics - Biological Physics, Mathematics - Dynamical Systems, Computer Science - Computational Engineering, Finance, and Science, Mathematics - Optimization and Control, Physarum polycephalum, dynamical system, shortest path, Emerging Technologies (cs.ET), Optimization and Control (math.OC), Biological Physics (physics.bio-ph), Natural adaptive networks; Natural algorithm; Slime mold; Models, Biological; Movement; Physarum polycephalum
FOS: Computer and information sciences, Movement, Computer Science - Emerging Technologies, FOS: Physical sciences, Systems and Control (eess.SY), Dynamical Systems (math.DS), Electrical Engineering and Systems Science - Systems and Control, Models, Biological, Computational Engineering, Finance, and Science (cs.CE), Physarum polycephalum, Computer Science - Data Structures and Algorithms, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Data Structures and Algorithms (cs.DS), Physics - Biological Physics, Mathematics - Dynamical Systems, Computer Science - Computational Engineering, Finance, and Science, Mathematics - Optimization and Control, Physarum polycephalum, dynamical system, shortest path, Emerging Technologies (cs.ET), Optimization and Control (math.OC), Biological Physics (physics.bio-ph), Natural adaptive networks; Natural algorithm; Slime mold; Models, Biological; Movement; Physarum polycephalum
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).108 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 1% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!