Page 126 - 6197

1 M 1 M 4 0 

 
2 1 M 0 29 24 



C   1  3 15 13 35 5 M  .
 
4 0 0 M 2 2 


5 2 41 43 M 0 



  1
Для матриці C обчислимо константи приведення.
Очевидно, що r  , а всі інші значення r і h дорівнюють
5
3 k k

 
5
нулю. Тому   і L C   1  58 5 63  .
0
Не будучи повним циклом, отриманий маршрут має
*
оцінку, яка є однаковою з оцінкою замкнутого маршруту i .
Оскільки елементи матриці C невід’ємні числа неможливо,
  1
виходячи із G , отримати маршрут меншої довжини. Отже,
2
*
знайдений маршрут i є оптимальним.

2.3.5 Симетрична задача комівояжера
У тому випадку, коли c  c маємо симетричну задачу
ij ji
комівояжера.
Для розв’язання симетричної задачі можна застосувати
алгоритм, який розроблений для несиметричної задачі
комівояжера. При цьому виникають складнощі, які зумовлені
тим, що дерево розгалуження має значне число вершин.
Для симетричних задач розроблений спеціальний
алгоритм, який пов'язаний з поняттям 1-дерево.
1-деревом називають граф, який будується за таким
правилом: до дерева, що стягує вершини 2 3, , ,n,
добавляються два ребра, які інциденті вершині 1.
Довжину 1-дерева визначають як суму ваг його ребер.
Найкоротшим 1-деревом називають дерево мінімальної
дожини.

126