Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 3 )

Циклы Гамильтона: (a, b, e, c, d, f ), (a, b, e, d, f, c ).

Метод ветвей и границ

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

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

Рассмотрим особенности метода ветвей и границ применительно к задаче коммивояжера, иллюстрируя примером взвешенного неографа на 4-х вершинах:

Т. к. при построении циклов выбор первой вершины не принципиален, то положим, что это будет вершина с №1. Для данного графа цикл Гамильтона будет содержать 4-ре ребра, поэтому дерево решений для него выглядит следующим образом (всего шесть различных вариантов решения):

Примем за начальный "базовый" 4-ый вариант решения, который соответствует циклу Гамильтона (1,3,2,4,1) с весом Lб:

Lб=с(1,3)+ с(3,2)+ с(2,4)+ с(4,1) = 10+6+8+4 = 28 ед.

Первым (в ходе поиска) ребром цикла для базового варианта решения является ребро (1, 3). В других вариантах могут быть также ребра (1, 2) и

(1, 4). Для них можно вычислить оптимистические оценки нижней границы суммарного веса ребер цикла (далее просто веса соответствующего варианта).

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

·  Если значение оценки меньше Lб, то за базовый принимается этот вариант и процесс поиска продолжается.

Поиск прекращается, когда будет получено решение, включающее все вершины графа, т. е. найден цикл Гамильтона с минимальным суммарным весом ребер.

Эффективность метода ветвей и границ во многом зависит от способа получения оптимистических оценок строящегося цикла. Одна из подобных процедур при выборе начального участка X1 = { x1 (1), x2 (1), ..., x1 (1) } сводится к следующему. Из матрицы весов С, характеризующей граф решений, вычеркиваются строки {1, 2, ..., k-1} и столбцы {2, 3, ..., k}, определяемые номерами ветвей, образующих рассматриваемый участок нового варианта. В оставшейся части матрицы С' на первом этапе оценки в каждой строке матрицы С' отыскивается min c'ij, который запоминается. Этот минимальный элемент вычитается из оставшихся ненулевых элементов в каждой строке. Получаем новую матрицу - С". На втором этапе - в каждом столбце матрицы С" отыскивается min c"ij, который запоминается и затем вычитается из всех ненулевых элементов соответствующих столбцов. При этом оптимистическая Lo оценка длины цикла определяется как:

Lo = L (1,2,...,k) + min c'ij + min c"ij

Пример: Построим матрицу весов[14]:

	1	2	3	4
1	x	9	10	4
2	9	x	6	8
3	10	6	x	7
4	4	8	7	x

Если в качестве начального ребра выбрано ребро (1,2), то в соответствии с процедурой получения оптимистической оценки Lo получаем матрицу:

	1	2	3	4		min c’_ij			1	2	3	4
1	-	-	-	-		0		1	-	-	-	-
2	9	-	6	8		6		2	3	-	0	2
3	10	-	x	7		7		3	3	-	x	0
4	4	-	7	x		4		4	0	-	3	x
								min c’’_ij	0	-	0	0

Lo = c12 + min c'ij + min c"ij = 9+6+7+4+0+0+0 = 26 единиц < Lб .

Для начального ребра (1,4):

	1	2	3	4		min c’_ij			1	2	3	4
1	-	-	-	-		0		1	-	-	-	-
2	9	x	6	-		6		2	3	x	0	-
3	10	6	x	-		6		3	3	0	x	-
4	4	8	7	-		4		4	0	4	3	-
								min c’’_ij	0	0	0	-

Lо = c14 + min cij + min c"ij= 4+6+6+0+0+0 = 20 < Lб .

Оба пути 1,2 и 1,4 являются перспективными Lo < Lб. Для продолжения решения в качестве начальных участков могут быть выбраны 1,2,3; 1,2,4; 1,4,2; 1,4,3.

Оценка Lo для начального участка 1,2,3.

	1	2	3	4		min c’_ij			1	2	3	4
1	-	-	-	-		0		1	-	-	-	-
2	-	-	-	-		-		2	-	-	-	-
3	10	-	-	7		7		3	3	-	-	0
4	4	-	-	x		4		4	0	-	-	x
								min c’’_ij	0	-	-	0

Lo = L(1,2,3) + min c'ij + min c"ij = 15+7+4 = 26 < Lб