Bonifaci, Vincenzo; Mehlhorn, Kurt; Varma, Girish Physarum can compute shortest paths. (English) Zbl 1411.92332 J. Theor. Biol. 309, 121-133 (2012). Summary: Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by A. Tero et al. [“A mathematical model for adaptive transport network in path finding by true slime mold”, ibid. 244, No. 4, 553–564 (2007; doi:10.1016/j.jtbi.2006.07.015)] to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources \(s_0\) and \(s_1\). We prove that, under this model, the mass of the mold will eventually converge to the shortest \(s_0-s_1\) 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 Tero et al. and can be seen as an example of a “natural algorithm”, that is, an algorithm developed by evolution over millions of years. Cited in 2 ReviewsCited in 14 Documents MSC: 92D50 Animal behavior 05C85 Graph algorithms (graph-theoretic aspects) Keywords:slime mold; natural algorithm; natural adaptive networks PDFBibTeX XMLCite \textit{V. Bonifaci} et al., J. Theor. Biol. 309, 121--133 (2012; Zbl 1411.92332) Full Text: DOI References: [1] Adamatzky, A., Physarum Machines: Computers from Slime Mold (2010), World Scientific: World Scientific Singapore [2] Baldauf, S. L.; Doolittle, W. F., Origin and evolution of the slime molds (Mycetozoa), Proc. Natl. Acad. Sci. USA, 94, 12007-12012 (1997) [3] Bollobás, B., Modern Graph Theory (1998), Springer: Springer New York · Zbl 0902.05016 [4] Bonifaci, V., Mehlhorn, K., Varma, G., 2011. Physarum can compute shortest paths, arXiv:1106.0423v3; Bonifaci, V., Mehlhorn, K., Varma, G., 2011. Physarum can compute shortest paths, arXiv:1106.0423v3 [5] Chazelle, B., Natural algorithms, (Mathieu, C., Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (2009), SIAM: SIAM Philadelphia, PA) · Zbl 1423.92246 [6] Clarke, F.; Ledyaev, Y.; Stern, R.; Wolenski, P., Nonsmooth Analysis and Control Theory (1998), Springer: Springer New York · Zbl 1047.49500 [7] Hirsch, M. W.; Smale, S., Differential Equations, Dynamical Systems, and Linear Algebra (1974), Academic Press: Academic Press San Diego · Zbl 0309.34001 [8] Ito, K., Johansson, A., Nakagaki, T., Tero, A., 2011. Convergence properties for the Physarum solver, arXiv:1101.5249v1; Ito, K., Johansson, A., Nakagaki, T., Tero, A., 2011. Convergence properties for the Physarum solver, arXiv:1101.5249v1 [9] Kirby, B. J., Micro- and Nanoscale Fluid Mechanics: Transport in Microfluidic Devices (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1283.76002 [10] Mäkelä, M. M.; Neittanmäki, P., Nonsmooth Optimization (1992), World Scientific: World Scientific Singapore [11] Miyaji, T.; Ohnishi, I., Mathematical analysis to an adaptive network of the plasmodium system, Hokkaido Math. J., 36, 445-465 (2007) · Zbl 1136.34045 [12] Miyaji, T.; Ohnishi, I., Physarum can solve the shortest path problem on Riemannian surface mathematically rigourously, Intern. J. Pure Appl. Math., 47, 353-369 (2008) · Zbl 1235.92004 [13] Nakagaki, T.; Tero, A.; Kobayashi, R.; Ohnishi, I.; Miyaji, T., Computational ability of cells based on cell dynamics and adaptability, New Gener. Comput., 27, 57-81 (2009) · Zbl 1192.68653 [14] Nakagaki, T.; Yamada, H.; Tóth, A., Maze-solving by an amoeboid organism, Nature, 407, 470 (2000) [15] Tero, A.; Kobayashi, R.; Nakagaki, T., A mathematical model for adaptive transport network in path finding by true slime mold, J. Theor. Biol., 244, 553-564 (2007) · Zbl 1450.92052 [16] Tero, A.; Takagi, S.; Saigusa, T.; Ito, K.; Bebber, D.; Fricker, M.; Yumiki, K.; Kobayashi, R.; Nakagaki, T., Rules for biologically inspired adaptive network design, Science, 327, 439-442 (2010) · Zbl 1226.90021 [17] \( \langle\) http://www.youtube.com/watch?v=tLO2n3YMcXw&t=4m43s \(\rangle \); \( \langle\) http://www.youtube.com/watch?v=tLO2n3YMcXw&t=4m43s \(\rangle \) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.