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

Рис.1

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

j i	1	2	3	4	6
2	03	∞	8	02	8
3	22	04	∞	26	4
4	3	00	17	∞	04
5	∞	010	17	10	47
6	37	12	010	2	∞

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

Табл.3

j i	1	2	4	6
2	0	∞	0	8
3	22	0	26	∞
4	3	0	∞	0
5	∞	0	10	47

Табл.4

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	∞	2	∞	2
8

Определим константы приведения для этих матриц

,

Следовательно

,

Так как , то дальнейшему ветвлению подлежит подмножество . Находим степени нулей матрицы.

j i	1	2	4	6
2	03	∞	02	8
3	22	022	26	∞
4	3	00	∞	08
5	∞	010	10	47

Претендентом к включению в гамильтонов контур станет дуга (3;2). Разбиваем множество на два и .

j i	1	4	6
2	0	0	8
4	3	∞	0
5	∞	10	47	10

j i	1	2	4	6
2	0	∞	0	8
3	22	∞	26	∞	22
4	3	0	∞	0
5	∞	0	10	47

Очевидно

,

Следовательно, очередному ветвлению нужно подвергнуть подмножество .

Переходим к ветвлению подмножества . Определяем степени нулей. Претендентом на включение в гамильтонов контур является дуга (5;4). Разбиваем множество на два подмножества: и .

Находим нижние границы

,