Page 110 - 6197

Рисунок 2.4 – Один із можливих маршрутів
комівояжера

Зауважимо, що у загальному випадку c  c .
ij ji
Нехай I множина всіх можливих маршрутів комівояжера.
Оскільки початкова точка фіксована, то число можливих
маршрутів визначається перестановкою чисел 1, 2, …, n  1,
тобто
I  n   1 !.
Серед всіх можливих маршрутів i необхідно знайти
I
маршрут мінімальної довжини за умови, що він не вміщувати
внутрішніх замкнутих циклів і i  i
1 n 1
*
L   min :i  L   i . (2.15)
Для розв’язування задачі (2.15) скористаємося методом
меж і гілок. Утворимо матрицю віддалей
c  c  c 
11 12 1n
 c c  c 
C   21 22 2n  , c  M , i  1,n ,
     ii
 
 c 1 n c n 2  c nn 
де M - досить велике додатне число.

110