КМиИсО

"2 = minf2g = 2:

Находим

" = minf3; 2; 3 2g = 1:

Величину потока на прямых дугах ((s; a); (b; t)) увеличиваем, а на обратной ((a; b) уменьшаем на 1. Получаем:

		a
	4;1		2;2
	5		1
	s	3;1	t
		1
	2;2		3;1
	1		6

b

Считаем

0 = 0 + " = 2 + 1 = 3:

Òàê êàê 0 = , то алгоритм свою работу закончил, в сети построен опти-

мальный поток.

Посчитаем суммарную стоимость пропущенного потока:

S(f) = 1 5 + 1 2 + 1 1 + 1 2 + 6 1 = 16:

41

5.8Алгоритм Клейна

Рассмотрим еще один алгоритм, позволяющий построить в сети поток заданной величины минимальной стоимости. Алгоритм Клейна работает иначе, чем алгоритм Басакера-Гоуэна: здесь сначала пропускается поток нужной мощности, а потом он изменяется таким образом, чтобы стоимость пропущенного потока стала минимальной.

ШАГ 0: Решение начинаем с любого потока f из источника в сток мощности M(f) = . Это может быть сделано подбором или с помощью задачи о максимальном потоке (в котором надо проводить вычисления до тех пор, пока величина потока не станет равной ). Вычисляем стоимость пропущенного потока f по формуле

Sf0 =	d(x; y)f(x; y):
	X
	(x;y)2E

ШАГ 1: Строим граф модифицированных стоимостей Gf .

ШАГ 2: Находим в графе Gf ориентировнный цикл отрицательной длины P :

df (P ) < 0:

Если в графе модифицированных стоимостей Gf нет ни одного цикла

отрицательной длины, то задача решена: в сети G построен поток мини-

мальной стоимости S(f) = Sf0 мощности . В противном случае переходим к Шагу 3.

ШАГ 3: В исходной сети G определяем замкнутую цепь (без ориентации) P , ñî- ответствующую циклу P . Прямыми дугами в этом цикле считаем дуги, сонаправленные соответствующим дугам цикла P в графе Gf , обрат- ными - дуги, имеющие противоположную ориентацию. На прямых дугах пути P вычисляем:

"1 = minfc(x; y) f(x; y)g;

на обратных -

"2 = minff(y; x)g:

42

Находим

" = minf"1; "2g:

На прямых дугах пути P величину потока увеличиваем, а на обратных уменьшаем на ".

ШАГ 4: Пересчитываем

Sf0 = Sf0 + df (P ) "

èпереходим к Шагу 1.

5.9Пример

Построить поток заданной мощности = 5 минимальной стоимости в сети

G:

		3;2	b
		2		5;2
	4;2	a		2
	1
		3;0		t
	s	2	2;0
		3;2	1
		3
			3;2
			8

c

В сети построен поток мощности = 4. Пропускаем еще одну единицу потока произвольным образом, получаем:

		3;3	b
		2		5;3
	4;3	a		2
	1
		3;0		t
	s	2	2;0
		3;2	1
		3
			3;2
			8

c

43

Итерация 1.

Находим Sf0 = 1 3 + 2 3 + 2 3 + 3 2 + 8 2 = 37: Строим граф модифицированных стоимостей Gf .

1	a			2	b
					2
1					2
s	3	2	1
					t
					8
3					8
		c

Находим цикл отрицательной длины P (можно воспользоваться алгорит-

мом Флойда):

P : b ! t ! c ! b;

длина цикла df (P ) = 5. Соответствующая ему цепь в сети G:

P : b ! t c ! b

На прямых дугах пути P ((b; t); (c; b) вычисляем:

"1 = minf5 3; 2 0g = 2;

на обратной (t; c)

"2 = minf2g = 2:

Находим

" = minf2; 2g = 2:

Величину потока на прямых дугах увеличиваем, а на обратной уменьшаем на 2. Получаем:

		3;3	b
		2		5;5
	4;3	a		2
	1
		3;0		t
	s	2	2;2
		3;2	1
		3
			3;0
			8

c

44

Находим стоимость нового потока

Sf0 = 37 + ( 5) 2 = 27:

Итерация 2.

Строим граф модифицированных стоимостей Gf

	1	a		2	b
	1				2
s		2	1
		3			t
					8

3

c

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

Легко видеть, что оба рассмотренных алгоритма позволяют найти поток мощности , если это число не превышает максимальной мощности допу-

стимых потоков.

Упражнение. Как с помощью алгоритма Басакера-Гоуэна и алгоритма Клейна найти в сети поток максимальной мощности минимальной стоимости?

45

6Задача коммивояжера. Алгоритм Литтла.

6.1Постановка задачи и необходимые определения

Постановка задачи.

Классическая формулировка задачи коммивояжера звучит следующим образом: как коммивояжеру, выйдя из своего города, вернуться в него, обойдя

åùå n городов, причем таким образом, чтобы длина пути была минимальной.

Другая известная интерпретация задачи коммивояжера может быть сформулирована так:

Пусть имеется n городов. Каждая пара городов соединена дорогой с заданной стоимостью проезда (при этом, стоимость проезда из A â B может отли- чаться от стоимости проезда из B â A). Найти такой циклический путь (т.е.

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

Эту задачу можно сформулировать и на языке теории графов. Для этого введем следующие определения.

Определение 6.1 Граф называется полным, если для любых u; 2 V 9 дуга (u; ) 2 E; то есть если E = V (2).

Определение 6.2 Простой цикл, соединяющий все вершины графа, называется гамильтоновым.

Переформулировка задачи.

Пусть дан полный ориентированный граф, имеющий n вершин с заданны-

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

Определение 6.3 Пусть f1; 2; :::; ng - все вершины G. Рассмотрим мат-

ðèöó C = (cij)ni;j=1;n, ãäå cij- стоимость дуги (i; j), cii = +1 è cij = +1, если дуги (i; j) нет. Такая матрица C называется матрицей стоимостей.

Определение 6.4 Назовем операцией приведения матрицы C следующую процедуру:

46

1)Из каждого столбца с номером j вычитаем минимальный элемент j,

2)После этого из каждой строки с номером i вычитаем минимальный элемент i.

Полученная таким образом матрица Ce называется приведенной матрицей, а число

XX

h =	i + j	(1)
i	j

константой приведения.

Матрица Ce обладает следующими свойствами:

1)eij 0;

