Page 138 - 6197

Шостий крок алгоритму.
На шостому кроці алгоритму розглядаємо задачі отримані
внаслідок розгалуження задачі 2 5,  (рис. 2.20).

1
 Задача   2, розв’язана на третьому кроці алгоритму з
оцінкою   12L i  .
 Задача 2 3,  розв’язана на четвертому кроці алгоритму

з оцінкою   12L i  .

 Задача 2 4,  розв’язана на п’ятому кроці алгоритму з
оцінкою   11L i  .

Всі задачі   2, , 2 3,  і 2 4,  відсіяні. Процес
1
розв’язування симетричної задачі комівояжера закінчений. У
результаті отриманий оптимальний маршрут   11L i *  .
На рис. 2.20 показано повне дерево розгалужень для
симетричної задачі.

Рисунок 2.20 – Повне дерево розгалужень для симетричної
задачі комівояжера

Відмітимо, що процес розгалуження задач відбувається у
тому випадку, коли степінь вершини 1-дерева T перевищує
1
значення 2. Ця умова також може бути використана як

138