Задача коммивояжёра: перебор, Хелд–Карп и эвристики 2-opt

Задача коммивояжёра (TSP) на собеседовании: перебор с отсечениями, динамика Хелда–Карпа за O(2ⁿ·n²) с восстановлением маршрута, ближайший сосед, 2-opt и оценка через MST. Код на Python.

14 мин чтенияалгоритмы · графы · динамическое программирование · python

Коротко

ПодходВремяТочностьКогда брать
Полный переборO(n!)O(n!)точноn ≤ 10
Перебор с отсечениямиO(n!)O(n!) в худшем случае, на практике быстрееточноn ≤ 12–13
Хелд–Карп (ДП по маскам)O(2n⋅n2)O(2^n \cdot n^2), память O(2n⋅n)O(2^n \cdot n)точноn ≤ 16–20
Ближайший соседO(n2)O(n^2)+10–25% к оптимумубыстрый стартовый маршрут
2-opt поверх соседаO(n2)O(n^2) за проходобычно в пределах нескольких %сотни и тысячи городов
Обход MSTO(n2)O(n^2)не хуже 2·OPT при неравенстве треугольникакогда нужна гарантия
  • Задача NP-трудная: полиномиального точного алгоритма не знают, и, скорее всего, его нет.
  • На собеседовании маленькое ограничение (n ≤ 16–20) почти всегда означает динамику по подмножествам.
  • Если городов много, задача превращается в инженерную: быстрая эвристика плюс локальные улучшения.

Постановка

Есть n городов и матрица расстояний dist[i][j]. Нужно выйти из города 0, побывать в каждом городе ровно один раз и вернуться назад так, чтобы суммарная длина маршрута была минимальной. В терминах графов это поиск гамильтонова цикла минимального веса.

Вариации, которые меняют решение:

  • Симметричная или асимметричная. В симметричной dist[i][j] == dist[j][i]. В асимметричной (улицы с односторонним движением, перелёты с разными ценами туда и обратно) направление обхода важно.
  • Метрическая или нет. Метрическая значит, что выполняется неравенство треугольника: dist[a][c] <= dist[a][b] + dist[b][c]. Для точек на плоскости это верно всегда. От этого свойства зависят гарантии приближённых алгоритмов.
  • Цикл или путь. Иногда возвращаться не нужно, а старт свободный. Это задача о кратчайшем гамильтоновом пути, и решается она тем же каркасом.

Почему задача сложная: решающая версия («есть ли маршрут короче L?») NP-полна, а оптимизационная NP-трудна. Для собеседования достаточно понимать следствие: точные методы экспоненциальны, и выбор идёт между «точно, но для малых n» и «быстро, но приближённо».

Полный перебор

Фиксируем город 0 как старт: циклический сдвиг маршрута не меняет его длину, поэтому перебирать стартовую точку бессмысленно. Остаётся (n − 1)! перестановок.

import math from itertools import permutations def tsp_brute(dist): n = len(dist) best, best_route = math.inf, None for perm in permutations(range(1, n)): # город 0 фиксируем как старт route = (0, *perm, 0) cost = sum(dist[a][b] for a, b in zip(route, route[1:])) if cost < best: best, best_route = cost, list(route) return best, best_route dist = [ [0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0], ] print(tsp_brute(dist)) # (80, [0, 1, 3, 2, 0])

Каждую перестановку мы ещё и суммируем за O(n)O(n), итого O(n⋅n!)O(n \cdot n!). В симметричном случае можно поделить на два: маршрут и его разворот имеют одинаковую длину. На асимптотику это не влияет.

Как быстро растёт факториал:

n(n − 1)! маршрутов
85 040
10362 880
13479 001 600
16≈ 1,3 · 10¹²
20≈ 1,2 · 10¹⁷

На Python перебор для n = 10 занимает доли секунды, при n = 13 уже минуты. Дальше без вариантов.

Перебор с отсечениями

Улучшаем перебор идеей ветвей и границ: строим маршрут поэлементно в духе бэктрекинга и бросаем ветку, как только частичная длина достигла лучшего найденного ответа. Рёбра положительные, поэтому продолжение такой ветки лучше уже не станет.

def tsp_backtrack(dist): n = len(dist) best = [math.inf, None] route = [0] used = [False] * n used[0] = True def dfs(cost): if cost >= best[0]: return # уже не лучше рекорда — отсекаем if len(route) == n: total = cost + dist[route[-1]][0] if total < best[0]: best[0], best[1] = total, route + [0] return last = route[-1] # сначала пробуем ближние города: рекорд найдётся раньше for nxt in sorted(range(n), key=lambda v: dist[last][v]): if not used[nxt]: used[nxt] = True route.append(nxt) dfs(cost + dist[last][nxt]) route.pop() used[nxt] = False dfs(0) return best[0], best[1] print(tsp_backtrack(dist)) # (80, [0, 1, 3, 2, 0])

