Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds
verfasst von : Luca Becchetti, Vincenzo Bonifaci, Michael Dirnberger, Andreas Karrenbauer, Kurt Mehlhorn
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Physarum polycephalum
is a slime mold that is apparently able to solve shortest path problems. A mathematical model for the slime’s behavior in the form of a coupled system of differential equations was proposed by Tero, Kobayashi and Nakagaki [TKN07]. We prove that a discretization of the model (Euler integration) computes a (1 +
ε
)-approximation of the shortest path in
O
(
m
L
(log
n
+ log
L
)/
ε
3
) iterations, with arithmetic on numbers of
O
(log(
nL
/
ε
)) bits; here,
n
and
m
are the number of nodes and edges of the graph, respectively, and
L
is the largest length of an edge. We also obtain two results for a directed Physarum model proposed by Ito et al. [IJNT11]: convergence in the general, nonuniform case and convergence and complexity bounds for the discretization of the uniform case.