Кратко: NP‑полные задачи на практике решают не точными полиномиальными алгоритмами (их нет при общепринятом предположении $P\ne NP$), а эвристиками, аппроксимациями и методами локального поиска, которые обеспечивают приемлемое качество решений за разумное время. Ниже — обзор на примерах рюкзака и коммивояжёра и практические рекомендации.
1) Задача о рюкзаке (0/1 knapsack)
- Формулировка: есть ёмкость $W$ и $n$ предметов с весами $w_i$ и ценностями $v_i$; цель — максимизировать суммарную ценность при суммарном весе $\le W$.
- Точные и псевдополиномиальные методы:
- Динамическое программирование по весу: время $O(nW)$ — работоспособно при умеренных $W$.
- Branch-and-bound / ветвей и границ — эффективен на многих реальных наборах благодаря отсечению.
- Аппроксимации и FPTAS:
- Скалирование ценностей даёт FPTAS: для заданного $\epsilon >0$ можно получить решение не хуже $(1-\epsilon )$ от оптимума за время полиномиальное в $n$ и $1/\epsilon$ (в разных реализациях, например, $O(n^2/\epsilon )$ или $O(n^3/\epsilon )$).
- Простые эвристики:
- Жадный по плотности: сортировка по $v_i/w_i$ и заполнение — оптимален для дробного рюкзака, для 0/1 даёт часто хорошее приближение, но может провалиться в худшем случае.
- Приём «жадный или лучший одиночный предмет»: взять максимум между жадным решением и одним самым ценным предметом даёт гарантию $1/2$.
- Локальный поиск и метаэвристики:
- Операторы соседства: добавить/удалить предмет, обмен (1‑0, 1‑1), k‑swap.
- Алгоритмы: Hill‑climbing, simulated annealing, tabu search, генетические алгоритмы — часто дают близкие к оптимальным решения за большие $n$.
- Практические рекомендации:
- Если $W$ невелик — DP; если нужна гарантированная близость — FPTAS; для очень больших $n$ — жадный + локальный поиск/метаэвристика; B&B используют, если нужны точные решения для большинства инстансов.
2) Задача коммивояжёра (TSP)
- Формулировка: найти гамильтонов цикл минимальной длины в графе с $n$ вершинами; важна разница: метрический TSP (матрица расстояний удовлетворяет неравенству треугольника) vs общий TSP.
- Политика аппроксимаций (метрический случай):
- Двойное MST (двойной обход MST с сокращением) даёт 2‑аппроксимацию.
- Алгоритм Кристофидеса даёт гарантированную аппроксимацию $3/2$ для симметричного метрического TSP.
- Для общего (не метрического) TSP нет полиномиальных алгоритмов с постоянным приближением (если $P\ne NP$).
- Практические эвристики и локальный поиск:
- Простые эвристики: nearest neighbor, greedy, insertion — быстрые стартовые решения, но без сильных гарантий.
- k‑opt (2‑opt, 3‑opt) — базовый локальный поиск, эффективно устраняет перекрёстки; 2‑opt быстро, 3‑opt лучше по качеству.
- Lin‑Kernighan (LK) и его реализации (LKH) — в практике дают очень хорошие решения на больших инстансах, хотя формальной гарантии постоянного фактора нет.
- Metaheuristics: simulated annealing, tabu search, ant colony — часто применяются для сложных или специфичных инстансов.
- Использование релаксаций и точных методов:
- LP‑релаксация (Held‑Karp) даёт сильные нижние оценки; используется в branch‑and‑bound / branch‑and‑cut (Concorde — промышленный решатель).
- Практические рекомендации:
- Для метрического TSP: если нужна гарантия — Кристофидес; для реальной большой практики — стартовый алгоритм + Lin‑Kernighan (LKH), многократные рестарты и пост‑обработка 3‑opt.
- Для специфичных ограничений — гибридные подходы: эвристика для быстрого решения, B&C для доочистки/доказательства оптимальности на подзадачах.
3) Общие принципы применения эвристик и локального поиска
- Комбинации работают лучше: жадная инициализация → локальная оптимизация (k‑opt) → метаэвристика для выхода из локальных минимумов → повторные рестарты.
- Баланс качество/время: задавайте допустимый $\epsilon$ или время и выбирайте FPTAS/локал/метаэвристику соответственно.
- Использование нижних оценок (LP, MST, суммарные веса) помогает в ветвлении и оценке качества приближений.
- Настройка и адаптация: эвристики чувствительны к структуре входа — стоит тестировать и настраивать параметры (температура, табу‑длина, размер популяции и т.д.).
- Применение в гибридных системах: эвристики дают хорошие стартовые решения и верхние границы для точных методов (ускоряют B&B), точные методы используют эвристики для отсевов.
Краткое резюме: эвристики и локальные методы — основа практического решения NP‑задач. Для рюкзака предпочтительны DP/FPTAS при потребности в гарантии и жадные + локальные/метаэвристики при масштабах; для TSP — Кристофидес для гарантии в метрическом случае, а в реальных приложениях — Lin‑Kernighan (LKH) и гибриды с локальным поиском и метаэвристиками.