Лаборатория комбинаторной оптимизации

Зачем эти задачи

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

0/1 Knapsack — задача о рюкзаке

Постановка: дан набор предметов, каждый с весом w и ценностью v; рюкзак вместимостью W. Выбрать подмножество предметов с максимальной суммарной ценностью при ограничении суммарного веса ≤ W. Каждый предмет можно взять или не взять (0/1) — отличие от Fractional Knapsack, где можно брать дроби.

Решение через динамическое программирование: dp[i][w] = максимальная ценность из первых i предметов при доступной вместимости w. Переход: либо не берём i-й предмет (dp[i-1][w]), либо берём (dp[i-1][w-w_i] + v_i). Сложность O(n·W). Восстановление взятых предметов — обратным проходом.

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

Постановка: дано множество городов и расстояния между ними. Найти кратчайший маршрут, посещающий каждый город ровно один раз и возвращающийся в исходный.

В лаборатории два решателя:

• Held–Karp DP (1962) — точное решение через bitmask DP. dp[mask][v] = мин. стоимость покрыть города из mask, оканчиваясь в v. Сложность O(n²·2ⁿ). Для n=15 — около 30 миллионов состояний.
• Nearest Neighbor — простая эвристика: всегда идти в ближайший непосещённый город. Сложность O(n²). Среднее отклонение от оптимума — около 25%.

NP-полнота — почему сложно

Обе задачи NP-полные. Для n городов TSP имеет (n-1)!/2 различных маршрутов — для 20 городов это уже 60 квадриллионов. Перебор невозможен. Best современный алгоритм для точного TSP — гибрид DP и Branch-and-Bound. Для практических задач (1000+ городов) используются эвристики: Lin-Kernighan, симуляция отжига, генетика, муравьиные алгоритмы.

Тем не менее малые экземпляры (до 50 городов) решаются точно за разумное время современными ILP-солверами (Gurobi, CPLEX) с использованием cutting planes. Кейсы с десятками тысяч городов — через приближённые решения с гарантированными границами (PTAS).

Реальные применения

• Логистика: Яндекс Доставка, СДЭК, Boxberry — оптимизация маршрутов курьеров.
• Производство: сверление плат, обработка деталей, сборка.
• Планирование путешествий: tour planners.
• Инвестиции: выбор активов в портфеле при ограниченном капитале (Knapsack).
• Распределение ресурсов: upload/download throttling, кэши, очереди.
• Расписания: авиационные маршруты, школьные расписания (NP-полно).