Information Technology Reference
In-Depth Information
Fig. 5.25 Mazes of
different complexities: (a)
simplest treelike; (b)
treelike containing cycles;
(c) complex maze with
cycles and the arbitrary
number of entrance points
and exit points
When developing the technique to determine the shortest path in a maze based
on reaction-diffusion media, three basic principles were used at the faculty of
physics of the Moscow State University:
1. Information systems that operate on the basis of reaction-diffusion media and
capable of solving maze problems must have hybrid architecture, i.e., be a
combination of a reaction-diffusion medium and a general-purpose digital
computer. In this case the operations of high computational complexity, such
as parallel wave propagation in a maze, are performed by the medium, and post-
processing of data, which is a task of relatively low computational complexity, is
performed by a general-purpose computer.
Below follow several observations that are important for further understand-
ing of the possibility of creating an efficient computational procedure for finding
the shortest path in the maze.
