Page 128 - 6197

Риски над ребрами вказують на те, що в процесі побудови
1-дерева відповідні дуги повинні бути вилучені.
У подальшому процес розв’язання задачі відбувається у
відповідності з алгоритмом меж і гілок.
Приклад 2.4. Розв’яжемо задачу комівояжера, коли
c  c . Матриця віддалей між містами наведена в табл. 2.9.
ij ji
Спочатку знайдемо верхню оцінку G , використавши
0
жадібний алгоритм. Маємо такий маршрут:
5
2
3
4
i  1       1 , довжина якого   13L i  .
6
0 0

Таблиця 2.9 – Віддалі між містами
Номера пунктів
1 2 3 4 5 6
1 M 2 2 3 3 3
2 2 M 1 1 1 3
Номера пунктів 3 2 1 M M 3 3
3
3
3
3
3
1
4
5 3 1 3 3 M 1
6 3 3 3 3 1 M

Для матриці C будуємо 1-дерево T найкоротшої
1
довжини.
Всі можливі маршрути комівояжера утворюють зв’язаний
неорієнтований граф. Номера вершин графа співпадають з
номерами міст, а вага ребер c це віддалі між містами.
ij
Виберемо n  1 вершину графа з номерами 2 3, , ,n і
побудуємо на цих вершинах каркас графа найкоротшої
довжини. Оскільки розмір сформульованої задачі невеликий

128