Shortest Path Solvers. From Software to Wetware

✍ Scribed by Andrew Adamatzky

• Publisher: Springer International Publishing
• Year: 2018
• Tongue: English
• Leaves: 442
• Series: Emergence, Complexity and Computation 32
• Edition: 1st ed.
• Category: Library

✦ Synopsis

This book offers advanced parallel and distributed algorithms and experimental laboratory prototypes of unconventional shortest path solvers. In addition, it presents novel and unique algorithms of solving shortest problems in massively parallel cellular automaton machines. The shortest path problem is a fundamental and classical problem in graph theory and computer science and is frequently applied in the contexts of transport and logistics, telecommunication networks, virtual reality and gaming, geometry, and social networks analysis. Software implementations include distance-vector algorithms for distributed path computation in dynamics networks, parallel solutions of the constrained shortest path problem, and application of the shortest path solutions in gathering robotic swarms. Massively parallel algorithms utilise cellular automata, where a shortest path is computed either via matrix multiplication in automaton arrays, or via the representation of data graphs in automaton lattices and using the propagation of wave-like patterns. Unconventional shortest path solvers are presented in computer models of foraging behaviour and protoplasmic network optimisation by the slime mould Physarum polycephalum and fluidic devices, while experimental laboratory prototypes of path solvers using chemical media, flows and droplets, and electrical current are also highlighted. The book will be a pleasure to explore for readers from all walks of life, from undergraduate students to university professors, from mathematicians, computers scientists and engineers to chemists and biologists.

✦ Table of Contents

Front Matter ....Pages i-viii
A Parallel Algorithm for the Constrained Shortest Path Problem on Lattice Graphs (Ivan Matic)....Pages 1-26
Gathering a Swarm of Robots Through Shortest Paths (Serafino Cicerone, Gabriele Di Stefano, Alfredo Navarra)....Pages 27-72
The MinSum-MinHop and the MaxMin-MinHop Bicriteria Path Problems (Marta Pascoal)....Pages 73-97
Distance-Vector Algorithms for Distributed Shortest Paths Computation in Dynamic Networks (Gianlorenzo D’Angelo, Mattia D’Emidio, Daniele Frigioni)....Pages 99-143
Influenza Virus Algorithm for Multiobjective Energy Reduction Open Vehicle Routing Problem (Iraklis-Dimitrios Psychas, Eleni Delimpasi, Magdalene Marinaki, Yannis Marinakis)....Pages 145-161
Practical Algorithms for the All-Pairs Shortest Path Problem (Andrej Brodnik, Marko Grgurovič)....Pages 163-180
Computing Shortest Paths with Cellular Automata (Selim G. Akl)....Pages 181-198
Cellular Automata Applications in Shortest Path Problem (Michail-Antisthenis I. Tsompanas, Nikolaos I. Dourvas, Konstantinos Ioannidis, Georgios Ch. Sirakoulis, Rolf Hoffmann, Andrew Adamatzky)....Pages 199-237
Checkerboard Pattern Formed by Cellular Automata Agents (Rolf Hoffmann)....Pages 239-264
Do Ants Use Ant Colony Optimization? (Wolfhard von Thienen, Tomer J. Czaczkes)....Pages 265-291
Slime Mould Inspired Models for Path Planning: Collective and Structural Approaches (Jeff Jones, Alexander Safonov)....Pages 293-327
Physarum-Inspired Solutions to Network Optimization Problems (Xiaoge Zhang, Chao Yan)....Pages 329-363
Maze-Solving Cells (Daniel Irimia)....Pages 365-378
When the Path Is Never Shortest: A Reality Check on Shortest Path Biocomputation (Richard Mayne)....Pages 379-399
Shortest Path Finding in Mazes by Active and Passive Particles (Jitka Čejková, Rita Tóth, Artur Braun, Michal Branicki, Daishin Ueyama, István Lagzi)....Pages 401-408
The Electron in the Maze (Simon Ayrinhac)....Pages 409-420
Maze Solvers Demystified and Some Other Thoughts (Andrew Adamatzky)....Pages 421-438
Back Matter ....Pages 439-441

✦ Subjects

Engineering; Complexity; Computational Intelligence