Метод ветвей и границ: задача коммивояжёра по шагам

Задача коммивояжёра звучит обманчиво просто: объехать все города по одному разу и вернуться в исходный с минимальной суммарной длиной маршрута. Но при $n$ городах число различных циклов растёт как $(n-1)!/2$, и полный перебор быстро становится невозможным. Метод ветвей и границ (branch and bound) - это способ найти точный оптимум, не перебирая всё: алгоритм строит дерево частичных решений и отбрасывает целые ветви, как только понимает, что лучшего ответа в них не будет. Ниже разберём схему пошагово на матрице расстояний.

Что такое метод ветвей и границ

Метод ветвей и границ - общая стратегия точной дискретной оптимизации. Её две опоры заложены в названии. Ветвление (branching) разбивает множество всех допустимых решений на непересекающиеся подмножества - обычно по принципу «ребро $(i,j)$ входит в маршрут / не входит». Граница (bounding) - это оценка снизу для всех решений внутри подмножества: если нижняя граница ветви уже не меньше стоимости лучшего найденного маршрута (рекорда), вся ветвь отсекается без дальнейшего разбора.

Для задачи коммивояжёра метод ветвей и границ применяется к матрице расстояний $C = (c_{ij})$, где $c_{ij}$ - стоимость переезда из города $i$ в город $j$, а на диагонали стоит $\infty$ (в город из него самого ехать нельзя). Качество метода зависит от того, насколько точна нижняя граница: чем она «туже», тем больше ветвей отсекается.

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

Приведение матрицы и нижняя граница

Ключевая идея оценки снизу для задачи коммивояжёра - приведение матрицы. В любом маршруте из каждого города ровно один выезд и ровно один въезд. Значит, из каждой строки можно вычесть её минимум, а затем из каждого столбца - его минимум: ни одно допустимое решение от этого не изменится по структуре, изменится только отсчёт стоимости.

Сумма всех вычтенных минимумов и есть нижняя граница корня дерева. Формально, если $r_i = \min_j c_{ij}$ - минимум строки, а после вычитания строк $s_j = \min_i (c_{ij} - r_i)$ - минимум столбца, то

$h = \sum_i r_i + \sum_j s_j.$

Эта величина $h$ - гарантированный минимум: любой полный цикл стоит не меньше $h$. После приведения в матрице в каждой строке и каждом столбце появляется хотя бы один ноль - именно нули становятся кандидатами на включение в маршрут.

Выбор ребра для ветвления

Теперь нужно решить, по какому ребру $(i,j)$ ветвиться. Берут нулевые клетки и для каждой считают штраф - сумму второго по величине минимума по строке $i$ и по столбцу $j$ (точнее, минимума оставшихся элементов строки и столбца без самой клетки). Штраф $\theta_{ij}$ показывает, насколько вырастет нижняя граница, если ребро $(i,j)$ в маршрут НЕ включить.

Для ветвления выбирают клетку с максимальным штрафом: включение этого ребра выгоднее всего, а его исключение дороже всего наказывается. Это та эвристика, что отличает метод ветвей и границ от слепого перебора - она направляет поиск к перспективным маршрутам первым.

Дерево ветвления: две ветви

Выбранное ребро $(i,j)$ порождает две дочерние ветви.

• Ребро включается. Из матрицы удаляют строку $i$ и столбец $j$, ставят $\infty$ в клетку $(j,i)$, чтобы не образовался преждевременный подцикл, и снова приводят уменьшенную матрицу. Новая нижняя граница ветви = граница родителя + сумма новых приведений.
• Ребро исключается. В клетку $(i,j)$ ставят $\infty$ и приводят. Нижняя граница этой ветви = граница родителя + штраф $\theta_{ij}$.

Алгоритм всегда раскрывает ветвь с наименьшей текущей нижней границей (стратегия «лучший первым»). Когда матрица сжимается до размера $2 \times 2$, оставшиеся два ребра определяются однозначно, и маршрут замыкается в полный цикл - его стоимость становится кандидатом в рекорд.

Отсечение бесперспективных ветвей

