Решение задачи коммивояжера с помощью метода ветвей и границ

Алгоритм состоит из двух этапов:

Первый этап

Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.

1. Вычисляем наименьший элемент в каждой строке (константа приведения для строки)
2. Переходим к новой матрице затрат, вычитая из каждой строки ее константу приведения
3. Вычисляем наименьший элемент в каждом столбце (константа приведения для столбца)
4. Переходим к новой матрице затрат, вычитая из каждого столбца его константу приведения.
Как результат имеем матрицу затрат, в которой в каждой строчке и в каждом столбце имеется хотя бы один нулевой элемент.
5. Вычисляем границу на данном этапе как сумму констант приведения для столбцов и строк (данная граница будет являться стоимостью, меньше которой невозможно построить искомый маршрут)

Второй (основной) этап

1.Вычисление штрафа за неиспользование для каждого нулевого элемента приведенной матрицы затрат.
Штраф за неиспользование элемента с индексом (h,k) в матрице, означает, что это ребро не включается в наш маршрут, а значит минимальная стоимость «неиспользования» этого ребра равна сумме минимальных элементов в строке h и столбце k.

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

2. Теперь наше множество S разбиваем на множества — содержащие ребро с максимальным штрафом(S_wi) и не содержащие эти ребра(S_wi/o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множеств S_wi/o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h_i,k_i), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h_i,k_i)
б) При вычислении затрат для множества S_wi примем во внимание, что раз ребро (h_ii,k_i) входит в маршрут, то значит ребро (k_i,h_i) в маршрут входить не может, поэтому в матрице затрат пишем c(k_i,h_i)=infinity, а так как из пункта h_i мы «уже ушли», а в пункт k_i мы «уже пришли», то ни одно ребро, выходящее из h_i, и ни одно ребро, приходящее в k_i, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h_i и столбец k_i. После этого приводим матрицу, и тогда оценка затрат для S_w равна сумме оценки затрат для S и r(h_i,k_i), где r(h_i,k_i) — сумма констант приведения для измененной матрицы затрат.
4. Из всех неразбитых множеств выбирается то, которое имеет наименьшую оценку.

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

Небольшая оптимизация — подключаем эвристику

Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h_i,k_i) или нет, и вешаем двух и более детей — Sw(h_i,k_i) и Sw/o(h_i,k_i). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.