{3, 5} в дереве отработана. Тогда следующей целью может быть ветвление из вершины {3, 5} в надежде найти тур со стоимостью в пределах 49с<62.

В основных чертах блок-схема этого алгоритма ветвей и границ показана на рис. 3.4.5. Вскоре мы дополним эту схему рядом важных

йля текущей X

Шщистзат лерементк

ГГравевение С Устатбкп корня, X=R

BbUfoppedpe {к, I) 8т слеВукщега Ветбмния

ПроцЕса ВегпВ/1еяия Устанобкп Вершты Y Вычисление ш(У) .

Выбор „ следующей ВершшыХ

Если MV)<Zn, полагаем.

Рис 3.4.5. Блок-схема алгоритма ветвей и границ.

деталей. Здесь используются следующие обозначения. Буква X обозначает текущую вершину на дереве поиска, а w (X) - соответствующую нижнюю границу. Вершины, следующие непосредственно за X, назовем F и F; они выбираются ветвлением по некоторому ребру {k, I). Символ го обозначает стоимость самого дешевого тура, известного на данный момент. В начальный момент го=схэ. Советуем хорошо изучить эту блок-схему.

Теперь раскроем более детально содержание некоторых блоков этой схемы.

Блок 1. Установление начальных значений переменных, или инициализация, не представляет труда; детали оставлены в качестве упражнения.

Блок 2. Первое приведение - это непосредственная реализация описанной ранее процедуры; детали оставляем в качестве упражнения.

Блок 3. Выбор следующего ребра ветвления {k, I) определяет множества F и F, непосредственно следующие за текущим X. Ребро (k, I) нужно выбирать так, чтобы попытаться получить большую по величине нижнюю границу на множестве Y={k, 1), что облегчит проведение оценки для множества Y. Обычно предпочтительнее провести оценку для Y, так как размер этого множества и соответствующая ему матрица стоимостей обычно больше, чем у Y (из матрицы для Y вычеркнуты строка k и столбец /). Можно надеяться также, что Y с большей вероятностью содержит оптимальный тур.

Как применить эти идеи к выбору конкретного ребра ветвления (к, /)? В приведенной матрице стоимостей С, связанной с X, каждая строка и столбец имеют хотя бы по одному нулевому элементу (если нет, то С не полностью приведена). Можно предположить, что ребра, соответствующие этим нулевым стоимостям, будут с большей вероятностью входить в оптимальный тур, чем ребра с большими стоимостями. Поэтому мы выберем одно из них. Но какое? Пусть ребро (t, /) имеет Cij=0 в С. Мы хотим, чтобы у Y={i, j} была как можно большая нижняя граница. Вспоминая метод вычисления нижней границы для (3, 5} в нашем примере, мы видим, что для Y эта граница задается в виде

ш(К)=ш(Х)+(наименьшая стоимость в строке i, не включая Cj,-)+ -- (наименьшая стоимость в столбце /, не включая с).

Следовательно, из всех ребер (г, /) с Сг,=0 в текущей матрице С мы выбираем то, которое дает наибольшее значение для w{Y). Пусть это будет ребро {k, I).

Поэтому более подробное описание выбора, представленного блоком 3, имеет следующий вид:

Шаг 1. Пусть S - множество ребер (t, /), таких, что сг;=0 в текущей матрице стоимостей С.

Шаг 2. Положим Dij равным наименьшей стоимости в строке i, исключая сц, плюс наименьшая стоимость в столбце исключая Сц. Вычисляем Dij для всех (г, j)S.

Шаг 3. Выбираем следующее ребро ветвления {к, I) из условия

Dli= шах Dij.

Рассмотрим опять задачу с пятью городами, изображенную на рис. 3.4.1. Из приведенной матрицы С видно, что первое значение X, корень R, имеет w{X)=47. Применяя подалгоритм, описанный выше, находим наше первое ребро ветвления следующим образом:

Шаг 1. S={(1, 2), (2, 1), (3, 5), (4, 5), (5, 3), (5. 4)}

Шаг 2. Dia=2+1=3 D2i=12+3=15 Гз,=2+0=2 i>45=3+0=3 D,3=0+12=12 Dg4=0+2=2

Шаг 3. Выбираем ребро {k, l)={2, 1), так как Dgi - это максимальный элемент множества {Dtj}.

Блок 4. Определяем вершину F, следующую за X, точно так же, как мы делали раньше.

В рассматриваемом примере X=R и Y={2, 1}, т. е. это множество всех туров, не содержащих ребро (2, 1). Вычисляем нижнюю границу w(Y) так же, как в блоке 3, т. е.

w{Y) = w{X) + Dh и w{{2, 1}) = 47+15 = 62.

Блок 5. Вершине Y, следующей за X, соответствует подмножество туров из X, содержащих то ребро {k, 1), которое выбрано в блоке 3. В рассматриваемом примере Y={2, 1). При вычислении w{Y) необходима известная осторожность. Подробный подалгоритм имеет следующий вид:

Шаг 1. Из С исключаем строку k и столбец /.

Шаг 2. Все туры множества, представленного вершиной Y, содержат сколько-то (быть может, ни одного) из ранее выбранных ребер, помимо ребра (k, I). Ребро {k, I) будет или изолировано от этих других ребер, или будет частью пути, включающего некоторые или все эти ребра. Пусть р и q - начальный и конечный города этого пути. Возможно, что p=k и (или) q=l. Положим Сдр=(х>. Эта мера предохраняет от выбора ребра (<7, р) в качестве последующего для Y, а тем самым предохраняет от формирования замкнутого цикла длины меньше Л. Такие циклы, конечно, не разрешены при построении тура. Есть ли какие-то случаи, в которых мы не полагаем

Шаг 3. Приводим рассматриваемую матрицу С. Пусть h будет равно

сумме констант приведения. Шаг 4. Вычисляем w{Y) по формуле w{Y)=w{X)-\rh.

Возвращаясь к примеру, вычеркиваем строку 2 и столбец 1 из матрицы С, показанной на рис. 3.4.3. Так как ребро (2, 1) - един-