NP-полнота, приближённые и эвристические алгоритмы

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

Эта статья — про то, как перестать гадать. Теория NP-полноты даёт инструмент, который превращает интуицию «кажется, это трудно» в доказательство: не «я не нашёл алгоритм», а «полиномиального алгоритма не существует, если только не рухнет P ≠ NP, над чем полвека безуспешно бьётся вся computer science». Это радикально меняет разговор с менеджером и, что важнее, меняет то, что вы пишете дальше.

Потому что вторая половина статьи — самая практическая. NP-трудность не означает «сдаться». Она означает сменить цель: вместо «оптимум за полином на всех входах» выбрать, чем пожертвовать — точностью, универсальностью или гарантией времени. Приближённые алгоритмы с доказанной оценкой, параметризованная сложность, ветвление с отсечением, SAT/MIP-солверы и метаэвристики — это всё разные ответы на один вопрос «чем жертвуем».

Предполагается, что вы знакомы с асимптотикой и доказательствами из Анализ алгоритмов, с жадностью из Жадные алгоритмы и с ДП из Динамическое программирование.

Часть I. Что значит «задача трудна»

Задачи разрешения, а не оптимизации

Первая техническая деталь, которая всех спотыкает: теория сложности говорит о задачах разрешения (decision problems) — тех, где ответ «да» или «нет». Не «найди кратчайший маршрут», а «существует ли маршрут длины ≤ k».

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

На практике это не ограничение: оптимизационная и разрешающая версии почти всегда полиномиально эквивалентны. Если умеете отвечать «есть ли маршрут ≤ k», то бинарным поиском по k (см. Бинарный поиск по ответу) находите оптимальное значение за O(log(сумма весов)) вызовов, а сам маршрут восстанавливаете самосводимостью: фиксируете первое ребро, спрашиваете, достижим ли тот же k в остатке.

Практический вывод: когда вы читаете «TSP NP-полна», формально имеется в виду TSP-DECISION. Оптимизационная версия — NP-трудна, но не «NP-полна», потому что она вообще не задача разрешения. Эта педантичность важна на собеседовании и неважна в коде.

P, NP и верификаторы

P — задачи разрешения, решаемые детерминированной машиной за время, полиномиальное от длины входа. Сортировка, кратчайшие пути, максимальный поток, проверка простоты (с 2002 года, AKS) — всё здесь.

NP — задачи, для которых ответ «да» можно проверить за полином, если кто-то подсказал сертификат (свидетельство). Не «решить», а именно «проверить».

Это ключевая интуиция, и она проще, чем недетерминированные машины Тьюринга:

Заметьте асимметрию: сертификат есть для ответа «да». Для ответа «нет» («формула невыполнима») короткого сертификата не видно — это и есть класс coNP, и вопрос «NP = coNP?» открыт независимо от «P = NP?».

P ⊆ NP тривиально: если можете решить за полином, сертификат не нужен. Обратное — главный открытый вопрос информатики, одна из задач тысячелетия с призом в миллион долларов.

Сведение: главный инструмент

Полиномиальное сведение по Карпу A ≤ₚ B — это функция f, вычислимая за полином, такая что x ∈ A ⟺ f(x) ∈ B. То есть вы переписываете вход задачи A во вход задачи B так, что ответ сохраняется.

Смысл: если A ≤ₚ B и B решается за полином, то и A решается за полином (переведите вход и вызовите решатель B). Контрапозиция и есть рабочий инструмент: если A трудна, то и B трудна.

Направление стрелки — источник 90% ошибок у новичков. Запомните формулу: чтобы доказать трудность B, сводите известную трудную задачу К вашей, а не наоборот. «Я свёл свою задачу к SAT» — это не доказательство трудности, это алгоритм решения (и очень хороший, к нему вернёмся). «Я свёл 3-SAT к своей задаче» — вот это доказательство.

NP-трудная задача: любая задача из NP сводится к ней. NP-полная: NP-трудная И сама лежит в NP. Проблема остановки NP-трудна (к ней всё сводится), но не NP-полна — она даже не разрешима.

Теорема Кука–Левина и генеалогия трудности

