عنوان

Shortest path solvers :

3319775103

9783319775104

331977509X

9783319775098

Shortest path solvers :

[Book]

from software to wetware /

Andrew Adamatzky, editor.

Cham, Switzerland :

Springer,

2018.

1 online resource

Emergence, complexity and computation,

volume 32

2194-7287 ;

Includes index.

Intro; Preface; Contents; A Parallel Algorithm for the Constrained Shortest Path Problem on Lattice Graphs; 1 Definition of the Problem; 2 Related Problems in the Literature; 3 Example; 4 Pseudo-code of the Algorithm; 5 Memory Management and Initialization; 5.1 Labels for Vertices and Edges; 5.2 Termination; 5.3 Sequences Accessible to All Processing Elements; 6 Graph Update; 6.1 Step 1: Initial Triggering of Vertices; 6.2 Step 2: Analyzing Triggered Vertices; 6.3 Step 3: Gathering Input from Phantoms; 6.4 Step 4: Triggering Edges; 6.5 Step 5: Treatment of Triggered Edges.

5 Optimal Gathering for GG+5.1 Configuration Automorphisms, Symmetries and Ungatherabilty Results; 5.2 Weber Points for GG; 5.3 Optimal Gathering on Trees; 5.4 Optimal Gathering on Rings; 5.5 Optimal Gathering on Infinite Grids; 6 Conclusion; References; The MinSum-MinHop and the MaxMin-MinHop Bicriteria Path Problems; 1 Introduction; 2 Preliminaries; 3 MinHop-MinSum Path Problem; 4 MinHop-MaxMin Path Problem; 5 Computational Results; 5.1 MinHop-MinSum Path Problem; 5.2 MinHop-MaxMin Path Problem; 6 Conclusions; References.

6.6 Combining DCP with LFR6.7 Practical Effectiveness of DCP; 7 Conclusions; References; Influenza Virus Algorithm for Multiobjective Energy Reduction Open Vehicle Routing Problem; 1 Introduction; 2 Multiobjective Energy Reduction Open Vehicle Routing Problem; 3 Parallel Multi-Start Multiobjective Influenza Virus Algorithm (PMS-MOIVA); 3.1 Basic Parts of the Algorithm; 3.2 Multiobjective Influenza Virus Algorithm; 4 Computational Results; 5 Conclusions and Future Research; References; Practical Algorithms for the All-Pairs Shortest Path Problem; 1 Introduction; 2 The Hourglass Algorithm.

6.6 Step 6: Checking Terminal Conditions6.7 Step 7: Final Treatment of Phantoms; 6.8 Step 8: Final Treatment of Vertices; 6.9 Step 9: Final Treatment of Active Edges; 7 Large Sets of Active Vertices; 8 Performance Analysis; 9 Conclusion; References; Gathering a Swarm of Robots Through Shortest Paths; 1 Introduction; 2 Gathering in Different Environments; 3 Optimization Problems for Robot-Based Computing Systems; 4 Optimal Gathering for gmp+; 4.1 Configuration View; 4.2 Configuration Automorphisms and Symmetries; 4.3 Ungatherability Results; 4.4 Weber Points for gmp; 4.5 The Algorithm.

Distance-Vector Algorithms for Distributed Shortest Paths Computation in Dynamic Networks1 Introduction; 2 Background; 2.1 Asynchronous System; 2.2 Graph Notation; 2.3 Dynamic Networks; 2.4 Complexity Measures; 2.5 Distance-Vector Algorithms; 3 Distributed Bellmann-Ford; 4 Diffuse Update Algorithm; 4.1 Data Structures; 4.2 Algorithm; 4.3 Example of Execution; 5 Loop Free Routing; 5.1 Data Structures; 5.2 Algorithm; 5.3 Example of Execution; 6 Distributed Computation Pruning; 6.1 Power-Law Networks; 6.2 The Technique; 6.3 Data Structures; 6.4 Description; 6.5 Combining DCP with DUAL.

0

8

8

8

8

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.

Springer Nature

com.springer.onix.9783319775104

Shortest path solvers.

9783319775098

Cellular automata.

Computer algorithms.

Mathematical optimization.

Artificial intelligence.

Cellular automata.

Computer algorithms.

COMPUTERS-- General.

Cybernetics & systems theory.

Mathematical optimization.

COM-- 000000

GPFC

Adamatzky, Andrew

20200823112212.0

pn

[Book]

Y