Page 111 - 6197

I
Очевидно, що в будь-який маршрут i входить один
елемент один елемент кожного рядка і кожного стовпця
матриці C . Тому, якщо із усіх елементів деякого рядка
матриці C відняти певне число r , то у новій матриці довжини
i
всіх маршрутів зменшаться на величину r . Ця властивість
i
випливає із того факту, що комівояжер повинен відвідати
кожне місто тільки один раз.
Нехай r  min :c , i  1,n . Утворимо нову матрицю
i ij
j
n
C   1  c  r . (2.16)
ij i
1
  1
У матриці C знайдемо найменший елемент h у
j
кожному стовпці і побудуємо нову матрицю
n
  2   1
C  c  h . (2.17)
ij j 1
Операції, які визначаються формулами (2.16) і (2.17),
носять назву приведення матриці віддалей.
Виразимо елементи матриці C через елементи матриці
  1
  2
  2
  1
r
C . Оскільки c  c  , то c  c  . Для матриці C
r
ij ij i ij ij i
  1
  1
будемо мати c   2  c  h . Звідси c  c   2  h . Враховуючи
ij ij j ij ij j
  1
значення c , отримаємо
ij
c  c   2  r  h . (2.18)
ij ij i j
 
Використовуючи (2.18), знайдемо маршрут L i . У
відповідності з виразом (2.14)
n n
L   i   c i   2   r  h k  .
k
k k i
k 1 1  k 1
n n
0 
L
Введемо такі позначення:   i   c   2 і d  r  h  .
1 i k k i 1  k k
k 1  k 1 
Тоді
111