Замкнутый круг («чтобы доказать трудность, нужна известная трудная задача») разорвали независимо Стивен Кук (1971) и Леонид Левин (1973): SAT NP-полна. Доказательство прямое — работу любой недетерминированной машины Тьюринга за полиномиальное число шагов кодируют булевой формулой, где переменные описывают содержимое ленты в каждый момент, а дизъюнкты — корректность переходов. Формула выполнима тогда и только тогда, когда машина принимает вход.

Через год Ричард Карп (1972) показал 21 задачу, NP-полную по сведению от SAT, и лавина пошла. Сегодня каталог насчитывает тысячи задач — классический справочник Garey & Johnson, «Computers and Intractability» (1979) до сих пор не устарел.

Вот скелет «генеалогического дерева» — типичные маршруты сведений, которые полезно знать наизусть, потому что почти любая ваша задача похожа на одну из них:

Рецепт: как доказать, что ваша задача NP-трудна

Реальный, применимый за один рабочий день алгоритм действий:

1. Сформулируйте задачу разрешения. Уберите «минимизировать», добавьте порог k.
2. Покажите принадлежность NP (если хотите полноту, а не только трудность): опишите сертификат и проверку за полином. Обычно это три строки.
3. Выберите кандидата на источник. Смотрите на структуру:
   • есть выбор «взять/не взять» с числовым бюджетом → Subset Sum / Knapsack / Partition;
   • есть попарные конфликты («эти двое не вместе») → Independent Set / 3-COLORING;
   • нужно покрыть все элементы минимумом сущностей → Set Cover / Vertex Cover;
   • нужен обход/порядок всех объектов → Hamiltonian Path / TSP;
   • логические ограничения «или/не» → 3-SAT напрямую.
4. Постройте отображение f входа источника во вход вашей задачи. Это и есть творчество: «гаджеты» — маленькие конструкции, кодирующие переменную или клаузу.
5. Докажите две импликации. x ∈ A ⟹ f(x) ∈ B и f(x) ∈ B ⟹ x ∈ A. Вторая почти всегда сложнее и почти всегда именно там ошибка: нужно показать, что «паразитных» решений в B, не отвечающих ни одному решению A, не бывает.
6. Проверьте полиномиальность f. Если ваше сведение строит 2^n вершин — это не сведение.

Классический пример, который стоит уметь воспроизвести на доске — 3-SAT ≤ₚ Independent Set:

Дана 3-CNF формула с m клаузами.
Для каждой клаузы (l1 ∨ l2 ∨ l3) строим треугольник из 3 вершин,
    помеченных литералами.  → 3m вершин
Дополнительно соединяем ребром каждую пару вершин с противоречивыми
    метками: x и ¬x.
Вопрос: есть ли независимое множество размера m?

(⟹) Формула выполнима ⟹ в каждой клаузе есть истинный литерал;
     берём по одной такой вершине из треугольника. Внутри треугольника
     конфликта нет (взяли одну), между треугольниками — тоже, потому что
     все взятые литералы истинны одновременно, значит не противоречивы.

(⟸) Независимое множество размера m ⟹ ровно по одной вершине
     из каждого треугольника (иначе не хватит на m). Присваиваем этим
     литералам True — согласованно, так как противоречивые пары соединены.
     Каждая клауза получила истинный литерал ⟹ формула выполнима.

Обратите внимание на структуру: гаджет-треугольник кодирует «выбери ровно один», рёбра согласованности кодируют «не противоречь себе». Почти все сведения устроены так же.

Чего NP-полнота НЕ значит

Это место, где практики теряют больше всего времени и денег.

• «NP-полная» ≠ «нерешаемая». Это утверждение о худшем случае при n → ∞. Промышленные SAT-солверы ежедневно решают формулы с миллионами переменных. Реальные входы обладают структурой, которой нет у худших случаев.
• «NP-полная» ≠ «экспоненциальная». Никто не доказал нижнюю оценку 2^Ω(n) для SAT. Это гипотеза — ETH/SETH, более сильная, чем P ≠ NP, и на ней держится современная тонко-зернистая теория сложности.
• Псевдополиномиальность ≠ полиномиальность. ДП для Knapsack работает за O(nW) — и это не противоречит NP-полноте, потому что W записывается log W битами: время экспоненциально от длины входа. Задачи, где такое ДП есть, называют слабо NP-трудными (Knapsack, Subset Sum, Partition); задачи без него — сильно NP-трудными (TSP, 3-COLORING, Bin Packing при унарном кодировании).
• Малое n меняет всё. 2^n при n = 25 — это 33 миллиона, доли секунды. Прежде чем городить эвристику, посчитайте фактический размер входа. «NP-полно» при n ≤ 20 означает «напиши перебор с отсечениями и иди дальше».
• NP-полнота — свойство задачи, а не входа. «Наш граф NP-полон» — бессмысленная фраза. Более того, на ограниченных классах входов задача часто становится полиномиальной: 3-COLORING тривиальна на деревьях, Independent Set полиномиален на интервальных и хордальных графах, Vertex Cover — на двудольных (теорема Кёнига + паросочетание, см. Остовные деревья и потоки).

