Решение задачи коммивояжера методом ветвей и границ

Для приведения надо вычесть минимум по строке 4: r4=7. При этом нижняя граница станет равной 55+7 = 62. После приведения получим

Из матрицы 2´2 получаем два перехода с нулевой длинной: (4, 3) и (6, 2).

Рис. 4 Ветвление на четвертом шаге

Рис. 5 Дерево ветвления с оценками

Полученный маршрутом коммивояжера z0 = (1, 4, 3, 5, 6, 2, 1) или (A-D-C-E-F-B-A).

 Скачать реферат