Page 124 - 6197

4 M 0 

C   6    .
6 0 M 

Отримана матриця розміром 2 2 допускає включення
тільки двох пар (4, 3) і (6, 2). Отримали цикл
L   1 4 , 2 1, , ,  3 5, ,  4 3, ,  6 2, ,  . Таким чином,
    5 6,
маршрут комівояжера з початковим пунктом 1 буде таким:
*
5
6
2
i  1      1. Довжина такого маршруту
3
4
*
L   63i  .
*
Перевіримо маршрут i на оптимальність. Аналізуючи
 
отримані раніше оцінки для G   k , бачимо, що L G   1  58 має
2 2
 
меншу оцінку, ніж L G 1   5 . Виникає питання: чи не приведе
  1
множина G до утворення замкнутого з оцінкою меншою за
2
 
  . Для відповіді на це питання піддамо аналізу
L G 1   5  L i *
  1
множину G . Інші множини G   k , k  1, які отримані у
2 2
 
результаті розгалуження, мають оцінки не менші за L G 2   1 і
подальшому розгляду не підлягають.
У початковій матриці C ставимо заборону в клітинці (1, 4)
1 2 3 4 5 6
1 M 27 43 M 30 26

 
2 7 M 16 1 30 25
 

 3 20 13 M 35 5 0 
C    .
4 21 16 25 M 18 18 


5 12 46 27 48 M 5 
 
6 23 5 5 9 5 M 


За наведеним раніше алгоритмом над матрицею C
здійснюємо операцію приведення, що дає
124