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

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

С каждой вершиной дерева мы связываем нижнюю границу стоимости любого тура из множества, представленного вершиной. Вычисление этих нижних границ - основной фактор, дающий экономию усилий в любом алгоритме типа ветвей и границ. Поэтому особое внимание следует уделить получению как можно более точных границ. Причина этого следующая. Предположим, что мы построили конкретный полный тур со стоимостью т. Если нижняя граница, связанная с множеством туров, представленных вершиной v,, равна Мт, то до конца процесса поиска оптимального тура не нужно рассматривать вершину Vf и все следующие за ней (почему?).

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

1. В терминах матрицы стоимостей С каждый полный тур содержит только один элемент (ребро и соответствующую стоимость) из каждого столбца и каждой строки. Заметим, что обратное утверждение не всегда верно. Множество, содержащее один и только один элемент из каждой строки и из каждого столбца С, не обязательно представляет тур. Например, в задаче, изображенной на рис. 3.4.1, множество {(1, 5), (5, 1), (2, 3), (3, 4), (4, 2)} удовлетворяет этому условию, но не образует тура.

2. Если вычесть константу h из каждого элемента какой-то строки или столбца матрицы стоимостей С, то стоимость любого тура при новой матрице С ровно на h меньше стоимости того же тура при матрице С. Поскольку любой тур должен содержать ребро из данной строки или данного столбца, стоимость всех туров уменьшается на h. Это вычитание называется приведением строки (или столбца).

Пусть t - оптимальный тур при матрице стоимостей С. Тогда

стоимостью тура t будет

Если С получается из С приведением строки (или столбца), то t должен остаться оптимальным туром при С и

z{f)=h+zif), где г (t) -- стоимость тура t при С.

11 = 25 + 5 + 1+6 + 7 + 3 = 47

Рис. 3.4.3. Приведение матрицы стоимостей, показанной на рис. 3.4.1, а.

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

h= 2 hi.

все строка и столбцы.

Полученную в результате матрицу стоимостей назовем приведенной из С. На рис. 3.4.3 показано приведение матрицы стоимостей, изображенной на рис. 3.4.1, а. Значения hi даны в конце каждой строки и столбца (строки и столбцы последовательно перенумерованы).

Общее приведение составляет ft=47 единиц. Следовательно, нижняя граница стоимости любого тура из R также равна 47, т. е.

z{t)=h+z (0>/г=47,

так как г (0>0 для любого тура t при приведенной матрице С. Эта граница указана около корня дерева на рис. 3.4.2.

Рассмотрим нижние границы для вершин уровня 1, т. е. для мно-

жеств (3, 5} и (3, 5}. Будем работать с приведенной матрицей, изображенной на рис. 3.4.3, имея в виду, что значение 47 должно быть прибавлено к стоимости оптимального тура t при С для того, чтобы получить истинную стоимость t при с.

По определению ребро (3, 5) содержится в каждом туре множества {3, 5). Этот факт препятствует выбору ребра (5, 3), так как ребра (3, 5) и (5, 3) образуют цикл, а это не допускается ни для какого тура.

h=12 + 3 = 15

Рис. 3.4.4. (с) Приведенная матрица стоимостей после вычеркивания строки 3 и столбца 5 и установления £53=00; (б) приведение матрицы стоимостей, изображенной

в части (с).

Ребро (5, 3) исключаем из рассмотрения, положив Сдз=оо. Строку 3 и столбец 5 также можно исключить из дальнейшего рассмотрения по отношению к множеству (3, 5), потому что уже есть ребро из 3 в 5. Часть приведенной матрицы стоимостей, показанной на рис. 3.4.3, которая будет хоть сколько-нибудь полезна для дальнейшего поиска на множестве туров {3, 5}, показана на рис. 3.4.4, а. Она может быть приведена к матрице стоимостей, показанной на рис. 3.4.4, б с /г=15. Теперь нижняя граница для любого тура из множества {3, 5} равна 47+15=62; она указана около вершины (3, 5} на рис. 3.4.2.

Нижняя граница для множества (3, 5} получается несколько иным способом. Ребро (3, 5) не может находиться в этом множестве, поэтому полагаем £зв=оо в матрице, изображенной на рис. ,3.4.3. В любой тур из {3,5} будет входить какое-то ребро из города 8 и какое-то ребро к городу 5. Самое дешевое ребро из города 3, исключая старое значение (3, 5), имеет стоимость 2, а самое дешевое ребро к городу 5 имеет стоимость 0. Следовательно, нижняя граница любого тура в множестве {3,5} равна 47+2+0=49; это указано около вершины {3, 5} на рис. 3.4.2.

На данной стадии нам удалось сократить размер матрицы стоимостей, рассматриваемой в вершине (3, 5}. Кроме того, если мы сможем найти тур из множества {3, 5} со стоимостью, меньшей или равной 62, тогда не нужно проводить дальше ветвления и вычисления границ в аршине (3, 5}. В этом случае будем говорить, что вершина