Коммивояжёр и NP-трудность

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

NP-трудная задача — задача, для которой не известно алгоритма, гарантированно находящего точный оптимум за полиномиальное время; время точного решения растёт экспоненциально.

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

Дано $n$ городов и расстояния между ними. Нужно найти кратчайший замкнутый маршрут, проходящий через каждый город ровно раз. Решений — все перестановки городов, их $(n-1)!/2$. Для $n=10$ это $\sim181$ тысяча, для $n=20$ — больше $10^{16}$, для $n=60$ перестановок больше, чем атомов во Вселенной. Полный перебор обречён.

Лёгкая проверка, трудный поиск

Парадокс трудных задач: проверить данный маршрут (сложить расстояния) элементарно — $O(n)$. А найти лучший — невероятно трудно. Это и есть суть класса NP: решение проверяется быстро, но пространство решений экспоненциально. Коммивояжёр и рюкзак (в общей форме) — NP-трудные; для них не известно (и, по гипотезе $P\ne NP$, скорее всего не существует) быстрого точного алгоритма.

Рост перебора в числах

import math

print(f"{'городов':>8} | {'маршрутов (n-1)!/2':>22}")
for n in [5, 8, 10, 15, 20]:
    routes = math.factorial(n - 1) // 2
    print(f"{n:8d} | {routes:22d}")

Вывод:

 городов |     маршрутов (n-1)!/2
       5 |                     12
       8 |                   2520
      10 |                 181440
      15 |            43589145600
      20 |      60822550204416000

Каждые несколько добавленных городов умножают число маршрутов на порядки — наглядная экспонента. Перебор реально работает лишь до $n\approx12$.

Что делать с трудными задачами

Подход	Что даёт	Когда
Перебор	Точный оптимум	Крошечные $n$ ($\le12$)
Ветви и границы	Точный оптимум, отсекая бесперспективные ветви	Малые-средние $n$
Эвристики (ближайший сосед, 2-opt)	Хорошее решение быстро	Большие $n$
Метаэвристики (отжиг, ГА)	Очень хорошее решение	Большие $n$, есть время
Приближённые алгоритмы	Решение с гарантией «не хуже чем в $k$ раз»	Когда нужна гарантия качества

Ветви и границы — идея

Метод ветвей и границ (branch and bound) даёт точный ответ, но умнее перебора. Он строит дерево частичных маршрутов и для каждого считает нижнюю границу (оптимистичную оценку лучшего возможного продолжения). Если граница хуже уже найденного полного маршрута, всю ветвь отсекают, не разворачивая. Так дерево обрезается, и часто удаётся решить точно куда большие задачи, чем позволяет голый перебор.

Как работает под капотом

Граница между «лёгкими» (полиномиальными, класс P) и «трудными» (NP-трудными) задачами — центральный вопрос информатики ($P$ против $NP$, одна из задач тысячелетия). Практический вывод для оптимизатора прост: распознав NP-трудность задачи, не тратьте силы на поиск быстрого точного алгоритма (его, вероятно, нет) — переходите к ветвям и границам для умеренных размеров или к (мета)эвристикам для больших. Именно поэтому метаэвристики из прошлого раздела так важны: они — рабочий инструмент против комбинаторного взрыва.

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

Перебор для больших $n$. Уже при $n>12$ он безнадёжен — сразу берите эвристики.
Ждать точного оптимума за разумное время. Для NP-трудных задач большого размера это нереалистично; цельтесь в «достаточно хорошо».
Путать «трудно проверить» и «трудно найти». Проверка маршрута тривиальна; трудность — в поиске лучшего среди экспоненты вариантов.

Итоги

Коммивояжёр — NP-трудная задача: $(n-1)!/2$ маршрутов, перебор взрывается.
В NP-задачах решение проверяется быстро, но пространство поиска экспоненциально.
Точно — ветви и границы (умеренные $n$); для больших — эвристики и метаэвристики.