Здесь и срабатывает «bound». Как только найден хотя бы один полный маршрут стоимостью $B$ (рекорд), любая ветвь с нижней границей $\geq B$ закрывается: внутри неё точного решения лучше уже не будет. Чем раньше найден хороший рекорд, тем агрессивнее отсечение - поэтому хорошая первоначальная оценка (например, жадным «ближайшим соседом») ускоряет метод ветвей и границ в задаче коммивояжёра.

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

Сложность и практические границы

В худшем случае метод ветвей и границ для задачи коммивояжёра сохраняет экспоненциальную сложность - отсечения не дают гарантий по числу узлов. На практике же на матрицах до $20$–$40$ городов он находит точный оптимум за разумное время, потому что качественная нижняя граница режет огромную долю дерева.

Если задача больше, переходят либо к более сильным релаксациям (линейное программирование, метод Хелда-Карпа с $1$-деревом), либо к приближённым алгоритмам и эвристикам. Но именно метод ветвей и границ остаётся базовым «честным» способом получить доказуемо оптимальный маршрут.

Полезно понимать и расход памяти. При стратегии «лучший первым» в очереди живых ветвей одновременно может храниться много частичных матриц, и для больших $n$ это становится узким местом раньше, чем время. Поэтому на практике комбинируют подходы: сначала проходят вглубь по самой перспективной ветви, чтобы быстро получить рекорд $B$, а затем переключаются на лучший-первым уже с агрессивным отсечением. Ещё один рычаг - пересчитывать нижнюю границу инкрементно, не приводя всю матрицу заново на каждом узле, а лишь корректируя её после удаления одной строки и одного столбца. Эти инженерные детали не меняют корректность метода ветвей и границ, но решают, удастся ли довести задачу коммивояжёра до точного ответа за приемлемое время.

Частые ошибки

• Забывают про $\infty$ на диагонали. Без этого алгоритм «разрешит» переезд из города в самого себя и сломает нижнюю границу.
• Не блокируют преждевременный подцикл. При включении ребра $(i,j)$ обязательно ставят $\infty$ в $(j,i)$ (и в более длинных цепочках - в клетку, замыкающую частичный путь), иначе маршрут распадётся на несколько мелких циклов.
• Считают штраф неверно. Штраф нулевой клетки - это второй минимум по строке и столбцу, а не первый: сама клетка с нулём из подсчёта исключается.
• Берут симметрию формулы для несимметричной матрицы. Деление на $2$ в числе маршрутов $(n-1)!/2$ верно только для симметричной задачи ($c_{ij}=c_{ji}$); для ориентированного варианта циклов вдвое больше.
• Раскрывают ветви в случайном порядке. Без стратегии «лучший первым» рекорд находится поздно, и отсечение почти не работает.

FAQ

Чем метод ветвей и границ лучше полного перебора? Он находит тот же точный оптимум, но за счёт нижних границ отбрасывает целые поддеревья решений, не вычисляя их. На реальных матрицах это сокращает работу на порядки, хотя теоретическая верхняя оценка остаётся экспоненциальной.

Зачем приводить матрицу расстояний? Приведение по строкам и столбцам даёт начальную нижнюю границу даром: сумма вычтенных минимумов - это гарантированный минимум стоимости любого полного маршрута. Без приведения границы были бы слишком слабыми, и отсечение почти не срабатывало бы.

Подходит ли метод для несимметричной задачи коммивояжёра? Да. Матричный метод ветвей и границ изначально работает с произвольной матрицей $c_{ij} \neq c_{ji}$ - приведение, штрафы и блокировка подциклов не требуют симметрии. Симметрия лишь уменьшает число различных маршрутов вдвое.

Коротко

Метод ветвей и границ решает задачу коммивояжёра точно: приведение матрицы даёт нижнюю границу, штрафы нулевых клеток указывают ребро для ветвления, дерево делится на ветви «ребро включено / исключено», а найденный рекорд позволяет отсекать все ветви с границей не меньше его. Так алгоритм добирается до оптимального маршрута, перебирая лишь малую долю всех вариантов.