ЗАДАЧА № 3

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

Исходные данные.

Вариант	А	Б	В	Г	Д	Е
A		-
Б
В				-
Г					-
Д						-
Е							-

 

Решение:

 

Задачу решаем методом теории графов, известным как метод "ветвей и границ".

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

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

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

Сначала – по строкам:

 

	А	Б	В	Г	Д	Е
А	-						2	min в строке 1
Б		-					7	min в строке 2
В			-				6	min в строке 3
Г				-			2	min в строке 4
Д					-		14	min в строке 5
Е						-	7	min в строке 6

 

 

	А	Б	В	Г	Д	Е
А	-
Б		-
В			-
Г				-
Д					-
Е						-

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

	А	Б	В	Г	Д	Е
А	-
Б		-
В			-
Г				-
Д					-
Е						-
	­ min в столбце 1	­ min в столбце 2	­ min в столбце 3	­ min в столбце 4	­ min в столбце 5	­ min в столбце 6

 

	А	Б	В	Г	Д	Е
А	-
Б		-
В			-
Г				-
Д					-
Е						-

 

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

 

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

Например, вес нуля в первой строке и четвёртом столбце складывается из минимума по первой строке, равного 6 (c_А,Г=c_А,Д=6), и минимума по четвёртому столбцу Г, равного 0 (c_Г,В=0), без учета самого c_А,Г.

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

 

 

	А	Б	В	Г	Д	Е
А	-			0(6)
Б		-				0(3)
В			-	0(5)
Г	0(2)			-
Д	0(0)		0(2)		-	0(0)
Е		0(1)			0(5)	¥

 

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

Разобьём множество Г на две части: множество (все циклы, проходящие через дугу (А,Г)) и (все циклы, не проходящие через дугу (А,Г)). Такое ветвление определяет необходимость выбора одного из этих вариантов. Множеству соответствует матрица С_1,1, полученная вычёркиванием соответствующих строки (строку А) и столбца (столбец Г). У оставшихся строк и столбцов сохраним их исходные номера. Разумеется, вместе с вычёркиванием строки и столбца, в матрице надо заменить на ∞; числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n). В данном случае из города Г мы уже не можем проехать в город А, поэтому в клетке (А,Г) ставим знак ∞.

 

А Б В Д Е Б   -       В     -     Г -         Д       -   Е         - Матрица С1,1         А Б В Д Е Б   -       В     -     Г -         Д       -   Е         - Матрица С1,1 после приведения

Сумма констант приведения матрицы С_1,1 здесь равна 7, поэтому φ(Г_{(А,Г)})= φ_{А,Г}=49+7=56. Сопоставим результат φ(Г_{(i,j)}) множеству Г_{(i,j)}, (в нашем случае Г_{(А,Г)}).

Множеству (в нашем случае ), в свою очередь, соответствует другая матрица – С_1,2, полученная заменой на ∞ элемент с_А,Г в матрице С₁:

А Б В Г Д Е А -     ∞     Б   -         В     -       Г       -     Д         -   Е           - Матрица С1,2

 

	А	Б	В	Г	Д	Е
А	-			∞
Б		-
В			-
Г				-
Д					-
Е						-

 

Матрица С_1,2 после приведения

 

Сумма констант последнего приведения равна 6, так что φ()=49+6=55. Теперь выберем между множествами Г_{(i,j)} и то, на котором минимальна функция j. В нашем случае из множеств, которому соответствует меньшее из чисел φ(Г_{(А,Г)})=56 и φ()=55.Поэтому дальнейшей разработке подвергнется множество . Итак, выделена определенная дуга (А,Г) графа и построены новые матрицы, к которым, очевидно, можно применить описанную выше процедуру. При каждом таком повторном применении будет фиксироваться очередная дуга графа, которая в конечном итоге войдёт в искомый гамильтонов цикл, если данная ветвь будет продолжена до конца и иметь минимальный вес.

 

В матрице С_1,2,1 подсчитаем веса нулей (веса нулей указаны в скобках):

 

	А	Б	В	Г	Д	Е
А	-		0(0)	-	0(0)
Б		-				0(3)
В			-	0(8)
Г	0(2)			-
Д	0(0)		0(0)		-	0(0)
Е		0(1)			0(0)	-

 

Самым тяжёлым является нуль с номером (В,Г), так что теперь следует рассматривать множества и . Обратимся к первому из них. Необходимо заменить на ¥ числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем циклам, которые проходят через уже отобранные ранее ребра.

