Решение задачи коммивояжера методом ветвей и границ (1021734), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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).

Рис.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). Разбиваем множество на два и .

Очевидно

,

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

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

Характеристики

Список файлов домашнего задания