The directed Physarum dynamics is known to solve positive linear programs: minimize @math subject to @math and @math for a positive cost vector @math . The directed Physarum dynamics evolves a positive vector @math according to the dynamics @math . Here @math is the solution to @math that minimizes the "energy" @math . In this paper, we study the non-uniform directed dynamics @math , where @math is a positive diagonal matrix. The non-uniform dynamics is more complex than the uniform dynamics (with @math being the identity matrix), as it allows each component of @math to react with different speed to the differences between @math and @math . Our contribution is to show that the non-uniform directed dynamics solves positive linear programs.
is a slime mold that apparently is able to solve shortest path problems. Nakagaki, Yamada, and T ' o th @cite_0 report about the following experiment; see Figure . They built a maze, covered it by pieces of Physarum (the slime can be cut into pieces which will reunite if brought into vicinity), and then fed the slime with oatmeal at two locations. After a few hours the slime retracted to a path following the shortest path in the maze connecting the food sources. The authors report that they repeated the experiment with different mazes; in all experiments, Physarum retracted to the shortest path.
@cite_0
2138415668
Physarum Polycephalum is a slime mold that apparently is 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.