Поскольку, вычеркнув строку В и столбец Г в матрице С_1,2, нужно также заменить на ∞ числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n), то в клетке с номером (В,Г) надо поставить символ ∞. Получим матрицу С_1,2,1:

 

	А	Б	В	Д	Е
А	-
Б		-
Г	-		-
Д				-
Е					-

 

 

Сумма констант остается неизменной, так как матрица не требовала приведения φ()=55

А Б В Г Д Е А -     -     Б   -         В     - -     Г       -     Д         -   Е           - Матрица С1,2,2

 

А Б В Г Д Е А -     -     Б   -         В     - -     Г       -     Д         -   Е           - Матрица С1,2,2 после приведения

Сумма констант приведения φ()=55+8=63. Следовательно дальнейшей разработке подлежит . «Взвешиваем» нули в матрице С_1,2,1:

	А	Б	В	Д	Е
А	-		0(0)	0(0)
Б		-			0(5)
Г	0(8)		-
Д	0(0)		0(0)	-	0(0)
Е		0(1)		0(0)	-

 

Самым тяжелым является нуль с номером (Г,А), теперь рассмотрим множества и .

Вычеркиваем строку Г и столбец А, ставим ∞ в клетке (А,Г) и получаем матрицу С_1,2,1,1

 

	Б	В	Д	Е
А		-
Б	-
Д			-
Е				-

 

Матрица не требует приведения и сумма констант приведения останется без изменений φ()=55.

Рассмотрим матрицу С_1,2,1,2:

 

А Б В Д Е А -         Б   -       Г ¥   -     Д       -   Е         - Матрица С1,2,1,2

 

А Б В Д Е А -         Б   -       Г -   -     Д       -   Е         - Матрица С1,2,1,2 после приведения

 

Сумма констант приведения φ()=55+8=63.

Произведем оценку нулей в матрице С_1,2,1,1

 

	Б	В	Д	Е
А		-	0(13)
Б	-			0(5)
Д		0(7)	-	0(0)
Е			0(0)	-

 

Самый тяжелый вес равный 13 имеет нуль в клетке с номером (А,Д), следовательно будем рассматривать множества и . Вычеркиваем строку А и столбец Д и заменяем число в клетке (Д,В) на знак ∞.

 

Получаем матрицу С_1,2,1,1,1:

 

Б В Е Б -     Д   -   Е     - Матрица С1,2,1,1,1

 

	Б	В	Е
Б	-
Д		-
Е			-

Матрица С_1,2,1,1,1 после приведения

 

Сумма констант приведения φ()=55+7=62.

Для множества матрица С_1,2,1,1,2 приобретает вид:

 

Б В Д Е А   - -   Б -       Д     -   Е       - Матрица С1,2,1,1,2

 

 

Б В Д Е А   - -   Б -       Д     -   Е       - Матрица С1,2,1,1,2 после приведения

 

Сумма констант приведения φ()=55+13=68.

Следовательно дальше разрабатываем матрицу . «Взвешиваем» нули в матрице С_1,2,1,1,1:

 

	Б	В	Е
Б	-		0(2)
Д		-	0(1)
Е	0(1)	0(2)	-

 

У нас получилось два одинаково тяжелых нуля, разработаем матрицы и . Вычеркиваем строку Б и столбец Е и заменяем число в клетке (Б,Е) на ∞. Получаем матрицу С_1,2,1,1,1,1:

 

Б В Д   - Е -   Матрица С1,2,1,1,1,1

 

 

	Б	В
Д		-
Е	-

Матрица С_1,2,1,1,1,1 после приведения

 

Сумма констант приведения φ ()=62+2=68.

Рассмотрим матрицу С_1,2,1,1,1,2:

 

Б В Е Б -   - Д   -   Е     - Матрица С1,2,1,1,1,2

 

 

Б В Е Б -   - Д   -   Е     - Матрица С1,2,1,1,1,2 после приведения

Сумма констант приведения φ()=62+2. Получается что для дальнейшей разработки можно брать любое из множеств, если мы возьмем матрицу С_1,2,1,1,1,1 то можно отработать матрицу и следовательно мы получим кольцевой маршрут следующего вида:

(В,Г)(Г,А)(А,Д)(Д,Б)(Б,Е)(Е,В) или В→Г→А→Д→Б→Е→В.