Небольшая историческая перспектива — она полезна, чтобы понимать, откуда взялись современные инструменты:

Часть II. Что делать, когда задача NP-трудна

Доказали трудность — теперь надо поставлять фичу. Есть ровно четыре рычага, и надо осознанно выбрать, какой отпустить.

Дерево решений, которым я реально пользуюсь:

Рычаг 1: точные методы, которые всё же работают

DP по подмножествам (Held–Karp). Классика для TSP: O(2ⁿ·n²) времени вместо O(n!). Для n = 20 это ~400 млн операций — секунды.

def held_karp(dist):
    """Точный TSP через ДП по битмаске подмножеств.
    dist — квадратная матрица расстояний, старт и финиш в вершине 0.
    Время O(2^n · n^2), память O(2^n · n)."""
    n = len(dist)
    FULL = 1 << n
    INF = float("inf")
    # dp[mask][last] — минимальная стоимость пути, начавшегося в 0,
    # посетившего ровно вершины из mask и закончившегося в last
    dp = [[INF] * n for _ in range(FULL)]
    dp[1][0] = 0

    for mask in range(FULL):
        if not (mask & 1):          # вершина 0 всегда должна быть посещена
            continue
        for last in range(n):
            cur = dp[mask][last]
            if cur == INF or not (mask >> last) & 1:
                continue
            for nxt in range(n):
                if (mask >> nxt) & 1:
                    continue
                nmask = mask | (1 << nxt)
                cand = cur + dist[last][nxt]
                if cand < dp[nmask][nxt]:
                    dp[nmask][nxt] = cand

    return min(dp[FULL - 1][last] + dist[last][0] for last in range(1, n))

Тот же приём (2ⁿ вместо n!) закрывает Set Cover при малом универсуме, Bin Packing при малом числе предметов, задачи назначения с хитрыми ограничениями. Практический потолок в Python — n ≈ 20, на C++ с битовыми трюками — n ≈ 24–26.

Branch and bound. Идея: строим дерево решений, но в каждом узле считаем границу — оптимистичную оценку лучшего, что достижимо в этом поддереве. Если граница хуже уже найденного решения — поддерево отсекаем целиком.

BRANCH_AND_BOUND(задача):
    best = стоимость любого допустимого решения (жадность!)   # верхняя граница
    очередь = {корень}
    пока очередь не пуста:
        узел = извлечь (best-first по границе)
        если bound(узел) >= best:      # оптимистичная оценка уже хуже
            отбросить                  # ← вся сила метода здесь
        иначе если узел — лист:
            best = min(best, стоимость(узел))
        иначе:
            ветвление: зафиксировать одну переменную в 0 и в 1

Качество B&B определяется только двумя вещами: насколько туга граница и насколько хорошее стартовое решение. Для рюкзака граница — дробная релаксация (жадность по удельной ценности, ровно как в Жадные алгоритмы). Для TSP — вес MST на непосещённых вершинах плюс два минимальных ребра, или знаменитая 1-tree bound Хельда–Карпа с лагранжевой релаксацией, на которой построен Concorde.

Промышленные солверы — почти всегда правильный ответ. Это самый недооценённый пункт. Вместо своего B&B возьмите MIP-солвер (Gurobi, CPLEX, открытые HiGHS/SCIP) или CP-SAT из OR-Tools. Они содержат десятилетия инженерии: presolve, отсечения Гомори, эвристики поиска допустимого решения, рестарты, обучение конфликтов.

from ortools.sat.python import cp_model

