Для решения задачи коммивояжера

Постановка задачи коммивояжера состоит в следующем. Имеется городов. Задана матрица расстояний между ними: . Cчитаем, что . В общем случае возможно, что . Кроме того, будем полагать, что . Ищется кратчайший замкнутый маршрут (цикл), проходящий через каждый город ровно один раз и минимизирующий суммарное пройденное расстояние. Математическая постановка задачи может быть записана, например, следующим образом.

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

Определение.Матрица называется приведенной, если все ее элементы неотрицательны, а каждая строка и каждый столбец содержат по крайней мере по одному нулевому элементу.

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

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

Конкретизируем теперь основные этапы метода ветвей и границ применительно к данной задаче.

Пусть — множество всех возможных маршрутов.

1. Ветвление. При ветвлении очередное множество разбивается на два подмножества следующим образом. В матрице , соответствующей разветвляемому множеству, для каждого нулевого элемента вычисляется число . Затем определяется пара индексов , такая что . Первое подмножество формируется добавлением условия (из -го города идти в -й), второе подмножество содержит условие .

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

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