Два приёма делают отсечение эффективным. Первый: перебирать сначала ближайшие города, тогда хороший рекорд появляется рано и режет больше веток. Второй, следующий по силе: вместо «частичная длина ≥ рекорда» использовать нижнюю оценку остатка, например вес минимального остовного дерева по непосещённым городам. Промышленные точные солверы устроены именно так, только оценки у них гораздо сильнее.

В худшем случае это всё равно O(n!)O(n!). На случайных точках с n = 10 отсечения ускоряют перебор примерно вдвое, но на n = 13 счёт снова идёт на секунды и минуты. Отсечения хороши как ответ «что сделать, если динамика не лезет по памяти», а не как основное решение.

Хелд–Карп: динамика по подмножествам

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

Множество кодируем битовой маской. Получаем 2ⁿ · n состояний вместо n! маршрутов. Алгоритм опубликовали в 1962 году независимо Беллман и Хелд с Карпом.

Сама техника, восходящая (bottom-up) реализация dp[mask][last] и восстановление пути через массив предков подробно разобраны в статье ДП по подмножествам. Здесь покажем другой вариант записи, который удобно писать на собеседовании: нисходящий, с мемоизацией и восстановлением маршрута без отдельного массива предков.

Состояние. go(mask, last) — минимальная длина оставшейся части маршрута: мы стоим в last, посещены города из mask, нужно обойти остальные и вернуться в 0.

Переход. Перебираем следующий город nxt вне маски:

go(mask,last)=min⁡nxt∉mask(dist[last][nxt]+go(mask∪{nxt},nxt))go(mask, last) = \min_{nxt \notin mask} \big( dist[last][nxt] + go(mask \cup \{nxt\}, nxt) \big)

База. Если посещены все, осталось вернуться: go(full, last) = dist[last][0].

from functools import lru_cache def held_karp(dist): n = len(dist) full = (1 << n) - 1 @lru_cache(maxsize=None) def go(mask, last): """(стоимость, следующий город): как из last обойти всё, чего нет в mask, и вернуться в 0.""" if mask == full: return dist[last][0], 0 best = (math.inf, -1) for nxt in range(n): if not mask & (1 << nxt): cost = dist[last][nxt] + go(mask | (1 << nxt), nxt)[0] if cost < best[0]: best = (cost, nxt) return best total = go(1, 0)[0] # восстановление: идём по сохранённым «следующим» городам route, mask, last = [0], 1, 0 while mask != full: last = go(mask, last)[1] route.append(last) mask |= 1 << last route.append(0) return total, route print(held_karp(dist)) # (80, [0, 1, 3, 2, 0])

Трюк с восстановлением: функция возвращает не только стоимость, но и лучший следующий шаг. Поскольку результаты закэшированы, повторный проход от (1, 0) по этим шагам ничего не пересчитывает и даёт маршрут за O(n)O(n).

Разбор на примере

Посмотрим, что лежит в кэше для матрицы из четырёх городов. Маску пишем как множество, go(S, v) — сколько ещё идти, если посещено S и мы стоим в v.

Посещены все — осталось вернуться в 0:

СостояниеЗначение
go({0,1,2,3}, 1)dist[1][0] = 10
go({0,1,2,3}, 2)dist[2][0] = 15
go({0,1,2,3}, 3)dist[3][0] = 20

Посещены три города — выбора уже нет, остался один:

СостояниеХодЗначение
go({0,1,2}, 1)→ 325 + 20 = 45
go({0,1,2}, 2)→ 330 + 20 = 50
go({0,1,3}, 1)→ 235 + 15 = 50
go({0,1,3}, 3)→ 230 + 15 = 45
go({0,2,3}, 2)→ 135 + 10 = 45
go({0,2,3}, 3)→ 125 + 10 = 35

Посещены два — здесь впервые выбираем:

  • go({0,1}, 1) = min(35 + 50, 25 + 45) = 70, лучше идти в 3;
  • go({0,2}, 2) = min(35 + 45, 30 + 35) = 65, лучше идти в 3;
  • go({0,3}, 3) = min(25 + 50, 30 + 45) = 75, ничья.