def knapsack_exact(weights, values, capacity, time_limit_s=10.0):
    """0/1-рюкзак через CP-SAT: точный ответ или лучшее найденное + gap."""
    n = len(weights)
    model = cp_model.CpModel()
    x = [model.NewBoolVar(f"x[{i}]") for i in range(n)]
    model.Add(sum(weights[i] * x[i] for i in range(n)) <= capacity)
    model.Maximize(sum(values[i] * x[i] for i in range(n)))

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = time_limit_s
    solver.parameters.num_search_workers = 8        # параллельный портфель стратегий
    status = solver.Solve(model)

    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    chosen = [i for i in range(n) if solver.Value(x[i])]
    # ключевая для прода метрика: насколько мы далеки от доказанного оптимума
    gap = abs(solver.BestObjectiveBound - solver.ObjectiveValue()) / max(1.0, abs(solver.ObjectiveValue()))
    return {"items": chosen, "value": solver.ObjectiveValue(),
            "proven_optimal": status == cp_model.OPTIMAL, "gap": gap}

Главное, что даёт солвер и чего почти никогда не даёт своя эвристика, — сертификат качества: BestObjectiveBound показывает, что лучше этого не бывает в принципе. Ответ «нашли 98% от теоретического максимума за 10 секунд» — это то, с чем можно идти к бизнесу, в отличие от «наша эвристика что-то нашла».

SAT-солверы — вторая рабочая лошадь. Современный CDCL — не перебор, а обучающаяся машина: каждый тупик превращается в новую клаузу, отсекающую целый класс присваиваний.

Три механизма — обучение клауз (CDCL), эвристика активности VSIDS и агрессивные рестарты — и есть причина, по которой SAT «не работает» в теории и прекрасно работает на практике. Рекомендую SAT Competition и солвер CaDiCaL/Kissat Армина Бире как референс.

Рычаг 2: приближение с гарантией

Определение. Алгоритм — ρ-приближение для задачи минимизации, если для любого входа ALG ≤ ρ · OPT (для максимизации — ALG ≥ OPT/ρ). Гарантия должна выполняться на всех входах, а не в среднем. Именно это отличает приближённый алгоритм от эвристики.

Тонкость, которая ломает мозг новичкам: как доказать ALG ≤ 2·OPT, если OPT неизвестен? Ответ: через нижнюю границу. Находим величину LB, про которую доказуемо LB ≤ OPT, и показываем ALG ≤ 2·LB. Все доказательства ниже устроены ровно так.

Vertex Cover: 2-приближение из ниоткуда

def vertex_cover_2approx(edges):
    """Минимальное вершинное покрытие, гарантия ALG <= 2 * OPT.
    edges — список рёбер (u, v). Время O(E), память O(V)."""
    cover = set()
    for u, v in edges:
        if u not in cover and v not in cover:
            # ребро не покрыто ⇒ берём ОБА конца
            cover.add(u)
            cover.add(v)
    return cover

Четыре строки, а доказательство изящное. Рёбра, на которых мы срабатывали, попарно не имеют общих вершин — это паросочетание M. Любое покрытие обязано содержать хотя бы по одной вершине из каждого ребра M, значит OPT ≥ |M|. А мы взяли ровно 2|M| вершин. Итого ALG = 2|M| ≤ 2·OPT. Нижняя граница — размер паросочетания.

Типичная ошибка: «возьмём жадно вершину максимальной степени, это же умнее». Умнее выглядит, но гарантия у такого алгоритма — Θ(log n), то есть хуже, и есть явные контрпримеры. Красивая иллюстрация принципа: интуитивная жадность бывает хуже тупой, но доказуемой.

Metric TSP: MST даёт 2, Кристофидес даёт 1.5

Общий TSP не приближается вообще никак: если бы существовало ρ-приближение для любой константы ρ, им можно было бы решать Hamiltonian Cycle за полином. Но как только расстояния удовлетворяют неравенству треугольника (а в логистике и геометрии это почти всегда так), появляются приближения.

Доказательство целиком помещается в три строки: MST ≤ OPT (выкиньте ребро из оптимального цикла — получится остовное дерево), удвоение даёт эйлеров граф весом 2·MST, срезка повторов не увеличивает вес по неравенству треугольника. Итого ≤ 2·OPT.

Кристофидес (1976) заменяет удвоение на минимальное паросочетание вершин нечётной степени. Их чётное число, а вес паросочетания ≤ OPT/2 (оптимальный цикл распадается на два паросочетания на этих вершинах). Итого MST + OPT/2 ≤ 1.5·OPT. Этот результат простоял 44 года — до Karlin, Klein, Oveis Gharan (2020), которые получили 1.5 − ε с ε ≈ 10⁻³⁶. Практической ценности ноль, теоретический прорыв огромный.

