Решение задачи о коммивояжере методом ветвей и границ. Пример

Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере.

	¥
		¥
			¥
				¥
					¥

Верхняя строка и левый столбец, выделенные затемненным фоном, содержат номера вершин графа; символ ¥, стоящий на главной диагонали, означает, естественно, отсутствие ребер-петель (начинающихся и заканчивающихся в одной и той же вершине); кроме того, символ ¥ здесь и всюду в дальнейшем обозначает «компьютерную бесконечность», т.е. самое большое из возможных в рассмотрении чисел; считается, что ¥+любое число =¥.

Подсчитаем j(G) в нашем примере. Для этого выполним приведение матрицы весов; сначала - по строкам:

	¥						min в строке 1
		¥					min в строке 2
			¥				min в строке 3
				¥			min в строке 4
					¥		min в строке 5

результат приведения по строкам:

	¥
		¥
			¥
				¥
					¥

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

	¥
		¥
			¥
				¥
					¥
	­ min в столбце 1	­ min в столбце 2	­ min в столбце 3	­ min в столбце 4	­ min в столбце 5

результат приведения матрицы:

	¥
		¥
			¥
				¥
					¥

сумма констант приведения j(G)=4+4+2+1+2+1=14.

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

	¥			0(4)
		¥	0(2)
		0(1)	¥		0(3)
	0(1)			¥
	0(0)			0(0)	¥

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

Построим для множества соответствующую ему матрицу и значение оценочной функции. Сейчас уместно отдельным абзацем напомнить ту самую «сложную» фразу из предыдущей лекции:

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

Учитывая это напоминание, элемент с номером (4,1) заменим на ¥ и вычеркнем строку номер 1 и столбец номер 4:

		¥
			¥
	¥
				¥

Приведем теперь эту матрицу:

		¥
			¥
	¥
				¥

Это - матрица M1,1; сумма констант приведения здесь равна 1, поэтому 14+1= 15.

Для M1,2 заменяем на ¥ элемент (1,4) в M1:

	¥			¥
		¥
			¥
				¥
					¥

после этого приводим полученную матрицу:

	¥			¥
		¥
			¥
				¥
					¥

Это - матрица M1,2; сумма констант последнего приведения равна 4, так что 14+4=18. Следовательно, дальнейшей разработке подвергается множество . Вот веса нулей матрицы M1,1 (они указаны в скобках):

		¥	0(2)
		0(1)	¥	0(3)
	¥		0(4)
	0(3)			¥

самым тяжелым является нуль с номером (4,3), так что теперь

следует рассматривать множества и .

Обратимся к первому из них. Опять напомним ту самую «сложную» фразу из предыдущей лекции:

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

Следовательно, клетки с номерами (4,2), (4,5) и (3,1) надо заполнить символом ¥; после этого строку номер 4 и столбец номер 3 следует вычеркнуть; получим:

		¥
	¥
			¥

Приведение этой матрицы:

		¥
	¥
			¥

Для оценочной функции: =15+2=17.

Матрица для множества :

		¥
			¥
	¥		¥
				¥

Результат ее приведения:

		¥
			¥
	¥		¥
				¥

Оценочная функция: =15+4=19. Следовательно, дальнейшей разработке подлежит . «Взвешиваем» нули:

	0(1)	¥
	¥	0(1)	0(1)
	0(1)		¥

Выбираем любую из соответствующих клеток; для определенности - клетку (2,1).

Теперь речь пойдет о множествах и .

Опять напомним фразу:

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

Поэтому для первого множества положим в последней матрице элемент с номером (3,2) равным ¥, вычеркнем строку номер 2 и столбец номер 1:

	¥
		¥

Приведем эту матрицу:

	¥
		¥

Получаем для оценочной функции: =17+1=18.

Для множества матрица такова:

	¥	¥
	¥
			¥

Приведение этой матрицы дает:

	¥	¥
	¥
			¥

Для оценочной функции: =17+1=18.

Получилось, что для дальнейшей разработки можно брать любое из множеств и . В первом случае уже получена матрица размером 2´2; ее нулевые клетки дают те ребра, которые с найденными ранее составляют обход коммивояжера, причем вес этого обхода равен значению оценочной функции - 18. Вот этот обход:

(1,4)(4,3)(2,1)(5,2)(3,5) или 1®4®3®5®2®1.

Найденный рекорд на самом деле является искомым оптимумом,

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