Старт: go({0}, 0) = min(10 + 70, 15 + 65, 20 + 75) = 80. Два варианта дают 80 — это один и тот же цикл 0-1-3-2-0, пройденный в разные стороны. Код берёт первый строго лучший, поэтому выводит [0, 1, 3, 2, 0].

На четырёх городах экономия незаметна, но уже при пяти она видна: префиксы 0-1-2-3 и 0-2-1-3 приходят в одно и то же состояние ({0,1,2,3}, 3). Перебор продолжил бы каждый из них отдельно, а динамика оставляет только более короткий и решает хвост один раз. Чем больше n, тем больше префиксов сливается в одно состояние: n!n! маршрутов сжимаются до 2n⋅n2^n \cdot n состояний.

Сложность

Состояний 2n⋅n2^n \cdot n (на деле вдвое меньше: бит города 0 всегда установлен). Из каждого перебираем n переходов. Итого:

  • время O(2n⋅n2)O(2^n \cdot n^2);
  • память O(2n⋅n)O(2^n \cdot n).

Для n = 16 это около 16 миллионов элементарных шагов, и на Python наш вариант укладывается в секунду. Рост от n!n! к 2n2^n огромный, но экспонента остаётся экспонентой: каждый новый город примерно удваивает и время, и память. На C++ разумный потолок n ≈ 20–23, на Python — около 16–18, дальше упираемся в память lru_cache. Для больших n переходят на bottom-up с плоским массивом, как в статье про битмаски.

Путь без возврата

Если возвращаться не нужно, меняются две строчки: база становится нулём, а старт перебирается.

def shortest_hamiltonian_path(dist): n = len(dist) full = (1 << n) - 1 @lru_cache(maxsize=None) def go(mask, last): if mask == full: return 0 # возвращаться не нужно return min(dist[last][nxt] + go(mask | (1 << nxt), nxt) for nxt in range(n) if not mask & (1 << nxt))
# старт в любом городе
return min(go(1 << s, s) for s in range(n))

print(shortest_hamiltonian_path(dist)) # 50: маршрут 2-0-1-3


Здесь бит старта уже не всегда установлен, поэтому состояний честно $2^n \cdot n$.

## Где TSP прячется в задачах

На LeetCode слова «коммивояжёр» почти не встретишь, но каркас узнаётся по ограничению `n ≤ 12–20` и фразе «посетить всех»:

- **847. Shortest Path Visiting All Nodes.** Граф невзвешенный, вершины можно посещать повторно. Состояние то же, `(mask, node)`, но вместо ДП работает [BFS](/blog/dfs-bfs-algorithms) по этим состояниям, стартующий сразу из всех вершин.
- **943. Find the Shortest Superstring.** «Расстояние» от слова `a` до слова `b` — сколько символов добавится, если приклеить `b` после `a` с максимальным перекрытием. Дальше это асимметричный кратчайший гамильтонов путь, плюс восстановление ответа.
- **Доставка с обязательными точками.** Сначала [Дейкстрой](/blog/dijkstra-algorithm) или BFS считаем попарные расстояния между k ключевыми точками на большой карте, затем Хелд–Карп по k точкам. Типичная ошибка — пытаться засунуть всю карту в маску.

## Эвристики: когда городов много

Для сотен и тысяч городов точный ответ не нужен и недостижим. Нужен хороший маршрут быстро. Стандартная связка: построить маршрут жадно и улучшить его локальным поиском.

### Ближайший сосед

[Жадный](/blog/greedy-algorithm) алгоритм: из текущего города идём в ближайший непосещённый.

