Шаг 3. Определение множества дуг для дальнейшего ветвления.

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

.

В полученной матрице нужно определить сумму констант приведения:

Нижняя граница множества , где 18 – оценка предыдущего шага, 3 – оценка текущего шага.

Рассмотрим множество . Включение дуги проводится с помощью исключения 1-й строки (в множестве из пункта 1 мы идем только в пункт 3) и 3-го столбца (в множестве в пункт 3 мы можем попасть только из пункта 1). Элемент (3,1) заменяем на (исключаем возможность возвращения, зацикливания, образования негамильтонова цикла):

.

Нижняя граница множества , где 18 – оценка предыдущего шага, 1 – оценка текущего шага. Числа над матрицей суть номера столбцов, числа перед матрицей – номера строк.

Так как , то дальше ветвим множество .

Для матрицы

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

Для элемента эта сумма наибольшая. Поэтому все множество маршрутов распадается на два класса: (не содержит дугу ) и (содержит дугу ).

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

.

Определим в полученной матрице ее константу приведения:

.

Нижняя граница .

Рассмотрим множество . Включение дуги проводится с помощью исключения 2-й строки, 5-го столбца и замены элемента (5,2) на :

В полученной матрице

нужно определить константу приведения.

.

Нижняя граница . Поэтому дальше ветвим множество .

Для матрицы

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

.

Для элементов (3,4) и (4,2) эта сумма наибольшая. Выберем любой из них. Пусть это будет элемент (4,2). В этом случае все множество маршрутов распадается на два класса: (маршруты содержат дугу (4,2)) и (маршруты не содержат дугу (4,2)).

Рассмотрим множество . Исключение дуги (4,2) проводится с помощью замены элемента (4,2) на :

.

Определим в полученной матрице сумму констант приведения:

.

Получаем .

Рассмотрим множество . Включение дуги (4,2) производится за счет исключения 4-й строки и 2-го столбца. Элемент (2,4) в матрице отсутствует, поэтому нет угрозы зацикливания.

Для полученной матрицы определяем ее константу приведения. Очевидно, что она равна 1. Нижняя граница множества равна . Поэтому в дальнейшем ветвим множество .

Для этого в матрице

надо так выбрать нули, чтобы в каждой строке и в каждом столбце был ровно один отмеченный нуль. Это элементы (3,4) и (5,1). Именно эти дуги и нужно добавить в множество маршрутов : ответом в задаче является множество . Минимальная длина маршрута 21 (оценка, полученная на предыдущем шаге, не меняется). Маршрут, являющийся решением, выглядит следующим образом:

.

Дата добавления: 2015-08-09