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

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

i

1 2 3 4 5 6 Ui 1 ∞ 7 16 21 2 17 2 2 13 ∞ 21 15 43 23 13 3 25 3 ∞ 31 17 9 3 4 13 10 27 ∞ 33 12 10 5 9 2 19 14 ∞ 51 2 6 42 17 5 9 23 ∞ 5

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

j

i

 1 2 3 4 5 6
1 ∞ 5 14 19 0 15
2 0 ∞ 8 2 30 10
3 22 0 ∞ 28 14 6
4 3 0 17 ∞ 23 2
5 7 0 17 12 ∞ 49
6 37 12 0 4 18 ∞
Vj 0 0 0 2 0 2

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

Табл.2

j

i

 1 2 3 4 5 6
1 ∞ 5 14 17 019 13
2 03 ∞ 8 02 30 8
3 22 04 ∞ 26 14 4
4 3 00 17 ∞ 23 04
5 7 07 17 10 ∞ 47
6 37 12 08 2 18 ∞

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

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


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

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

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

j

i

 1 2 3 4 6
2 0 ∞ 8 0 8
3 22 0 ∞ 26 4
4 3 0 17 ∞ 0
5 ∞ 0 17 10 47
6 37 12 0 2 ∞

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

j

i

 1 2 3 4 5 6
1 ∞ 5 14 17 ∞ 13 5
2 0 ∞ 8 0 30 8
3 22 0 ∞ 26 14 4
4 3 0 17 ∞ 23 0
5 7 0 17 10 ∞ 47
6 37 12 0 2 18 ∞
14

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

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

:

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

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

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

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

К-во Просмотров: 335
Бесплатно скачать Курсовая работа: Решение задачи коммивояжера методом ветвей и границ