```python
def route_length(dist, route):
    return sum(dist[a][b] for a, b in zip(route, route[1:]))


def nearest_neighbor(dist, start=0):
    n = len(dist)
    route = [start]
    visited = {start}
    while len(route) < n:
        last = route[-1]
        nxt = min((v for v in range(n) if v not in visited),
                  key=lambda v: dist[last][v])
        route.append(nxt)
        visited.add(nxt)
    route.append(start)
    return route

Время O(n2)O(n^2). Проблема видна на примере: жадность обходит удобный кластер, а в конце вынуждена возвращаться через всю карту длинными рёбрами.

points = [(7, 2), (8, 3), (5, 4), (5, 0), (7, 5), (5, 1), (6, 7), (5, 2)] d = [[math.dist(p, q) for q in points] for p in points] nn = nearest_neighbor(d) print(nn, round(route_length(d, nn), 2)) # [0, 1, 4, 2, 7, 5, 3, 6, 0] 22.06 print(round(held_karp(d)[0], 2)) # 15.88

Жадный маршрут почти на 40% длиннее оптимального: сначала он ушёл наверх к точке (7, 5), потом спустился вниз до (5, 0) и последним ребром прыгнул через всю карту к (6, 7). На случайных точках разрыв обычно меньше, около 10–25%, но гарантий никаких: известны примеры, где жадность хуже оптимума в Θ(log⁡n)\Theta(\log n) раз.

2-opt

Локальное улучшение: берём два ребра маршрута a→b и c→d, удаляем их и соединяем концы крест-накрест: a→c и b→d. Чтобы маршрут остался циклом, участок от b до c нужно развернуть.

до:     a → b → … → c → d
после:  a → c → … → b → d      (участок b…c развёрнут)

Если новая пара рёбер короче старой, маршрут стал лучше. Повторяем, пока улучшения находятся. На плоскости это ровно «распутывание» самопересечений: в оптимальном евклидовом маршруте рёбра никогда не пересекаются, и 2-opt устраняет каждое пересечение.

def two_opt(dist, route): route = route[:] n = len(route) - 1 # маршрут замкнут: route[0] == route[-1] improved = True while improved: improved = False for i in range(1, n - 1): for j in range(i + 1, n): a, b = route[i - 1], route[i] c, d = route[j], route[j + 1] # было a-b ... c-d, станет a-c ... b-d delta = dist[a][c] + dist[b][d] - dist[a][b] - dist[c][d] if delta < -1e-9: route[i:j + 1] = reversed(route[i:j + 1]) improved = True return route better = two_opt(d, nn) print(better, round(route_length(d, better), 2)) # [0, 3, 5, 7, 2, 6, 4, 1, 0] 15.88

На нашем примере 2-opt из жадных 22,06 получил оптимальные 15,88.

Что важно в коде:

  • Изменение длины считаем за O(1)O(1). Меняются только два ребра, поэтому пересчитывать весь маршрут не нужно. Это превращает проход в O(n2)O(n^2), а не O(n3)O(n^3).
  • Разворот корректен только для симметричной матрицы. В асимметричной задаче развёрнутый участок проходится в обратную сторону и меняет длину. Там используют ходы без разворотов, например Or-opt (перенос цепочки из 1–3 городов в другое место).
  • Сравнение с допуском. С вещественными расстояниями без -1e-9 алгоритм может бесконечно менять местами рёбра, разница длин которых — ошибка округления.

Число проходов теоретически не ограничено полиномом, но на практике их немного. На 1000 случайных точек наш Python-код улучшает жадный маршрут примерно на 13% за секунду.

Насколько это хорошо

Прогнали на 30 наборах по 12 случайных точек на плоскости и сравнили с точным ответом Хелда–Карпа:

МетодСреднее отношение к оптимумуХудший случай в выборке
Ближайший сосед1,111,35
Ближайший сосед + 2-opt1,011,06
Обход MST1,201,36

Это эксперимент, а не теорема: на других распределениях цифры будут другими. Но картина типичная: 2-opt даёт огромный выигрыш при тривиальном коде.

Обход минимального остовного дерева: гарантия 2·OPT

Эвристики выше работают хорошо, но ничего не обещают. Есть простой алгоритм с доказуемой гарантией для метрического случая:

  1. Строим минимальное остовное дерево.
  2. Обходим его в прямом порядке (preorder) и выписываем вершины.
  3. Замыкаем маршрут.
def mst_tour(dist): n = len(dist) in_tree = [False] * n best = [math.inf] * n parent = [-1] * n children = [[] for _ in range(n)] best[0] = 0 for _ in range(n): # Прим за O(n²) u = min((v for v in range(n) if not in_tree[v]), key=lambda v: best[v]) in_tree[u] = True if parent[u] != -1: children[parent[u]].append(u) for v in range(n): if not in_tree[v] and dist[u][v] < best[v]: best[v], parent[v] = dist[u][v], u route, stack = [], [0] # прямой обход дерева while stack: u = stack.pop() route.append(u) stack.extend(reversed(children[u])) return route + [0] m = mst_tour(d) print(m, round(route_length(d, m), 2)) # [0, 1, 4, 6, 7, 5, 3, 2, 0] 19.81

Почему не хуже двух оптимумов — короткое доказательство, которое хорошо звучит на собеседовании:

  • Если из оптимального маршрута выкинуть одно ребро, получится остовное дерево (путь). Значит, MST≤OPTMST \le OPT.
  • Обход дерева «туда и обратно» по каждому ребру имеет длину 2⋅MST2 \cdot MST.
  • Прямой обход пропускает повторные посещения и идёт к следующей вершине напрямую. По неравенству треугольника прямой путь не длиннее обходного. Итого маршрут ≤2⋅MST≤2⋅OPT\le 2 \cdot MST \le 2 \cdot OPT.

Улучшение этой идеи — алгоритм Кристофидеса (1976): к дереву добавляется минимальное совершенное паросочетание на вершинах нечётной степени, и гарантия становится 1,5. Писать его на собеседовании не просят, но знать название и число полезно.

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

Что используют на практике

Для реальных задач маршрутизации берут готовое: солвер Concorde для точного решения на тысячах городов, эвристику Лина–Кернигана (обобщение 2-opt на k рёбер) и её реализацию LKH, библиотеку Google OR-Tools для задач маршрутизации транспорта с окнами времени и вместимостью. Самописный 2-opt — это хорошая стартовая точка и честный ответ на собеседовании, но не продакшн-решение для логистики.

Типичные ошибки

Перебор стартового города. Начало цикла не влияет на длину. Фиксируйте город 0, иначе работы в n раз больше.

Забыли ребро возврата. И в переборе, и в базе ДП нужно прибавить dist[last][0]. Без него решается задача о пути, и ответ получается меньше правильного.

Маска не содержит стартовый город. Если начать с go(0, 0), алгоритм может «посетить» город 0 ещё раз и вернуться в него дважды.

Хелд–Карп по всей карте. Маска строится по обязательным точкам, а не по всем вершинам графа. Расстояния между точками сначала считаются кратчайшими путями.

2-opt на асимметричной матрице. Разворот участка меняет его длину, и формула delta перестаёт быть верной.

Рекурсия и память в Python. Для n = 18 в кэше несколько миллионов записей, это сотни мегабайт. Если упираетесь, переходите на итеративный dp в списке массивов или в numpy.

Как отвечать на собеседовании

Хорошая структура ответа:

  1. Уточнить: цикл или путь, симметричные ли расстояния, какое n.
  2. Назвать перебор O(n!)O(n!) и сразу сказать, почему он не подходит при n > 10–11.
  3. Сформулировать состояние (mask, last) и объяснить, почему порядок внутри маски не важен. Это главный момент, на котором проверяют понимание.
  4. Написать Хелда–Карпа, назвать O(2n⋅n2)O(2^n \cdot n^2) по времени и O(2n⋅n)O(2^n \cdot n) по памяти, показать восстановление маршрута.
  5. На вопрос «а если городов 10 000?» — жадный старт, 2-opt, оценка через MST и упоминание Кристофидеса и готовых солверов.

Если интервьюер спрашивает «можно ли быстрее точно», честный ответ: для общего случая полиномиального алгоритма не известно, задача NP-трудная, а O(2n⋅n2)O(2^n \cdot n^2) — лучший классический точный результат, которым пользуются на практике для малых n.

Вопросы вдогонку

«Почему нельзя хранить только маску, без текущего города?» Потому что стоимость следующего шага зависит от того, где мы стоим. Два маршрута с одинаковым множеством, но разным концом нельзя сравнивать между собой.

«Как сэкономить память?» Переходы идут только от масок с k битами к маскам с k + 1 битами. Можно хранить два слоя по числу бит, но перебор масок по слоям неудобен, и в реальном коде обычно просто берут компактный массив чисел вместо списков Python.

«Что если некоторых дорог нет?» Ставим вместо них бесконечность. Если ответ остался бесконечным, гамильтонова цикла не существует — та же динамика отвечает на вопрос о его наличии.

«Можно ли распараллелить?» Все маски с одинаковым числом бит независимы друг от друга, поэтому слой можно считать параллельно. Экспоненту это не убирает, но константу уменьшает.

Что запомнить

  • TSP — поиск гамильтонова цикла минимального веса, задача NP-трудная.
  • Перебор: (n−1)!(n-1)! маршрутов, годится до n ≈ 10.
  • Хелд–Карп: состояние «множество посещённых + текущий город», O(2n⋅n2)O(2^n \cdot n^2) времени, O(2n⋅n)O(2^n \cdot n) памяти, предел около n = 20.
  • Восстановление маршрута: храним лучший следующий шаг или предка.
  • Ближайший сосед даёт быстрый, но неточный маршрут; 2-opt распутывает пересечения и почти всегда приближает к оптимуму на несколько процентов.
  • При неравенстве треугольника обход MST гарантирует ≤2⋅OPT\le 2 \cdot OPT, Кристофидес — ≤1,5⋅OPT\le 1{,}5 \cdot OPT.

Потренироваться в спокойной обстановке

Все задачи