e

2)в каждой строке и в каждом столбце Ce åñòü 0.

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

Лемма 6.1 Вес гамильтонова цикла относительно C равен весу гамиль-

тонова цикла относительно Ce + h:

Лемма 6.2 1) Вес любого гамильтонова цикла в графе G, которому соответствует матрица C, не меньше h;

2)Гамильтонов цикл является циклом минимального веса для графа, описываемого матрицей C, тогда и только тогда, когда он является цик-

лом минимального веса для графа, описываемого матрицей Ce.

Следствие. Åñëè fi1; :::; ing- некоторый гамильтонов цикл и все эле- менты в матрице Ce, соответствующие дугам данного цикла равны 0, то fi1; :::; ing - цикл минимального веса; вес этого цикла равен h.

Алгоритм, который будет описан ниже, основан на том, что на каждом шаге мы разбиваем множество рассматриваемых гамильтоновых циклов на два подмножества (одно из этих помножеств состоит из циклов, содержащих

выбранную дугу (i; j), а другое - из циклов, не содержащих этой дуги) и проводим оценку снизу для стоимостей циклов из этих подмножеств.

47

Исходя из вышеприведенного следствия, для поиска минимального цикла естественно рассматривать циклы, содержащие дуги, которым соответствуют

нули матрицы Ce(приведенной матрицы стоимостей).

Пусть (i; j) - некоторая дуга, такая что ecij = 0. Положим

	= min c	min c	(2)
ij	k6=j eik + s6=i esj

