Конспект лекций ДМ

4.6.5 Метод ветвей и границ в задаче о коммивояжёре

Показателем эффективности является длина гамильтонова цикла. При вычислении оценки снизу будем учитывать, что каждый гамильтонов цикл графа, представленного в виде матрицы смежности (расстояний), входит только по одному элементу из каждой строки и каждого столбца.

Поэтому, если все элементы каждой строки или столбца уменьшить на какое-то число, то сам гамильтонов цикл не изменится, а длина его уменьшится на это число. Это число принимаем за оценку снизу.

Основная “изюминка” метода ветвей и границ заключается в способе вычисления нижней границы подмножеств и указании дуги , включение или невключение в маршрут которой разбивает множество гамильтоновых циклов на подмножества.

Длина оптимального маршрута отличается от длины маршрута в задаче с неприведённой матрицей на сумму констант приведения: ,

где: - константа приведения по строкам, определяется как (минимальный элемент в i – й строке);

- константа приведения по столбцам, определяется как (минимальный элемент в j – м столбце).

Длина маршрута: .

Исключение какой-либо дуги из маршрута означает замену длины данного маршрута на бесконечность: .

Включение дуги в маршрут приводит к исключению строки и столбца, а также, для предотвращения построения негамильтонового цикла, к исключению дуги : .

Выбор дуги . В оптимальный маршрут должны входить дуги, для которых в приведённой матрице смежности . Невключение этих дуг резко увеличивает оценку снизу. Константами приведения являются минимальные элементы в строке и столбце. После замены на бесконечность, сумма минимальных элементов строки и столбца будет минимальной.

Алгоритм поиска гамильтонова цикла

Осуществить приведение матрицы смежности по строкам и столбцам и определить значение и для каждой строки и столбца, где и . Матрицу приводим по правилу: , т.е. из каждого элемента вычитаем сумму констант приведения. Эта сумма равна нижней оценке границы исходного множества решений: .
Для всех элементов, у которых найти и выбрать - максимальное приращение оценки. Определить и - строку и столбец.
Вычёркиваем строку равную и столбец равный , а также накладываем запрет на дугу, образующую цикл с ранее выбранными дугами, если он не гамильтонов.
Разбиваем множество решений на два подмножества, включающее дугу и не включающее эту дугу. Если не выбраны все вершины графа, то переходим к пункту 1, иначе формируем гамильтонов цикл. Длина цикла будет определена суммой нижних оценок длин путей, полученных при каждом приведении матрицы.

Примечание. После получения оптимального решения необходимо проверить нет ли лучшего решения среди нерассмотренных подмножеств. Если такое есть, то необходимо выполнить весь алгоритм для подмножества с меньшей оценкой снизу.

Пример решения задачи о коммивояжёре

Имеем граф с шестью вершинами и следующей матрицей смежности (таблица 4.14). Найти методом ветвей и границ гамильтонов цикл наименьшей длины.

Таблица 4.14 - Матрица смежности

i/j	1	2	3	4	5	6
1		68	73	24	70	9
2	58		16	44	11	92
3	63	9		86	13	18
4	17	34	76		52	70
5	60	18	3	45		58
6	16	82	11	60	48

Приведем данную матрицу по строкам и столбцам.

Таблица 4.15 - Приведённая матрица смежности с константами приведения по строкам и столбцам

i/j	1	2	3	4	5	6
1		59	64	15	61	0	9
2	47		5	33	0	18	11
3	54	0		77	4	9	9
4	0	17	59		35	53	17
5	57	15	0	42		55	3
6	5	71	0	49	37		11
	0	0	0	15	0	0

Сумма констант приведения даёт некоторую нижнюю границу длин всех гамильтоновых путей: . Улучшили оценку за счёт приведения матрицы по столбцам. Нижняя оценка длин всех гамильтоновых путей: .

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

Подсчитаем эти суммы:

Максимальная сумма соответствует дуге .

Множество разбиваем на два подмножества, одно из которых включает дугу - подмножество В, а другое – не включает – подмножество А. В матрице элемент заменяем на бесконечность, из элементов четвёртой строки вычитаем 17, а из элементов первого столбца вычитаем 5.

Таблица 4.16 - Матрица смежности подмножества

i/j	1	2	3	4	5	6
1		59	64	0	61	0
2	42		5	18	0	81
3	49	0		62	4	9
4		0	42		18	36
5	52	15	0	27		55
6	0	71	0	34	37

Находим оценку снизу подмножества : .

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

Таблица 4.18 - Матрица смежности подмножества

i/j	2	3	4	5	6
1	59	64		61	0
2		5	18	0	81
3	0		62	4	9
5	15	0	27		55
6	71	0	34	37

Эту матрицу можно привести по четвёртому столбцу, тем самым улучшить оценку на 18. Находим оценку снизу подмножества : .

Сравниваем две оценки: . Для дальнейшего разбиения выбираем подмножество . .

Таблица 4.19 - Приведённая матрица смежности подмножества

i/j	2	3	4	5	6
1	59	64		61	0
2		5	0	0	81
3	0		44	4	9
5	15	0	9		55
6	71	0	16	37

Находим дугу в матрице, которая максимально увеличивает нижнюю оценку при её исключении, т.е. имеет максимальную сумму констант приведений:

