2015-08-21
291
This problem is known as «The problem about the travelling salesman». Let the graph G (N, V) is given, which vertices correspond to cities in the service zone of the travelling salesman, and arcs represent connections between pairs of cities. The route of the travelling salesman is called the contour which includes each node of a graph G.
D e f i n i t i o n. Contour including each vertex of graph G (N, V) only once is called Hamiltonian contour (or Hamiltonian cycle)
The term Hamiltonian cycle is given by name of the Irish mathematician William Hamilton who began studying these problems for the first time in 1859.
The travelling-salesman problem is called the problem of search of the traveling salesman route of the least length. The optimum solution of this problem is the Hamiltonian cycle of the least length. The problem can be solved with the following exact method.
Let's renumber n cities as integers from 1 to n. The base city will posses number n. We will notice that the travelling-salesman round tour corresponds to the shift of integers 1, 2..., (n- 1). Thus, the base city at number n constantly takes last position and does not participate in shift processes. Each shift can take conformity some number defining length traveling-salesman route as the sum of ribs lengths of a cycle, connecting all n graph nodes.
Having formed all shifts from (n -1) numbers and gained routes lengths, which quantity is defined as (n -1)!, it is easy to find the route of the least length.
The approximate heuristic algorithm can be obtained with the use of heuristics, for example «on each next step the nearest city is included into the cycle».
Definition of Hamiltonian cycle of the least length is immediate while defining optimum ring topology of telecommunication networks segments.
