Information Technology Reference
In-Depth Information
It is easy to see that in this case relative lengths of the paths, and not the paths
themselves, can be determined based on the wave transit time. Therefore, to find
the shortest path in the maze, an additional algorithm must be specified.
These considerations determine the basic features of the computational pro-
cedure for finding a path in the maze based on the wave processes inherent in
nonlinear reaction-diffusion media.
Wave propagation through a maze is a parallel operation of high computa-
tional complexity. Reaction-diffusion media can effectively carry out such an
operation, and its successive stages can be stored in the memory of a digital
computer.
It will be shown below that for finding the shortest path in the maze between
the specified entry and exit points, a procedure of low computational complexity
implemented by a digital computer can be proposed. The basis for this procedure
is constituted by processing of images describing wave propagation through the
maze, recorded in computer memory.
2. A fundamentally important issue is the formation and storage of the maze image
in the medium as the wave passes through it. Attempts are known to solve it by
carving the image of a given maze out of an ion-exchange membrane in the
catalyst of the Belousov-Zhabotinsky reaction is immobilized. Efforts have also
been made to form a maze by printing its image on the surface of a membrane,
using a catalyst solution instead of printer ink. Nevertheless, these methods are
not effective for creating data-processing devices capable of quickly switching
from one type of the maze to another one and transform the maze during the
search for the shortest path. Media of the Belousov-Zhabotinsky type excited by
light are probably particularly suitable for solving maze problems. Their main
property is that they store input information for a sufficiently long time. There-
fore, the appearance of the image of the maze in the medium and the process of
its evolution during the passage of the wave can be recorded by a camcorder and
input into a digital computer. After that, finding the shortest path from the maze
entrance to the selected exit can be reduced to standard digital image processing
operations.
3. The crucial point in solving maze problems using reaction-diffusion media is
sufficiently rapid excitation of the wave process.
Two types of wave processes propagating in reaction-diffusion media are
known:
The first one represents trigger waves arising as a result of the interaction of
chemical processes and diffusion of medium components. The speed of
propagation of trigger waves is small—0.05 mm/s.
The second process represents phase waves that propagate independently of the
diffusion along the phase gradient created in some way. Phase waves are fast,
but difficult to control.
To determine the path in the maze phase waves excited by light radiation were
used. If projected onto the surface layer of the medium, an image whose intensity
varies monotonically along the surface of the medium will undergo evolution
