Page 130 - 6197

Верхня межа оцінки маршруту комівояжера   13L i 
0
буде рекордом задачі, який позначимо так: R . Всі задачі, які
e
будуть отримані у процесі розгалуження, зі значенням
верхньої межі, що перевищують R розгалуженню не
e
підлягають і в подальшому не розглядаються.
Перший крок алгоритму. Знаходимо степені вершин графа
4
T . Маємо d  d  d  2 , d  , d  d  1. Оскільки
1 1 3 5 2 4 6
max :d  , то початкова задача розгалужується на чотири
4
i i
задачі (рис. 2.9).
Обчислимо оцінки для кожної із вершин.
Другий крок алгоритму.
 Із початкового 1-дерева T (рис. 2.8) вилучаємо дугу
1
(1,2) і утворюємо цикл, з’єднавши вершини 1 і 6 (рис. 2.10).

Рисунок 2.8 - 1-дерево T
1
Довжина 1-дерева T
1
1
L T 1 L   3,  L 3 2,  L 2 4,  L 2 5,  L 5 6,  L   1, 
6
  
 2 1 1 1 13 9     . Крім того d  d  d  d  2 , d  ,
3
1 3 5 6 2
1
d  1. Задача   2, розгалужується на три задачі 2 3,  , 2 4, 
4

130