Information Technology Reference
In-Depth Information
Fig. 4.1 “Traveling salesman problem”
complex implicit dependence between the optimization of food delivery routes to
the anthill complex and the mechanisms of behavior of individual ants. This effect,
called emerging mechanisms, will be discussed in more detail below.
Distributed systems are characterized by multilevel operation. In the ant com-
munity there is a strict differentiation of persons in terms of actions they perform—
searching for food, protection from enemies, etc. This differentiation significantly
increases the efficiency of the system in terms of the main goal—survival in a
complex, dangerous, and changing environment.
In general information tasks required to understand the processes occurring in large
dynamic systems and to control them proved to be a stumbling block for digital
computers with von Neumann architecture due to their high computational complex-
ity. As the size of the problem (the required accuracy of calculations, dimensionality,
etc.) grows, resources needed for its solution, i.e., the required number of computer
cycles or the number of memory cells, grow sharply and in some cases exponentially.
An impressive example is the famous “traveling salesman problem” (Fig.
4.1
).
Suppose we have a number of cities to be visited. The traveling salesman
problem involves finding the shortest possible tour that visits each city exactly
once. Let us denote the start and end points of the route by
N
(0) and
N
(max). Then
the route can be written as
N
(0)-1-2-
...
-
N
-
N
(max). It is easy to see that the
number of all possible routes will be
N
! Suppose that the problem is solved by brute
force, i.e., by comparing the lengths of all paths. For
N
4 we need to compare the
24 routes, but if the number of cities increases to just 10, the number of routes will
have a huge value of 3,628,800.
¼
4.1.1 Some Details: Structural, Behavioral,
and Computational Complexity
The world around us is complex. This is a reality that defines our understanding of
the phenomena encountered every day. They become apparent in various fields of
human activity, from isolated, seemingly simple engineering tasks to sophisticated
