Оптимизация
Комбинаторная оптимизация
Amazon ежедневно решает тысячи задач маршрутизации доставки - вариантов TSP. Google Maps оптимизирует маршруты для миллионов водителей. Ни одна из этих задач не решается точно за полиномиальное время, но аппроксимационные алгоритмы с гарантиями делают их практически решаемыми.
- **Доставка:** UPS экономит 10 миллионов литров топлива в год через ORION - алгоритм маршрутизации на основе аппроксимации TSP
- **Chip design:** размещение компонентов на чипе (floorplanning) - комбинаторная задача; решается ILP + метаэвристики в Intel/NVIDIA
- **ML feature selection:** отбор минимального покрывающего набора признаков - Set Cover с ML-специфичными objective
Предварительные знания
Задача коммивояжёра (TSP)
**TSP (Travelling Salesman Problem)**: дан граф из n городов с расстояниями - найти кратчайший гамильтонов цикл (обойти все города ровно по разу и вернуться). NP-сложная задача: точное решение - O(n!) в лоб, O(2ⁿ·n²) динамическим программированием. Но 3/2-аппроксимация алгоритмом Кристофидеса - за полиномиальное время.
**Алгоритм Кристофидеса (1976):** гарантия ≤ 1.5 × оптимум для метрического TSP. Шаги: 1. минимальное остовное дерево MST 2. минимальное совершенное паросочетание для нечётных вершин 3. Эйлеров обход 4. shortcutting. Один из классических результатов - 1.5 × OPT держится как рекорд до недавнего прорыва (2020: 1.5-ε, Karlin, Klein, Gharan).
Почему алгоритм Кристофидеса гарантирует не более 1.5 × OPT для метрического TSP, но не для общего TSP?
Минимальное остовное дерево
**MST** (Minimum Spanning Tree): найти подграф из n-1 рёбер, связывающий все n вершин с минимальной суммарной стоимостью. В отличие от TSP - полиномиальная задача! Алгоритм Прима (жадный) и Краскала (sort + union-find) решают за O(E log V).
| Алгоритм | Сложность | Когда лучше |
|---|---|---|
| Прима (naive) | O(V²) | Плотные графы (E ≈ V²) |
| Прима (heap) | O(E log V) | Разреженные графы |
| Краскала | O(E log E) | Разреженные графы, edge list |
| Борувки | O(E log V) | Параллельная реализация |
Алгоритм Краскала добавляет рёбра в порядке возрастания веса. Как он проверяет, что новое ребро не создаёт цикл?
Set Cover и аппроксимация
**Задача покрытия множества**: дано множество U из n элементов и коллекция подмножеств S₁,...,Sₘ - найти минимальный набор подмножеств, покрывающий U. NP-сложная задача. Жадный алгоритм «выбирать Sᵢ с максимальным числом непокрытых элементов» даёт **ln(n)-аппроксимацию**.
**Нижняя граница:** нельзя аппроксимировать Set Cover лучше чем (1-ε)·ln(n) за полиномиальное время (если P≠NP, Dinur & Steurer, 2014). Жадный алгоритм optimal! Это один из редких случаев, когда простой жадный алгоритм теоретически оптимален среди полиномиальных.
Жадный алгоритм для Set Cover выбирает подмножество с максимальным числом новых покрытых элементов. Каков теоретический guarantee на качество решения?
Аппроксимируемость и NP-сложность
Комбинаторная оптимизация изучает не только алгоритмы, но и **нижние границы аппроксимации**: насколько близко к оптимуму можно подойти за полиномиальное время? PCP theorem и inapproximability results дают точные ответы для многих задач.
**В ML-инженерии:** понимание аппроксимируемости помогает выбирать алгоритм. Если задача аппроксимируется с гарантией - используем её. Если нет (например, общий TSP) - метаэвристики (SA, GA, ACO) без гарантий, но с хорошей практической работой.
Для NP-сложных задач нет ничего лучше полного перебора или метаэвристик
Многие NP-сложные задачи имеют полиномиальные аппроксимации с гарантиями: Кристофидес для TSP (1.5×), жадный для Set Cover (ln n ×), FPTAS для рюкзака ((1+ε)×).
NP-сложность означает, что точный алгоритм неполиномиален. Но аппроксимационные алгоритмы могут быть полиномиальными и давать строгие гарантии на качество. Иерархия аппроксимируемости (PTAS, APX, inapproximable) изучает эти границы точно. Для инженера это значит: перед метаэвристикой стоит проверить - нет ли аппроксимационного алгоритма с гарантией.
FPTAS для задачи о рюкзаке даёт (1+ε)-аппроксимацию за O(n/ε²). Что это означает на практике?
Ключевые идеи
- **TSP** - NP-сложный; алгоритм Кристофидеса: 3/2-аппроксимация через MST + паросочетание для метрического TSP
- **MST** - полиномиальный (Прим, Краскал O(E log V)); строительный блок для аппроксимаций и кластеризации
- **Set Cover** - жадный алгоритм: ln(n)-аппроксимация, теоретически оптимальная среди полиномиальных
- **Аппроксимируемость:** PTAS/FPTAS для рюкзака и scheduling; APX-complete для Vertex Cover; inapproximable для общего TSP
Связанные темы
Комбинаторная оптимизация: точные методы и эвристики:
- ILP — TSP, Set Cover формулируются как ILP; Branch & Cut решает точно на малых n
- Метаэвристики — SA, GA, ACO используются когда нет аппроксимаций с гарантиями
- Multi-Objective — Маршрутизация с несколькими критериями (время, стоимость, углерод) - MOO задача
Вопросы для размышления
- Почему для метрического TSP существует 3/2-аппроксимация, а для общего TSP (без треугольного неравенства) нельзя аппроксимировать с любой константой? Что именно ломается?
- Жадный алгоритм для Set Cover теоретически оптимален. Тогда зачем использовать ILP или метаэвристики для задач покрытия?
- Как задача отбора признаков в ML сводится к Set Cover? Что является universe, что является подмножествами?