Максимальная сумма констант приведений соответствует дуге . Исключение дуги приводит к улучшению оценки на 68: , . . Включение дуги в путь вызывает исключение в матрице первой строки и шестого столбца. Необходимо запретить контур , тем самым исключить из рассмотрения дугу .

, для разбиения выбираем множество .

Таблица 4.20 - Матрица смежности подмножества

i/j	2	3	4	5
2		5	0	0
3	0		44	4
5	15	0	9
6	71	0		37

Подсчитываем сумму констант: .

Выбираем дугу , считаем оценку снизу подмножества : . Включение дуги приводит к исключению третьего столбца и шестой строки. Так же исключаем контур , запрещая дугу .

Таблица 4.21 - Матрица смежности подмножества

i/j	2	4	5
2		0	0
3	0		4
5	15	9

Матрицу можно привести по пятой строке на девять единиц. Нижняя оценка подмножества : . Сравниваем две оценки: . Для дальнейшего разбиения выбираем подмножество , .

Таблица 4.22 - Приведённая матрица смежности подмножества

i/j	2	4	5
2		0	0
3	0		4
5	6	0

Подсчитываем сумму констант, для которых : . Исключение дуги , приводит к улучшению нижней оценки подмножества на 10: . Включение дуги запрещает третью строку и второй столбик.

Таблица 4.23 - Матрица смежности подмножества

i/j	4	5
2		0
5	0

Эта матрица прямо указывает на то, что в искомый маршрут необходимо включить дуги . При этом нижняя оценка подмножества G увеличится на 10 и станет равной: . . Подмножества Н останется без изменения: .

Таким образом получили следующий гамильтонов цикл: (4, 1, 6, 3, 2, 5, 4). Длина его L = 102.

Сопоставляя длину найденного маршрута с нижней границей длин маршрутов подмножеств, которые не были рассмотрены до конца, видим, что рассмотрение большинства из них не имеет смысла, так как их нижняя граница превышает . Но может оказаться, что среди гамильтоновых путей подмножества , у которого нижняя граница равна 97, имеется путь меньшей длины.

Необходимо исследовать данное подмножество по матрице подмножества (таблица 10.7.3). Нужно рассмотреть два подмножества . Исключение дуги приводит к увеличению оценки подмножества : . Подмножество можно исключить из пути, так как .

Для подмножества включение дуги означает изъятие из матрицы шестой строки и первого столбца. Необходимо запретить дугу .

Таблица 4.24 - Матрица смежности подмножества

i/j	2	3	4	5	6
1	59	64	0	61
2		5	18	0	81
3	0		62	4	9
4	0	42		18	36
5	15	0	27		55

Матрицу можно привести по шестому столбцу путём вычитания из всех элементов столбца 9. Тогда нижняя оценка подмножества увеличится на 9: . И она станет больше, чем у подмножества . Значит лучшего решения в подмножестве К нет.

Рисунок 4.25 - Гамильтонов путь

Построим дерево, иллюстрирующее алгоритм решения.

А B

J K C D

G H

Рисунок 4.26 – Решение задачи о коммивояжёре в виде дерева

Содержание

i/j	1	2	3	4	5	6
1		68	73	24	70	9
2	58		16	44	11	92
3	63	9		86	13	18
4	17	34	76		52	70
5	60	18	3	45		58
6	16	82	11	60	48

i/j	1	2	3	4	5	6
1		59	64	15	61	0	9
2	47		5	33	0	18	11
3	54	0		77	4	9	9
4	0	17	59		35	53	17
5	57	15	0	42		55	3
6	5	71	0	49	37		11
	0	0	0	15	0	0

i/j	1	2	3	4	5	6
1		59	64	0	61	0
2	42		5	18	0	81
3	49	0		62	4	9
4		0	42		18	36
5	52	15	0	27		55
6	0	71	0	34	37

i/j	1	2	3	4	5	6
1		68	73	24	70	9
2	58		16	44	11	92
3	63	9		86	13	18
4	17	34	76		52	70
5	60	18	3	45		58
6	16	82	11	60	48

i/j	1	2	3	4	5	6
1		59	64	15	61	0	9
2	47		5	33	0	18	11
3	54	0		77	4	9	9
4	0	17	59		35	53	17
5	57	15	0	42		55	3
6	5	71	0	49	37		11
	0	0	0	15	0	0

i/j	1	2	3	4	5	6
1		59	64	0	61	0
2	42		5	18	0	81
3	49	0		62	4	9
4		0	42		18	36
5	52	15	0	27		55
6	0	71	0	34	37

i/j	1	2	3	4	5	6
1		68	73	24	70	9
2	58		16	44	11	92
3	63	9		86	13	18
4	17	34	76		52	70
5	60	18	3	45		58
6	16	82	11	60	48

i/j	1	2	3	4	5	6
1		59	64	15	61	0	9
2	47		5	33	0	18	11
3	54	0		77	4	9	9
4	0	17	59		35	53	17
5	57	15	0	42		55	3
6	5	71	0	49	37		11
	0	0	0	15	0	0

i/j	1	2	3	4	5	6
1		59	64	0	61	0
2	42		5	18	0	81
3	49	0		62	4	9
4		0	42		18	36
5	52	15	0	27		55
6	0	71	0	34	37