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

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

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

Lo = L(1,2,4) + min c'+ min c"= 17+10+4+3=34 > Lб .

Оценка Lo для участка 1,4,2.

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

Lo = 12+6+10+0+0=28 = Lб.

Оценка Lo для участка 1,4,3.

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

В результате преобразований в матрице весов получаем

Lo = 11 + 9 + 6 + 0 +0 = 26 < Lэ.

Из всех полученных вариантов два являются перспективными. Это варианты 1,2,3 и 1,4,3. Продолжаем рассматривать эти варианты аналогично предыдущему шагу.

Полностью дерево решений для заданного примера имеет вид:

Два полученных решения отличаются только направлением маршрута.

Эвристические методы

На практике чаще используют приближенные эвристические алгоритмы, дающие решения, близкие к оптимальным. Рассмотрим один из таких алгоритмов, известный под названием "метод (или алгоритм) ближайшего соседа".

1.  В качестве начальной точки произвольно выбираем один из городов.

2.  Следующим городом для посещения выбирается ближайший к последнему городу.

3.  Если все города уже посещались, возвращаемся в начальный город.

Можно получить лучшие результаты, используя более искусную локально-оптимальную стратегию. Алгоритм "включения ближайшего города" проводит маршрут по подмножеству из n городов. Алгоритм начинает работу с одного произвольно выбранного города. Новый город, добавляемый на каждом шаге, выбирается из городов, еще не вошедших в маршрут, как город, ближайший к некоторому городу, уже принадлежащему маршруту.

2.3.  Тема № 3 «Деревья в графе». Минимальные остовные деревья во взвешенном графе.

Дерево – связный граф, не содержащий циклов.

Остовное дерево графа – граф G*(X, U*), построенный на множестве вершин X и некотором подмножестве U* ребер исходного графа G(V, U) и являющийся деревом. По отношению к исходному графу такое дерево является остовом или каркасом. Если исходный граф является несвязным, то его остовом является лес, каждое дерево которого является остовом соответствующей компоненты связности.

Минимальное остовные дерево графа (или дерево Прима) – остов взвешенного исходного графа с минимальным суммарным весом ребер остова.

Метод Прима

Метод Прима является последовательным и наращивает дерево, состоящее из одной компоненты связности по матрице расстояний D={dij}nxn (n-количество вершин графа). Элемент матрицы dij равен расстоянию между i и j вершинами графа, рассчитанному, например, для ортогональной метрики, по формуле :

dij = mod(xi - xj) + mod(yi - yj),

где: хi, xj, yi, yj - координаты вершин i и j,

mod(p) - функция, дающая абсолютное значение выражения p.

Алгоритм состоит из следующей последовательности действий:

1.  В матрице D просматриваются элементы первой строки и выбирается минимальный элемент (например, элемент g-го столбца).

2.  Исключаются из рассмотрения 1-й и g-й столбцы и строится ребро, соединяющее 1-ю и g-ю вершины.

3.  Просматриваются 1-я и g-я строки и выбирается в одной из них минимальный элемент (если минимальных элементов несколько, то выбирается любой из них).

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