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

Таким образом, нижней границей множества всех гамильтоновых контуров будет число

5) Находим степени нулей полностью приведенной матрицы. Для этого как бы заменяем в ней все нули на знак «∞» и устанавливаем сумму минимальных элементов соответствующей строки и столбца. Степени нулей записаны в правых верхних углах клеток, для которых .

6) Определяем максимальную степень нуля. Она равна 19 и соответствует клетке (1;5). Таким образом, претендентом на включение в гамильтонов контур является дуга (1;5).

7) Разбиваем множество всех гамильтоновых контуров на два:  и . Матрицу  с дугой (1;5) получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент (5;1) на знак «∞».

8) Матрицу гамильтоновых контуров  получим из таблицы 2 путем замены элемента (1;5) на знак «∞».

9) Делаем дополнительное приведение матрицы контуров : = 0. Нижняя граница множества  равна .

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