ственное выбранное ребро, полагаем р-2, q=\ и Ci2=oo. После этих шагов, соответствующих шагам 1 и 2 описанного выше подалгоритма, текущая матрица показана на рис. 3.4.6, а. После приведения получаем матрицу, изображенную на рис. 3.4.6, б, с /г=3 и w [(2, 1)]= =uy(X)+ft=47-b3=50. Текущее состояние показано на уровнях О и 1 на рис. 3.4.7.

10 0 0 11 = 2 + 1=3 В 6

Рис. 3.4.6. (с) Приведенная матрица стоимостей после вычеркивания строки 2 и столбца 1 и установления Ci2=oo; (б) приведение матрицы стоимостей, изображенной

в части (а).

. UpoSem О

Рис. 3.4.7. Дерево поиска, построенное для задачи, изображенной на рис. 3.4.1.

Блок 6. В конце концов мы должны прийти к множествам, содержащим так мало туров, что мы можем рассмотреть каждый из них и провести оценку для этой вершины без дальнейшего ветвления. Блок 6 проверяет, не пришли ли мы уже к таким множествам. Каждое ребро, про которое мы знаем, что оно содержится во всех турах из Y, сокращает размер С на одну строку и один столбец. Если в исходной задаче было N городов, а текущая матрица С имеет размер 2x2, то выбрано

уже N-2 ребер каждого тура Y. Поэтому множество Y содержит самое большее два тура (почему?). Вопрос о том, как их распознать, оставим в качестве упражнения. Таким образом, блок 6 проверяет, является ли С матрицей размера 2x2. Заметим, что это, посуществу, дает ответ на вопрос, поставленный в конце шага 2 при обсуждении блока 5.

Блоки 7 и 8. Блок 7 работает, только если С - матрица размеров 2x2. В этом блоке отыскивается самый дешевый тур в У и его вес обозначается через wiX). В блоке 8 проверяется, лучше ли данный тур, чем текущий лучший из известных туров. Если нет, то новый тур отбрасывается. Если да, то текущим лучшим туром становится новый тур, и мы полагаем Zo-w{Y).

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

Шаг I. Ищем множество S конечных вершин текущего дерева поиска. Шаг 2. Пусть вершина X будет выбрана так, что

w{X) = mmw{v).

в рассматриваемом примере:

Шаг 1. 5={{2ГГ}, {2, 1}}. Шаг 2. хю{{2, 1})=62, w{{2, 1})=50. Поэтому Х=(2, 1}.

Блок 10. Наше обсуждение помогает решить, что делать с этим беспокоящим вопросительным знаком, поставленным в блоке 10. Вы, должно быть, заметили, что алгоритм, представленный блок-схемой на рис. 3.4.5, не имеет окончания. Блок 10 показывает, должны ли мы остановиться. Если текущая граница для нашего лучшего тура Zo меньше или равна w{X) - наименьшей из неисследованных нижних границ,- тогда никакая из вершин, следующих за X, не может содержать лучшего тура. Благодаря способу выбора X в блоке 9 лучший тур не может также содержаться ни в какой другой из неоцененных конечных вершин. Теперь все дерево поиска оценено, и мы останавливаемся.

Если ш(Х)<го, поиск должен быть продолжен. В нашем примере Zo=oo, поэтому поиск не прекращается.

Блок 11. В этой части алгоритма получается откорректированная матрица стоимостей С для текущей вершины X. Процедура корректировки следующая:

Шаг 1. Равно ли множество X множеству Y, последний раз образованному в блоке 5? Если да, то текущая матрица С - это то, что нам нужно, и мы возвращаемся в блок 3. Именно это обычно случается на уровне 2 дерева поиска.

Шаг 2. Устанавливаем С -t- исходная матрица стоимостей.

Шаг 3. Устанавливаем S -*- (множество всех пар (J, /), которые должны быть ребрами в X).

Шаг 4. Вычисляем ё=ц. i)isCij.

Шаг 5. Для каждой (i, /) 6 S вычеркиваем строку i и столбец / в С. Для каждого пути, проходящего через (t, /), находим начальный и конечный города р и q и полагаем ср=оо. У каждого ребра (k, I), запрещенного для туров в X, полагаем С/;,=оо.

Шаг 6. Приводим матрицу С. Полагаем h равным сумме констант приведения.

Шаг 7. Вычисляем w(X)=g-\-h.

Шаг 5 вносит неудобство, так как он сводится к повторению того, что мы делали раньше. Очевидная альтернатива, осуществление которой потребует большого объема памяти,- запоминать матрицы С для каждой конечной вершины дерева. Как правило, это непрактично. В рассматриваемом примере мы просто выходим из подалгоритма на шаге 1.

Продолжим пример. Сейчас мы находимся в блоке 3, Х={2, 1}, ш(Х)=50, и дерево содержит только уровни О и 1 (рис. 3.4.7). Для определения множеств, следующих за X, нужно ребро (k, I). Подходящая матрица С показана на рис. 3.4.6, б. Используя подалгоритм, описанный в блоке 3, имеем

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

£)х5=1+0=1

Оз,=2+0=2

D„=18+0-18

Dg2=13+0=13

D,3=13+0--13

r,.,=0+l = l

Шаг 3. Dki=D-18 (в случае нескольких равных выбираем произвольно). Таким образом, (k, 0=(4, 5).

Теперь устанавливаем F, используя блок 4:

¥--={4, 5} и ш({4, 5}) = ш({2, 1}) + D:5 = 50 +18 = 68.

Далее рассматриваем вершину F={4, 5}. Во-первых, вычеркиваем из С строку 4 и столбец 5. Так как ребро (4, 5) не пересекается с ребром (2, 1), р=4 и q=5. Полагаем £5=00 и приводим С. Находим, что h=3 и w(F)=50+fi=53. Приведенная матрица С показана на рис. 3.4.8, а. Заметим, что нижние границы не уменьшаются при прохождении в глубь дерева.