Задача коммивояжёра

Облететь все 214 городов мира с населением от двух миллионов и вернуться домой, пролетев как можно меньше. Разных маршрутов — 213!/2, около 5·10⁴⁰⁴. Точная таблица по маскам справляется с двумя десятками точек, а здесь их в десять раз больше. При этом развозка, сверление плат и сборка заказов на складе каждый день упираются в такие задачи на тысячах точек — и решаются за секунды. Не точно, но с гарантией: вместе с маршрутом считают число, короче которого маршрута быть не может. Ниже это видно на карте.

Ближайший сосед — «каждый раз в ближайший ещё не посещённый город» — пролетает 151 412 км. Правка 2-opt и Or-opt укорачивает маршрут до 136 783 км. Нажмите «Ещё 10 стартов»: лучший из одиннадцати запусков — 128 435 км. Снизу растёт нижняя оценка, 120 336 км: короче ни один маршрут не бывает. Где-то в этой вилке лежит оптимум, и, ничего не зная о нём, мы уже знаем, что наш маршрут хуже лучшего не больше чем на 6,7 %. Переключите набор на миллионники — там 573 города, и всё работает так же быстро.

Идея

Задача коммивояжёра — найти кратчайший замкнутый маршрут, проходящий все точки по одному разу. Почему она трудна и что из этого следует, подробно разобрано в главах курса о P и NP и «Экспедиция коммивояжёра»: быстрого точного алгоритма для неё, по всей видимости, нет, а точная динамика стоит 2ⁿ·n². Эта статья — о том, что делают с такой задачей на практике.

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

Маршрут и его правка

Ближайший сосед строит маршрут за O(n²): из текущего города в ближайший непосещённый. Начало у него хорошее, конец плохой: последние города остаются разбросанными по карте, и к ним приходится лететь далеко. На случайных точках он в среднем на четверть длиннее нижней оценки, у нас — на 26 %.

2-opt берёт два ребра маршрута, a–b и c–e, и заменяет их на a–c и b–e; кусок маршрута между ними при этом разворачивается. Ход выгоден, если новые рёбра в сумме короче старых. На плоскости два пересекающихся ребра всегда можно так распутать, поэтому у плоского маршрута, который 2-opt больше не улучшает, самопересечений нет. Or-opt вынимает кусок из одного–трёх городов и вставляет его в другое место, как есть или задом наперёд: это то, что 2-opt одним ходом сделать не может.

Перебор всех пар рёбер стоит n²/2 проверок на проход, а проходов много. Два приёма делают правку почти линейной. Первый — списки ближайших соседей: для каждого города заранее выписаны десять ближайших, и новое ребро ищется только среди них, причём перебор обрывается, как только новое ребро становится не короче старого. Второй — биты «не смотреть»: город, от которого улучшение не нашлось, больше не проверяется, пока рядом с ним в маршруте ничего не поменяется. Города ждут проверки в очереди, и каждый ход ставит в неё четыре города, чьи рёбра он поменял.

Почему так можно

Это наблюдение Линя и Кернигана 1973 года; потеряться при нём могут только ходы, где нужный сосед не попал в десятку ближайших. Биты «не смотреть» — эвристика Бентли 1992 года без гарантий: город, рядом с которым ничего не поменялось, мог бы найти ход через изменения далеко от себя. На практике такие потери — доли процента.

Голое 1-дерево — слабая оценка: у него бывают города с тремя и более рёбрами и висячие листья. Надбавки чинят это. Город, у которого в дереве больше двух рёбер, получает надбавку побольше, лист — поменьше, и дерево следующего шага сдвигается к маршруту. Как подбирать шаг надбавок и почему оценка растёт, подробно разобрано в главе «Экспедиция коммивояжёра». Само дерево — алгоритм Прима за O(n²), по одному на шаг. Размер шага зависит от длины уже известного маршрута, поэтому подбор, начатый от разных маршрутов, приходит к разным оценкам, и верна каждая. От первого маршрута у нас выходит 120 336 км, от лучшего из одиннадцати — 120 076; сцена запоминает наибольшую из найденных.

Код

Листинг повторяет сцену шаг в шаг. Расстояния — по дуге большого круга, округлённые до километра, чтобы Python, Go и сцена складывали одни и те же числа. Маршрут хранится массивом городов и массивом их мест; разворот куска переставляет только меньшую из двух частей круга. Нижняя оценка считает остов Примом на каждом шаге и сдвигает надбавки на величину, пропорциональную (степень − 2).

2-opt over all pairs of edges: 136116 km, 90308 checks
2-opt over the 10 nearest neighbours: 140096 km, 785 checks, 44 moves
then Or-opt and 2-opt in turn: 136783 km
the best of 11 starts: 128435 km
lower bound, Held-Karp 1-trees: 120336 km

