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

3) В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы 2.

Табл.2

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

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

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

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

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

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

Страницы: 1, 2, 3, 4, 5