Практикум по дисциплине «Дискретная математика»

Эта задача имеет практическую интерпретацию, благодаря которой и получила своё название: коммивояжёр (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3..n и вернуться в первый город. Стоимости проезда между городами известны. В каком порядке следует объезжать города, чтобы замкнутый путь (тур) коммивояжера был наименее затратным?

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

Очевидно, c_ij следует трактовать как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру $5. Это означает, что любой тур подешевеет на $5, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы M на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере $10, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.

Вычитая любую константу из всех элементов любой строки или столбца матрицы C, мы оставляем минимальный тур минимальным.

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

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

Продемонстрируем теперь метод ветвей и границ для решения задачи о коммивояжёре.

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

	1	2	3	4	5
1		9	8	4	10
2	6		4	5	7
3	5	3		6	2
4	1	7	2		8
5	2	4	5	2	

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

Обозначим за Г множество всех обходов коммивояжера (т. е. всех простых ориентированных остовных циклов). Поскольку граф – полный, это множество заведомо не пусто. Сопоставим ему число (Г), которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов дуг графа и является оценкой снизу для стоимости минимального тура коммивояжёра. Приведённую матрицу весов данного графа следует запомнить, обозначим ее через С₁.

Подсчитаем (Г). Для этого выполним приведение матрицы весов.

1 2 3 4 5 1  5 4 0 6 4  min в первой строке 2 2  0 1 3 4  min во второй строке 3 3 1  4 0 2  min в третьей строке 4 0 6 1  7 1  min в четвёртой строке 5 0 2 3 0  2  min в пятой строке

1 2 3 4 5 1  5 4 0 6 2 2  0 1 3 3 3 1  4 0 4 0 6 1  7 5 0 2 3 0 

Теперь − по столбцам:

1 2 3 4 5 1  5 4 0 6 2 2  0 1 3 3 3 1  4 0 4 0 6 1  7 5 0 2 3 0  0 1 0 0 0 ↑ min в первом столбце ↑ min во втором столбце ↑ min в третьем столбце ↑ min в четвёртом столбце ↑ min в пятом столбце

1 2 3 4 5 1  4 4 0 6 2 2  0 1 3 3 3 0  4 0 4 0 5 1  7 5 0 1 3 0  Матрица C1

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

Обозначим полученную матрицу через С₁ и найдём в ней самый тяжёлый нуль. Заметим, что замена нулевого элемента на  приводит к изменению лишь двух слагаемых суммы констант приведения (Г) – по одному при приведении строк и столбцов. Поэтому вес нуля можно определить суммированием наименьших элементов его строки и столбца. Вообще нуль в клетке (i,j) приведённой матрицы означает, что цена перехода из города i в город j равна 0. А если мы не пойдём из города i в город j? Тогда все равно нужно въехать в город j за минимальную цену, указанные в j-том столбце; и все равно надо будет выехать из города i за минимальную цену, указанную в i-той строке. А это и есть оценка нуля. Например, вес нуля в первой строке и четвёртом столбце складывается из минимума по первой строке, равного 4 (c_1,2=c_1,3=4), и минимума по четвёртому столбцу, равного 0 (c_5,4=0), без учета самого c_1,4.

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

	1	2	3	4	5
1		4	4	0(4)	6
2	2		0(2)	1	3
3	3	0(1)		4	0(3)
4	0(1)	5	1		7
5	0(0)	1	3	0(0)	

Самым тяжёлым оказывается нуль в клетке (1,4).