3. Метод ветвей и границ для решения задачи коммивояжера.

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

1. Вычисление оценки для множества .

Положим . Тогда для любого и

.

Положим . Тогда для любого и

. (19)

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

.

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

. (20)

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

3. Разбиение множества на подмножества (ветвление). Через обозначим приведенную матрицу, соответствующую множеству . Описанным ниже в п. 5 способом выбирается дуга . Множество разбивается на два подмножества и и исключается из числа кандиадтов на ветвление. Подмножество состоит из всех маршрутов множества , не содержащих дугу ; подмножество - из всех маршрутов, содержащих дугу (рис. 5).

Рис. 5

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

Оценки для вновь образованных множеств вычисляются следующим образом:

где и есть суммы констант приведения матриц и .

Легко показать, что

. (21)

5. Выбор дуги для ветвления.

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

. (22)

чтобы выполнить второе условие, среди дуг, удовлетворяющих (22), выберем дугу , для которой значение будет максимальным. Для этого, используя (21), вычислим функцию

для каждой дуги такой, что . В качестве дуги выберем ту, для которой

.