Пример: размещение точек доступа Wi‑Fi как задача минимального покрытия (Set Cover).
Формулировка
- Универсум мест, которые надо покрыть: $U=\{u_1,\dots ,u_n\}$.
- Набор кандидатов (зоны покрытия каждой точки): $\mathcal{S}=\{S_1,\dots ,S_m\}$, где $S_j\subseteq U$.
- Для варинта с ценами — стоимость установки точки $c_j>0$.
- Решающий (decision) вариант NP-полной задачи: существует ли подпоследовательность $\mathcal{C}\subseteq \mathcal{S}$ такой, что ${\bigcup }_{S\in \mathcal{C}}S=U$ и ${\sum }_{S\in \mathcal{C}}c(S)\le K$?
Анализ сложности
- Задача Set Cover в этой форме — NP‑полная.
- Жёсткое ограничение аппроксимации: нельзя добиться аппроксимации лучше, чем $(1-o(1))\ln n$ (где $n=|U|$), если $\mathrm{P}\ne \mathrm{NP}$.
Эвристики и приближённые алгоритмы (для практического решения)
1) Жадный алгоритм (стоимость/прибыль)
- Выбирать на каждом шаге множество $S_j$ с максимальным значением $\frac{|S_j\setminus C|}{c_j}$ (где $C$ — уже покрытые элементы).
- Гарантия качества: аппроксимация $H_n\le \ln n+O(1)$, где $H_n$ — гармонический ряд.
- Сложность: наивно $O(mn)$ за шаги; оптимизации через структуры данных/кучи и инцидентные списки дают близко к $O({\sum }_j|S_j|\log m)$.
2) LP‑релаксация и округление
- Решить линейную релаксацию: минимизировать ${\sum }_j{c}_j{x}_j$ при ${\sum }_{j:i\in S_j}{x}_j\ge 1\forall i$, $0\le x_j\le 1$.
- Округление (пороговое или случайное) даёт аппроксимацию $O(\ln n)$ (аналогично жадному).
- Практика: даёт хорошие решения, особенно если включить пост‑процессинг (удаление лишних множеств).
3) Локальный поиск и улучшение
- Начать с жадного решения, затем пробовать операции swap: заменить $t$ множеств на $t-1$ и т.д.
- Симулированный отжиг или эволюционные алгоритмы для выхода из локальных минимумов.
- Качество: нет строгой гарантии, но часто существенно улучшает жадный результат в практике.
4) Специальные предобработки и сокращения
- Удалить доминируемые множества ($S_a\subseteq S_b$ и $c_a\ge c_b$).
- Покрыть элементы, которые встречаются в единственном множестве (обязательное включение).
- Сжать задачу (kernelization) для частичных вариантов.
5) Точный метод для небольших/умеренных случаев
- ILP/Branch-and-Bound/Branch-and-Cut (коммерческие солверы: CPLEX, Gurobi) — решают оптимально до размеров, зависящих от структуры (до тысяч переменных при удачной структуре).
Оценка качества методов
- Теоретическая гарантия: жадный и LP‑методы дают аппроксимацию $H_n\le \ln n+O(1)$. Нельзя (в общем случае) получить лучше чем $(1-o(1))\ln n$.
- Практическая оценка:
- Жадный: быстро, часто близко к оптимуму (в реальных инстанциях ошибка обычно небольшая).
- LP + округление: чуть дороже по времени, обычно лучше жадного при учёте стоимостей.
- Локальный поиск/метаэвристики: улучшение жадного решения на $5\%-30\%$ в типичных тестах (зависит от структуры), но без строгой гарантии.
- ILP‑решение: оптимум для малых и средних задач; при больших размерах — вычислительно тяжело.
Практические рекомендации
- Для больших инстанций: жадный алгоритм (с учётом стоимости) + локальный поиск; предусмотреть предобработку (удаление доминаций).
- Если важна формальная гарантия: LP‑релаксация и округление.
- Для критичных малых/средних задач: использовать ILP‑солвер для точного решения.
- Оценивать качество эмпирически на типичных данных: сравнивать жадный/LP‑решения с ILP на уменьшенных случаях, чтобы настроить эвристики.
Кратко: реальная задача минимальной установки точек Wi‑Fi сводится к Set Cover (NP‑полная). Жадный и LP‑подходы дают теоретически оптимальную в смысле аппроксимации $O(\ln n)$ и на практике обычно дают хорошие решения; локальный поиск и солверы помогают довести качество до практически приемлемого уровня.