Алгоритм Литтла: решаем задачу коммивояжёра

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

Что такое алгоритм Литтла

Алгоритм Литтла работает с квадратной матрицей расстояний $C = (c_{ij})$, где $c_{ij}$ - стоимость переезда из города $i$ в город $j$, а на диагонали стоит $\infty$, потому что ехать из города в самого себя нельзя. Это частный случай общей схемы branch and bound, но с двумя характерными именно для него приёмами: оценка снизу строится через приведение матрицы, а ребро для ветвления выбирается по максимальному штрафу нулевой клетки.

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

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

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

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

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

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

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

Штрафы нулевых клеток

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

$\theta_{ij} = \min_{k \neq j} c_{ik} + \min_{k \neq i} c_{kj}.$

Логика простая: если ребро $(i,j)$ исключить (поставить в клетку $\infty$), то выезд из города $i$ и въезд в город $j$ всё равно придётся оплатить, и минимально это обойдётся в $\theta_{ij}$. Поэтому исключение клетки с большим штрафом дорого наказывается - её выгоднее включить.

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

Для ветвления алгоритм Литтла выбирает нулевую клетку с максимальным штрафом $\theta_{ij}$. Это эвристика, направляющая поиск: включение такого ребра перспективнее всего, а его исключение поднимает границу сильнее всего. Выбранное ребро $(i,j)$ порождает две дочерние ветви.

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

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

Отсечение по рекорду

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

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

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

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

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

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

• Забывают $\infty$ на диагонали. Без этого алгоритм Литтла «разрешит» переезд города в самого себя и испортит нижнюю границу с первого же приведения.
• Не блокируют подцикл. При включении ребра $(i,j)$ обязательно ставят $\infty$ в $(j,i)$, а в длинных цепочках - в клетку, замыкающую уже собранный частичный путь, иначе маршрут распадётся на несколько мелких циклов.
• Берут первый минимум вместо второго в штрафе. Штраф нулевой клетки считается по минимумам строки и столбца без самой клетки; саму нулевую клетку из подсчёта исключают.
• Путают ветви местами. Прибавка штрафа $\theta_{ij}$ идёт к ветви, где ребро исключается; к ветви включения прибавляется сумма новых приведений уменьшенной матрицы.
• Раскрывают узлы в произвольном порядке. Без стратегии «лучший первым» рекорд $B$ находится поздно, отсечение почти не работает, и дерево раздувается.

FAQ

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

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

Работает ли алгоритм Литтла для несимметричной задачи? Да. Он изначально оперирует произвольной матрицей $c_{ij} \neq c_{ji}$ - приведение, штрафы и блокировка подциклов симметрии не требуют. Симметрия лишь уменьшает число различных маршрутов вдвое, до $(n-1)!/2$.

Коротко

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