Information Technology Reference
In-Depth Information
5.3 Reaction-Diffusion Processors: Defining the Shortest
Path in a Maze
5.3.1 Characteristics of the Problem of Finding the Shortest
Path in the Maze
The problem of finding the shortest path in the maze, determined by certain
conditions, is one of the best known contemporary problems of high computational
complexity. A number of attempts to find efficient algorithms for its solution were
undertaken starting from the 1960s of the past century, including the use of
nonlinear reaction-diffusion media (mainly the media of the Belousov-
Zhabotinsky type). Especially important was the work of American researchers
Steinbock, Toth, and Showalter who offered a way to determine the shortest path in
complex mazes based on the use of trigger waves propagating in a Belousov-
Zhabotinsky medium.
Nevertheless, conclusions about the practical application of reaction-diffusion
media were for a long time quite pessimistic, because the propagation velocity of
the trigger waves excited in these media is small (~3 mm/min), with the character-
istic size of the maze in the order of centimeters. Only relatively recently it has been
shown that:
￿ Known photosensitive reaction-diffusion media of the Belousov-Zhabotinsky
type can be effectively used to solve at least not very complex maze problems.
￿ An effective technique can be developed for finding a path in a maze based on
the information about successive stages of wave propagation through it.
5.3.2 Basic Solution Principles of the Problem of Finding
the Shortest Path in the Maze
Let us define a maze as an object whose topological properties can be described
with a limited directed graph. This means that the object is composed of an arbitrary
number of vertices and edges joining them. In accordance with the specifics of the
maze let us subdivide the vertices into four types: starting points, which are entry
points into the maze (index of such vertices is equal to 1), intermediate points
(index of the vertex greater than or equal to 2), dead ends, and destination points
(index of such points is equal to 1).
The simplest graph in terms of the structure is a tree (Fig. 5.25 ). It has one
starting point and an arbitrary number of branches and destination points. More
complex are multigraphs containing cyclical combinations of edges. In this case at
least two routes connecting the chosen starting point and the destination can be
determined.
Search WWH ::




Custom Search