Set Cover: жадность даёт ln n, и лучше нельзя

def greedy_set_cover(universe, subsets, costs=None):
    """Покрытие множества: жадный выбор по цене за новый элемент.
    subsets: dict name -> set. Гарантия H(n) ≈ ln n + 1 от оптимума.
    Время O(|subsets| · |universe|) при наивной реализации."""
    uncovered = set(universe)
    chosen = []
    while uncovered:
        best_name, best_ratio, best_gain = None, float("inf"), 0
        for name, s in subsets.items():
            gain = len(s & uncovered)
            if gain == 0:
                continue
            cost = 1.0 if costs is None else costs[name]
            ratio = cost / gain            # цена за один новый покрытый элемент
            if ratio < best_ratio:
                best_name, best_ratio, best_gain = name, ratio, gain
        if best_name is None:
            raise ValueError("универсум не покрывается данными подмножествами")
        chosen.append(best_name)
        uncovered -= subsets[best_name]
    return chosen

Гарантия H(n) = 1 + 1/2 + ... + 1/n ≈ ln n. Доказательство — «раскидать» стоимость шага по покрытым на нём элементам: когда осталось k непокрытых, оптимум покрывает их OPT множествами, значит нашлось множество с ценой ≤ OPT/k за элемент.

И самое интересное: улучшить нельзя. Feige (1998) и затем Dinur & Steurer (2014) показали, что (1 − o(1))·ln n — предел при P ≠ NP. То есть эта наивная жадность оптимальна как алгоритм. Знать такие результаты полезно: они экономят недели попыток «придумать что-то поумнее».

FPTAS: рюкзак с любой заданной точностью

Иерархия схем приближения:

FPTAS — лучшее, на что можно надеяться для NP-трудной задачи. Идея для рюкзака: классическое ДП по стоимости работает за O(n·ΣV); округлим стоимости так, чтобы их сумма стала полиномиальной, и потеряем контролируемо мало.

