КМиИсО

	0	2	1 4		1	4	1
	B	1	5	2	4	2	C
		4	2	4		2
	B			1 4			C
C =	B	5	6			1	C
		1	4	5	1
	B				5		C
	@					1 A

Решение.

Шаг 1. приводим матрицу C и находим константу приведения

		0	1	1 2		04		3	1
		B	1	3	03	3		1	C
			3	0	2			1
C0	= C =	B	4	3	1 3		04		C
	e	B	03	2	3	1			C
		B				4			C
		@						1 A

h = 1 + 2 + 2 + 1 + 1 = 7

Для каждого нуля матрицы C0 считаем штраф по формуле (2) (обычно принято записывать штрафы в виде индексов рядом с соответствующим нулем, что мы и сделали). Например, 51 = min Ci1+min C5j = 1 + 2 = 3

Среди всех нулей полученной матрицы выбираем нуль с наибольшим штрафом. В нашем случае это элементы, соответствующие дугам (2; 4)

è (3; 5). Так как в нашей матрице имеется 2 нуля с максимальным штра-

фом, мы можем выбрать любой из них. Рассмотрим, например,

(2; 4).

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

a)множество циклов , содержащих дугу (2; 4) (соответственно вершины графа обозначим (2; 4)).

51

b)множествî öèклов, не содержащих этой дуги, которое будет обозна- чаться (2; 4)

Оценка множества (2; 4) равна

(2; 4) = 7 + 4 = 11;

где штраф 24 = 4.

Тогда матрица Cf1, описывающая множество (2; 4), согласно лемме 3 имеет вид:

		0	1	1	2	1	3	1
		B	1	3	0	3	1	C
			3	0	2		1
C1	=	B	4	4	1 3		0	C
e		B	0	2	3	1		C
		B				4		C
		@					1 A

,а приведенная матрица

		0	0	1	1	1	2	1
		B	1	3	0	0	1	C
			3	0	2		1
		B			1 0			C
C1	=	B	4	4			0	C
			0	2	3	1
		B				1		C
		@					1 A

Матрица C2 - это матрица, полученная стягиванием C0 ïî äóãå (2; 4).

Она получается из матрицы Cf2		1	2	3	5	1
C2 =	30	4	4	1	0
	1	1	3	0	1	C
e	4B	3	1	2	1
	5B	0	2	3		C
	@				1 A

52

и имеет вид:

C2 =	30	1	2	3	5
		4	2	1	0 1;
	1	1	1	0	1	C
	4B	2	1	1	0
	5B	0	0	3		C
	@				1 A

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

		C0
		7
C1		C
		2
		2;4
2;4
11		10

Здесь рядом с вершинами стоят оценки и записаны номера матриц, соответствующих этим вершинам.

Вычисляются они следующим образом:

( (2; 4)) = ( ) + 24 = 7 + 4 = 11;

à

( (2; 4)) = ( ) + hf24 = 7 + 3 = 10:

Согласно алгоритму, так как оценка, соответствующая матрице C2, ìåíü- ше оценки для C1, на следующем шаге для ветвления выбирают вершину(2; 4)и работают с матрицей C2; ей соответствующей.

Шаг 2. Считаем штрафы нулей C2. Результат имеет следующий вид:

53

C2 =	30	1	2	3	5
		4	2	1 02 1
	1	1	1	02	1	C
	4B	2	1	1	01
	5B	02	01	3		C
	@				1 A

Максимальный штраф соответствует дугам (1; 3); (3; 5); (5; 1) (так как нумерация строк и столбцов не изменяется по сравнению с исходной матрицей C0).

Выбирем, например, дугу (1; 3)

Имеем

( (1; 3)) = ( (2; 4)) + 2 = 12;

где штраф 13 = 2 .

Матрица, описывающая (1; 3), имеет вид:

C3 =	30	1	2	3	5	1
		4	2	1	0
	1	1	0	1	0	C
	4B	2	1	0	0
	5B	0	0	2		C
	@				1 A

(Это уже приведенная матрица, константа приведения которой равна 2.) Проведем теперь оценку вершины (1; 3).

Стягиваем матрицу C3 ïî (1; 3). Получаем

0	1	2	5
	1	2	1
3			0
C4 = 4	2	1	0
5@	0	0	1 A

(Здесь элемент c31 = 1, так как стягивание производилось по дуге

(1; 3).)

54

Эта матрица уже приведена. Поэтому

( (1; 3)) = ( (2; 4)) = 10

Âрезультате мы приходим к следующему дереву

			C0
			7
C1			C2
			2;4
2;4
11			10
		C3	C4
			1;3
1;3
			12

Теперь висячими у нас являются вершины (2; 4); (1; 3); (1; 3) и вершина (1; 3) имеет наименьшую оценку.Поэтому на следующем шаге мы разветвляем (1; 3) .

Шаг 3. Считаем штрафы нулей C4. Результат записан в виде

C4	= 40	1	2	5	1
		2	1	02
	3	1	0	02
	5@	02	02	1 A

Так как штрафы всех нулей равны, то выбираем любой, например, (3; 5). Имеем

( (3; 5)) = ( (1; 3)) + 2 = 12:

Матрица, описывающая (3; 5) имеет вид

C5	= 40	1	2	5	1
		2	1	0
	3	1	0	1
	5@	0	0	1 A

55

Проводим оценку (3; 5).

Стягиваем матрицу C5 ïî (3; 5) (при этом, чтобы не получить частичного цикла 1 ! 3 ! 5 ! 1 нужно поставить +1 и на месте (5; 1)).Получаем

5	1	2
		0
C6 = 4	2	1
e	1

Приводим эту матрицу и находим константу приведения.

5	1	2
	1	0
C6 = 4	0	1

h = 2

Оценка вершины (3; 5) равна

( (3; 5)) = ( (1; 3)) + 2 = 12

Âрезультате мы приходим к графу

C0
7
	C2
2;4	2;4
11	10
		C4
1;3		1;3
12		10
		C6
	3;5	3;5
	12	12

Таким образом, мы получили рекорд равный двенадцати и соответствующий ему цикл:

4 ! 1 ! 3 ! 5 ! 2 ! 4:

56

Так как в условии задачи требуется найти гамильтонов цикл минимальной стоимости, а не все такие циклы, вершины с оценками, не меньшими 12, отсекàþтся. Таким образом, остается единственная неотсеченная вер-

øèíà (2; 4), которая имеет оценку 11. Так как ей соответствует матрица C1; на следующем этапе будем работать именно с этой матрицей:

Шаг 4. Считаем штрафы нулей матрицы C1. Результат записан в виде

0	01	1	1	1 2		1
B	1	3	01	00	1	C
	3	0	2		1
B	4	3	1 00		01	C
B	01	2	3	1		C
B				1		C
@					1 A

Соответственно для ветвления выбираем дугу (4; 2).

( (4; 2)) = 11 + 3 = 14:

Так как полученная оценка больше рекорда, то вершина (4; 2) будет отсечена.

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

Стягиваем C1 ïî (4; 2).Получаем

C7 =	20	1	3	4	5	1
		0	1	1	2
	1	1	0	0	1	C
	3B	4	1	0	0
	5B	0	3	1		C
	@				1 A

Эта матрица уже приведена, поэтому

( (4; 2)) = ( (2; 4)) = 11

57

У нас только одна висячая вершина (4; 2) является неотсеченной и на следующем шаге мы должны разветвлять ее.

Шаг 5. Cчитаем штрафы в C7. Результат:

C7 =	20	1	3	4	5
		01	1	1	2 1
	1	1	01	00	1	C
	3B	4	1 00		01
	5B	01	3	1		C
	@				1 A

В качестве дуги для ветвления выбираем, например, (1; 3) .

( (1; 3)) = 11 + 1 = 12

Òàê êàê ( (1; 3)) не меньше рекорда, то (1; 3) будет отсечена.

Проводим оценку (1; 3).

Стягиваем C7 ïî (1; 3). Результат:

C8	= 30	1	4	5	1
		1	0	0
	2	0	1	2
	5@	0	1	1 A

Эта матрица приведена, поэтому

( (1; 3)) = ( (4; 2)=11

Óнас только одна неотсеченная вершина (1; 3). Значит на следующем шаге мы разветвляем ее.

Шаг 6. Считаем штрафы в C8. Результат:

C8	= 30	1	4	5
		1 01		02 1
	2	02	1	2
	5@	01	1	1 A

58

В качестве дуги ветвления выбираем, например, (2; 1).

( (2; 1)) = 11 + 2 = 13

Òàê êàê ( (2; 1)) не меньше рекорда, то (2; 1) будет отсечена. Проводим оценку (2; 1).

Стягиваем C8 ïî (2; 1) (чтобы не образовался частичный цикл 4 ! 2 ! 1 ! 3 ! 4 заменяем элемент (3; 4) íà +1). Результат:

C90 =	1 0
	1	1

Константа приведения этой матрицы равна 1. Значит

( (2; 1)) = ( (1; 3)) + 1 = 12

не меньше рекорда.

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

4 ! 1 ! 3 ! 5 ! 2 ! 4:

Это означает, что в данной формулировке задачи вершину (2; 1) можно отсечь.

Однако, так как после приведения матрицы C90 мы имеем

1 0

C9 = 1

0

,

Следовательно, с учетом предыдущих вычислений мы можем выписать еще 1 гамильтонов цикл

H2 = f4 ! 2 ! 1 ! 3 ! 5 ! 4g

59

с тем же весом 12.

Замечание. Если бы в условии задачи требовалось найти все гамильтоновы циклы минимального веса в графе, то на шаге 3 мы отсекли бы только те вершины, оценки которых строго больше рекорда. Те вершины, оценки которых в точности равны рекорду, также требуется ветвить с помощью алгоритма Литтла.

Схематически ход решения изображают в виде дерева.

C0

7

			C1						C2
								2;4
		2;4
		11						10
	\				C7		C3	\			C4
4;2		4;2				1;3					1;3
	14					11		12			10
		\				C8		\			C6
									C5
						1;3					3;5
		1;3						3;5
		12				11		12			12
						\	C9
						2;1					4;1
		2;1
						13		12
											12
						3;5					5;2 рекорд

5;4 рекорд

60