Лемма 6.3 Любой гамильтонов цикл, принадлежащий множеству i;j - циклов, не содержащих дуги (i; j), имеет вес, не меньший, чем

				(i; j) = h + ij				(3);
ãäå	h	оценка снизу по матрице C.
				, описывающая
Приведенная матрица C0							, получается из C заменой
						i;j
ci;j на +1 и последующей			процедурой приведения, причем					ij - константа
приведения.			e					e
e

Число i;j в (2) называется штрафом (за то, что мы не включили дугу (i; j) в цикл). Исходя из (3), естественным является выбор дуги (i; j) для включения в цикл из условия

ij = max sk;	(4)
ecsk=0

т. е. выбор такого нуля в матрице Ce, для которого штраф максимален.

Пусть дуга (i; j) выбрана из условия (4). Оценим стоимости гамильтоновых циклов, содержащих (i; j).

Определение 6.5 Пусть Ce	- матрица, полученная из C вычеркивани-
e	e

ем i-й строки и j-го столбца и заменой на +1 элемента ecji и всех других

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

Ce с помощью операции приведения, называется матрицей, стянутой по e

(i; j).

48

Лемма 6.4 Любой гамильтонов цикл, принадлежащий множеству i;j циклов, содержащих дугу (i; j), имеет вес, не меньший, чем

(i; j) = h + ehij;

ãäå hfij - константа приведения матрицы Ce. e

Графически вышеприведенные рассуждения можно описать следующим образом:

					( )=h
			C0			C0
			f			f
						i;j
			i;j			f
(i;j)=h+ ij					(i;j)=h+hij
							f
Здесь - множество всех гамильтоновых							f C - приведенная матри-
						циклов,		e
ца исходного графа, h - константа приведения (1)									C, ( ) - оценка
							матрицы

снизу стоимостей гамильтоновых циклов из , (i; j) - множество гамиль-

тоновых циклов не содержащих дугу (i; j), ij - штраф (2), (i; j) - оценка

0 - матрица, описанная в снизу для стоимостей циклов из множества (i; j), Cf

лемме 3, (i; j)- множество гамильтоновых циклов содержащих дугу (i; j),

(i; j) - оценка снизу стоимостей циклов из (i; j), hfij -константа приведения матрицы Ce, стянутой по (i; j), C0 - матрица, описанная в лемме 4. Выбор

äóãè (i; j) осущесвляется из условия (4). Эта схема описывает способ разбиения("разветвления") "корня" и получения оценок снизу для образованных ветвей.

6.2Алгоритм Литтла

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

49

матрицы C находят оценку снизу длины произвольного гамильтонова цикла в графе, затем выбирают дугу "ветвления" (i0; j0), то есть дугу, которой соответстует максимальный штраф i0j0 , и находят оценки множеств (i0; j0)

è(i0; j0) гамильтоновых циклов, соответственно содержащих дугу (i0; j0)

èне содержащиõ ýòó дугу. В дереве решений появляется 2 висячие верши-

íû (i0; j0) è (i0; j0). Из них выбирают вершину с минимальной оценкой и работают с матрицей, соответствующей этой вершине так же, как с матри-

öåé Ce, то есть находят элементы с максимальным штрафом, строят новые

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

Ck размерности 2 2 к соответствующей ей висячей вершине добавляем дуги, стоимости которых в Ck = 0, и получаем гамильтонов цикл стоимости,

равной оценке вершины с матрицей Ck: Стоимость этого цикла называют ре-

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

Замечание. В процессе построения матриц (во время операции стягивания) необходимо избегать возникновения частичных циклов. Например, если

мы работаем с циклом, в котором уже есть дуги (i; j) è (j; k), то нем не должно быть дуги (k; i), то есть запрещается ситуация, типа

i ! j ! k ! i:

Для исключения дуги (k; i) необходимо в соответствующей матрице коэффициент cki заменить на +1.

6.3Пример

Найти гамильтонов цикл минимального веса в графе, заданном матрицей

50