def knapsack_fptas(items, capacity, eps=0.1):
    """0/1-рюкзак: результат гарантированно >= (1 - eps) * OPT.
    items: [(weight, value)], целые неотрицательные.
    Время O(n^2 / eps), память O(n^2 / eps)."""
    usable = [(w, v) for (w, v) in items if w <= capacity and v > 0]
    if not usable:
        return 0, []

    n = len(usable)
    vmax = max(v for _, v in usable)
    K = eps * vmax / n                      # шаг округления
    scaled = [int(v / K) for _, v in usable]
    total = sum(scaled)                     # <= n * n/eps — полиномиально!

    INF = float("inf")
    # dp[i][s] — минимальный вес, которым первые i предметов дают
    # ровно s «округлённых» единиц стоимости
    dp = [[INF] * (total + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        w, s_i = usable[i - 1][0], scaled[i - 1]
        prev, cur = dp[i - 1], dp[i]
        for s in range(total + 1):
            best = prev[s]                          # не берём
            if s >= s_i and prev[s - s_i] + w < best:
                best = prev[s - s_i] + w            # берём
            cur[s] = best

    best_scaled = max(s for s in range(total + 1) if dp[n][s] <= capacity)

    # восстановление набора: значение изменилось ⇒ предмет был взят
    chosen, s = [], best_scaled
    for i in range(n, 0, -1):
        if dp[i][s] != dp[i - 1][s]:
            chosen.append(i - 1)
            s -= scaled[i - 1]
    chosen.reverse()
    return sum(usable[i][1] for i in chosen), [usable[i] for i in chosen]

Анализ потери. Округление вниз теряет меньше K на предмет, значит на оптимальном наборе (не более n предметов) теряется меньше nK = ε·vmax. Так как OPT ≥ vmax (любой отдельный предмет допустим), получаем ALG ≥ OPT − ε·vmax ≥ (1 − ε)·OPT. ∎

Практическая нота: ε = 0.01 уже даёт total ≈ 100n², что для n = 1000 — сто миллионов ячеек. FPTAS красив теоретически, но в проде чаще выигрывает CP-SAT с лимитом времени.

Неприближаемость: почему нельзя просто «постараться сильнее»

PCP-теорема (1992) — второй по значимости результат теории сложности после Кука–Левина. Из неё следуют жёсткие пределы:

• MAX-3SAT: нельзя лучше 7/8 (Håstad, 2001) — а 7/8 достигается тривиальным случайным присваиванием. Больше тут думать не о чем.
• Vertex Cover: нельзя лучше 1.3606 безусловно (Dinur–Safra) и лучше 2 − ε при гипотезе уникальных игр. То есть наши четыре строки, возможно, оптимальны.
• Общий TSP, Clique, Independent Set: приближения с константой не существует; для Clique предел — n^(1−ε).
• Bin Packing: нельзя 3/2 − ε для абсолютной гарантии (иначе решается Partition), зато есть асимптотический PTAS и практичный First-Fit-Decreasing с 11/9·OPT + 6/9.

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

Рычаг 3: параметризованная сложность (FPT)

Идея, которая моложе остальных и недооценена в индустрии. Вместо «полином от n» требуем время вида f(k) · poly(n), где k — некоторый параметр, малый на реальных данных. Экспонента остаётся, но она изолирована в параметре.

Канонический пример — Vertex Cover с параметром «размер покрытия k»:

def vertex_cover_fpt(edges, k):
    """Есть ли вершинное покрытие размера <= k. Время O(2^k * E), память O(k + E).
    Работает при n = 10^6, если k <= 30 — там, где 2^n безнадёжен."""
    def solve(remaining, k):
        if not remaining:
            return []
        if k == 0:
            return None
        u, v = next(iter(remaining))       # любое непокрытое ребро
        # в покрытии обязан быть u ЛИБО v — ветвление ровно на 2
        for pick in (u, v):
            rest = {e for e in remaining if pick not in e}
            sub = solve(rest, k - 1)
            if sub is not None:
                return [pick] + sub
        return None

    return solve({frozenset(e) for e in edges}, k)

Дерево ветвления имеет глубину k и фактор 2 — отсюда 2^k. Аккуратными правилами (вершины степени 1 и 2 обрабатываются детерминированно) база сбивается до 1.2738^k — Chen, Kanj, Xia (2010).

Кернелизация — вторая половина метода и, пожалуй, более практичная: за полином сжать вход до «ядра» размера g(k), эквивалентного исходному.

• Правило Бусса: вершина степени > k обязана быть в покрытии (иначе нужно > k соседей) — берём её, k--. Изолированные вершины удаляем. После этого рёбер остаётся ≤ k², иначе ответ «нет». Граф на миллион вершин при k = 40 сжимается до ≤ 1600 рёбер.
• Ядро Немхаузера–Троттера через LP-релаксацию даёт 2k вершин.

В проде кернелизация часто ценнее самого FPT-алгоритма: она — полиномиальный препроцессинг, после которого работает любой солвер. Это ровно то, что делает presolve в Gurobi. Каноническая книга — Cygan et al., «Parameterized Algorithms» (PDF свободно).

Рычаг 4: метаэвристики — когда гарантии не нужны

Гарантии стоят денег: 2-приближение Vertex Cover в среднем даёт решение хуже, чем жадность без гарантий. Если качество измеряется на реальных данных, а не в худшем случае, локальный поиск обычно выигрывает.

Локальный поиск = решение + окрестность + правило перехода. Для TSP каноническая окрестность — 2-opt: развернуть кусок маршрута.

import math
import random

def tsp_annealing(dist, iters=200_000, t0=1.0, t1=1e-4, seed=0):
    """Имитация отжига с 2-opt для TSP. Гарантий нет; на практике
    даёт 2–5% от оптимума за секунды там, где точные методы безнадёжны."""
    rnd = random.Random(seed)
    n = len(dist)
    tour = list(range(n))
    rnd.shuffle(tour)

    cur = sum(dist[tour[i]][tour[(i + 1) % n]] for i in range(n))
    best, best_tour = cur, tour[:]

    for step in range(iters):
        # геометрическое охлаждение: сначала прыгаем далеко, потом только вниз
        T = t0 * (t1 / t0) ** (step / iters)

        i, j = sorted((rnd.randrange(n), rnd.randrange(n)))
        if j - i < 2 or (i == 0 and j == n - 1):
            continue

        # 2-opt: разворачиваем tour[i..j]; меняются ровно два ребра
        p, q = tour[i - 1], tour[i]
        r, s = tour[j], tour[(j + 1) % n]
        delta = dist[p][r] + dist[q][s] - dist[p][q] - dist[r][s]

        # ключ метода: ухудшение принимается с вероятностью exp(-delta/T)
        if delta <= 0 or rnd.random() < math.exp(-delta / T):
            tour[i:j + 1] = reversed(tour[i:j + 1])
            cur += delta
            if cur < best:
                best, best_tour = cur, tour[:]

    return best, best_tour

Обратите внимание на два инженерных приёма, которые важнее выбора метаэвристики: инкрементальный пересчёт стоимости (delta за O(1) вместо O(n) на полный пересчёт — это разница в три порядка) и отдельное хранение лучшего найденного (текущее решение блуждает, лучшее — нет).

Семейство методов и чем они отличаются:

Прагматика: не начинайте с генетических алгоритмов. В 9 случаях из 10 хорошо настроенный локальный поиск с умной окрестностью бьёт «модную» метаэвристику, а отлаживается втрое проще. LKH находит оптимум на большинстве инстансов TSPLIB и решения в пределах 1% на миллионах городов. Про эволюционные подходы в инженерии стоит смотреть отдельный трек портала — search-based software engineering.

Про вероятностный анализ таких алгоритмов и про то, почему рандомизация вообще помогает, подробно в Рандомизированные алгоритмы.

Часть III. Как это выглядит в проде

NP-трудные задачи в промышленном коде встречаются намного чаще, чем кажется, — просто их не называют по именам.

• Разрешение зависимостей пакетов — это SAT. Формально NP-полно, и это доказано. Именно поэтому openSUSE/SUSE решают его SAT-солвером (libsolv), Eclipse p2 использовал SAT4J, а Dart pub и Rust cargo применяют PubGrub — алгоритм, прямо заимствующий CDCL-обучение конфликтов, чтобы выдавать внятные сообщения об ошибках вместо «не сошлось».
• Распределение регистров в компиляторе — раскраска графа интерференций (Chaitin, 1982). LLVM использует greedy-аллокатор с эвристиками приоритета и splitting, а не точную раскраску: компиляция должна занимать миллисекунды.
• Планирование в кластере (Kubernetes scheduler, Borg) — bin packing с ограничениями. Работают жадные фильтры + скоринг, потому что решение нужно за десятки миллисекунд и оно всё равно устареет через минуту.
• Маршрутизация транспорта (VRP) — Amazon, Яндекс Маршрутизация, DHL. Стек типичный: кластеризация → построение маршрутов эвристикой → локальный поиск (OR-Tools использует guided local search) → ре-оптимизация в реальном времени.
• Верификация железа и ПО — model checking, symbolic execution. SAT/SMT-солверы (Z3, CVC5) — фундамент. Здесь трудность принимают как данность и вкладываются в солвер.
• Раскладка на кристалле (placement & routing) в EDA — часы и дни счёта симулированным отжигом на задачах, где оптимум не найдёт никто и никогда.
• Составление расписаний — университеты, больницы, авиакомпании. Классическая вотчина CP-SAT и MIP; тут точность важнее скорости, счёт ночью — норма.

Общий инженерный паттерн этих систем один:

Три правила, выстраданные практикой:

1. Всегда имейте быстрое допустимое решение как fallback. Солвер может не уложиться в лимит; система не имеет права упасть из-за этого.
2. Всегда логируйте качество. Отношение к нижней границе, к вчерашнему решению, к решению вручную. Без этого вы не узнаете о деградации после смены данных.
3. Лимит времени — часть контракта, а не настройка. Anytime-алгоритм (даёт решение в любой момент, улучшая его со временем) почти всегда предпочтительнее алгоритма, который «когда-нибудь найдёт оптимум».

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

• Сведение не в ту сторону. «Я свёл свою задачу к 3-SAT, значит она NP-трудна» — нет, это значит, что вы её решили солвером. Молодцы, но доказательства нет.
• Забыли доказать обратную импликацию. f(x) ∈ B ⟹ x ∈ A — там живут «паразитные» решения. Это половина работы, и её систематически пропускают.
• Экспоненциальное сведение. Если построение f(x) само требует перебора — сведения нет.
• Путать NP-трудность и NP-полноту. Оптимизационная задача не в NP, значит не NP-полна. Мелочь, но выдаёт непонимание определения.
• Считать псевдополиномиальное ДП опровержением NP-полноты. Классика: «рюкзак же решается за O(nW)!» — да, и W экспоненциален по длине входа.
• Не посмотреть на реальный n. Написать метаэвристику там, где n = 18 и работает точный 2ⁿ-перебор, — потеря и качества, и времени разработки.
• Изобретать свой B&B вместо CP-SAT. Почти всегда проигрыш по срокам и по качеству. Своё пишут, когда структура задачи даёт границу, недоступную общему солверу.
• Эвристика без метрики качества. Если не измеряете отношение к нижней границе, вы не знаете, дают ли ваши «улучшения» хоть что-то.
• Игнорировать результаты о неприближаемости. Недели на алгоритм, который доказуемо невозможен, — реальная и частая история.
• Переоценивать метаэвристики. GA с 15 гиперпараметрами, каждый из которых надо тюнить, против 2-opt с рестартами — почти всегда выигрывает второе.
• Забыть про специальные случаи входа. Двудольность, планарность, ограниченная treewidth, интервальность — превращают NP-трудную задачу в полиномиальную. Сначала посмотрите на свои данные.

Мини-итог

• NP — это про проверяемость сертификата, а не про решаемость. Держите в голове именно верификатор, а не недетерминированную машину.
• Сведение направлено от известной трудной задачи к вашей. Это единственный источник ошибок, который стоит проверять дважды.
• NP-полнота — утверждение о худшем случае при растущем n. Она не запрещает решать ваши конкретные инстансы. Реальные данные структурированы, солверы это эксплуатируют.
• Четыре рычага: время (точные методы и солверы), оптимальность (приближения и эвристики), общность (частные классы, FPT), формулировка (переговоры с продуктом). Всегда выбирайте осознанно, какой отпускаете.
• Приближение с гарантией доказывается через нижнюю границу: паросочетание для Vertex Cover, MST для TSP, «цена за элемент» для Set Cover.
• Иерархия APX ⊃ PTAS ⊃ FPTAS — знайте, что достижимо для вашей задачи, и знайте пределы неприближаемости, чтобы не биться о стену.
• FPT и кернелизация — недооценённый инструмент: экспонента по маленькому параметру вместо экспоненты по размеру входа.
• В проде выигрывает не самый умный алгоритм, а связка «препроцессинг + гарантированный fallback + солвер с лимитом времени + метрика качества в логах».

Источники

• CLRS, Introduction to Algorithms, 4-е изд. — гл. 34 (NP-полнота) и гл. 35 (приближённые алгоритмы). Лучшая первая точка входа, полные доказательства сведений.
• M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) — знаменитый каталог с сотнями NP-полных задач. До сих пор первое место, куда стоит заглянуть с новой задачей.
• S. Arora, B. Barak, Computational Complexity: A Modern Approach — черновик свободно. Современное изложение: PCP, интерактивные доказательства, рандомизация.
• V. Vazirani, Approximation Algorithms и D. Williamson, D. Shmoys, The Design of Approximation Algorithms — PDF свободно. Канон по приближениям: LP-округление, primal-dual, полуопределённое программирование.
• M. Cygan et al., Parameterized Algorithms — PDF. FPT, кернелизация, treewidth, нижние оценки под ETH.
• S. Cook (1971), The Complexity of Theorem-Proving Procedures — ACM DL.
• R. Karp (1972), Reducibility Among Combinatorial Problems — PDF.
• J. Håstad (2001), Some Optimal Inapproximability Results — ACM DL.
• Karlin, Klein, Oveis Gharan (2020), A (Slightly) Improved Approximation Algorithm for Metric TSP — arXiv:2007.01409.
• Handbook of Satisfiability, ред. Biere, Heule, van Maaren, Walsh — всё про CDCL. Практика: SAT Competition, солвер Kissat.
• Google OR-Tools — документация, CP-SAT для планирования, маршрутизации и раскроя. Лучший бесплатный старт.
• Concorde TSP Solver — сайт и LKH. Оптимальное решение на 85 900 городов.
• Aaronson, S., P =? NP — обзор в Open Problems in Mathematics. Читаемое эссе о том, почему вопрос так тяжёл и что стоит на кону.

Что дальше

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

Параллельные и распределённые алгоритмы, консенсус