Полный 2-opt нашёл маршрут немного короче, но сделал 90 308 проверок против 785 — в сто с лишним раз больше. Списки соседей теряют три процента, которые Or-opt почти целиком возвращает. Самое большое улучшение дают разные старты: локальный поиск застревает в разных местах, и из одиннадцати попыток лучшая на шесть процентов короче первой.

Сколько это стоит

Таблица расстояний и ближайший сосед — O(n²). Списки соседей — O(n² log k) в лоб, а с k-d деревом — около O(n log n). Проход 2-opt по всем парам — O(n²) проверок, и проходов тем больше, чем больше точек. Со списками соседей и битами «не смотреть» на город приходится десяток проверок за раз, и вся правка растёт почти линейно. Замер — только правка, от одного и того же маршрута ближайшего соседа на случайных точках:

Перебор всех пар растёт быстрее квадрата: на 800 точках в Python он медленнее списков соседей больше чем в сто раз. Списки растут почти линейно, и на миллионе точек эта разница — между минутами и неделями.

Сколько стоит качество, хорошо видно по большому сравнению Дэвида Джонсона и Лайла Макгеоча 1997 года на случайных точках плоскости, в процентах над нижней оценкой Хелда — Карпа: ближайший сосед — около 25 %, алгоритм Кристофидеса — около 10 %, 2-opt со списками соседей — около 5 %, 3-opt — около 3 %, алгоритм Линя — Кернигана — 1–2 % от оптимума. Наш облёт хуже: города мира собраны в плотные кучи, разделённые океанами, и поиск, застрявший в одном порядке обхода континентов, сам из него не выберется.

Где правка ломается

Локальный оптимум. Маршрут, который никакой ход 2-opt или Or-opt не улучшает, может быть далёк от лучшего: в нашем облёте один запуск остановился на 136 783 км, другой — на 128 435. Помогают разные старты, ходы покрупнее (3-opt, Линь — Керниган) и отжиг, который иногда разрешает шаг в худшую сторону. Гарантии ни один из них не даёт — гарантию даёт только нижняя оценка.

Несимметричные расстояния. По улицам с односторонним движением путь из a в b не равен пути из b в a. Ход 2-opt разворачивает кусок маршрута, и вся его длина меняется — оценить ход по четырём рёбрам уже нельзя. В таких задачах полагаются на ходы без разворота, вроде Or-opt, и на ходы 3-opt, сохраняющие направление.

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

Где работает

Развоз и сбор. Курьерские службы, мусоровозы, инкассация — это коммивояжёр с добавками: несколько машин, вместимость, окна времени. Чистая задача — их сердцевина, и её эвристики — 2-opt, Or-opt, обмены кусками между маршрутами — стоят внутри решателей маршрутов.

Микросхемы и станки. Сверление отверстий в плате, проход резака, рисование лазером — точки, которые инструмент обходит, и порядок, в котором он движется без дела. Задачу на 85 900 точках из схемы микросхемы решатель Concorde решил точно в 2006 году.

Карта мира целиком. Задача World TSP — 1 904 711 населённых пунктов Земли. Лучший известный маршрут нашёл Юити Нагата в октябре 2025 года, а лучшая нижняя оценка, посчитанная Concorde ещё в 2007-м, отстаёт от него на 0,047 %. Оптимум неизвестен до сих пор, но вилка в полсотни тысячных процента — это ровно то, что показывает сцена в начале статьи, только в масштабе планеты.

История

2-opt предложил Г. А. Кроус в 1958 году; сам ход замены двух рёбер упоминал Меррилл Флуд двумя годами раньше. В 1970–1971 годах Майкл Хелд и Ричард Карп придумали 1-деревья с надбавками — оценку, которая до сих пор стоит внутри точных решателей. В 1973 году Шен Линь и Брайан Керниган описали ход переменной глубины, который больше пятнадцати лет оставался лучшей эвристикой; в 2000 году Кельд Хельсгаун развил его в программу LKH, одну из самых сильных эвристик и сегодня. Or-opt — из диссертации Ильхана Ора 1976 года о логистике банков крови. Биты «не смотреть» и быстрые списки соседей на k-d деревьях, без которых локальный поиск не дотянулся бы до миллионов точек, описал Джон Бентли в 1992 году. Алгоритм Кристофидеса с гарантией в полтора оптимума продержался рекордом 44 года: в 2020 году Анна Карлин, Натан Кляйн и Шаян Овейс Гаран улучшили его до 3/2 − ε, где ε больше 10⁻³⁶, — улучшение крошечное, но первое.

Задачи

В первой задаче маршрут обязан идти сначала только на восток, потом только на запад, — и от такого ограничения коммивояжёр становится динамикой за O(n²). Во второй нужно облететь до полутора тысяч городов, уложившись в 110 % от эталонного маршрута: ближайшего соседа для этого мало.