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

10) Находим константу приведения для множества контуров

:

Следовательно, нижняя граница множества  равна

11) Сравниваем нижние границы подмножеств  и . Так как

то дальнейшему ветвлению подвергаем множество .

На рис.1 представлено ветвление по дуге (1;5).

Рис.1

Переходим к ветвлению подмножества . Его приведенная матрица представлена в таблице ниже.

12) Узнаем степени нулей матрицы. Претендентами на включение в гамильтонов контур будут несколько дуг (5;2) и (6;3). Для дальнейших расчетов выберем дугу (6;3). Разбиваем множество  на два подмножества: и  (табл. 3 и 4). Чтобы не допустить образования негамильтонова контура, в таблице 3 заменяем элемент (3;6) на знак «∞»

Табл.3

Табл.4

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9