Пример: задача размещения Wi‑Fi роутеров (минимальное число роутеров, чтобы покрыть все комнаты/точки). Это классический случай, когда формулировка как задача NP‑полной оптимизации (Set Cover) полезна.
Формулировка как Set Cover
- Универсум: множество точек/комнат $U$.
- Для каждой возможной позиции роутера $i$ задано множество точек, которые она покрывает: $S_i\subseteq U$.
- Цель: выбрать подмножество позиций $C$ минимального размера, чтобы покрыть всё $U$:
$$\min |C|\text{при условии}\bigcup _{S\in C}S=U.$$
Редукция (показывает NP‑трудность)
- Возьмём известную NP‑полную задачу Vertex Cover: граф $G=(V,E)$, число $k$; вопрос: существует ли вершинное покрытие размера $\le k$?
- Построим экземпляр Set Cover: пусть $U=E$ (ребра — элементы универсума). Для каждой вершины $v\in V$ определим множество $S_v=\{e\in E:e\text{инцидентно}v\}$.
- Тогда набор вершин $C\subseteq V$ является вершинным покрытием размера $\le k$ тогда и только тогда, когда соответствующий набор множеств $\{S_v:v\in C\}$ покрывает $U$ и имеет мощность $\le k$.
- Следовательно задача минимального покрытия роутерами (Set Cover) является NP‑трудной; её решение в полиномиальное время для всех входов привело бы к $P=NP$.
Почему точное решение невозможно для больших входов
- Точными алгоритмами обычно перебирают экспоненциально много комбинаций: грубо $O(2^m)$ по числу позиций $m$ (или $O(2^{|U|})$ по числу элементов), возможно с улучшениями, но всё равно экспоненциально в худшем случае.
- Для оптимизации Set Cover нет полиномиального алгоритма с гарантированной точностью (если $P\ne NP$), и дополнительно известно ограничение на аппроксимацию: нельзя добиться приближения лучше, чем $(1-o(1))\ln |U|$ в полиномиальное время, если $P\ne NP$.
$$\text{Greedy даёт фактор}{H}_{|U|}\le \ln |U|+1,\text{а лучше}(1-o(1))\ln |U|\text{в общем случае недостижимо.}$$
Какие эвристики и приближённые методы применять (практические рекомендации)
1. Жадный алгоритм
- Итеративно выбирать множество, покрывающее максимум ещё непокрытых элементов. Быстро, даёт приближённый фактор $H_{|U|}$.
2. LP‑релаксация + округление
- Решить линейное программирование релаксацию, затем выполнить детерминированное или рандомизированное округление; даёт схожие гарантии и часто лучшую практическую производительность.
3. Локальный поиск и улучшающие эвристики (hill‑climbing, GRASP)
- Начать с жадного решения, затем пробовать замены/удаления/добавления позиций для уменьшения числа роутеров.
4. Метагевристики: симулированный отжиг, генетические алгоритмы, табу‑поиск
- Хорошо работают на больших практических инстансах без жёстких гарантий.
5. Целочисленное программирование (ILP) с ветвлением и отсечением
- Для средних по размеру задач (сотни‑тысячи переменных/ограничений) может дать оптимум; полезно сочетать с проблемно‑специфическими отсечениями.
6. Параллельные/распределённые приближения и жадные жадные локальные схемы
- Для больших распределённых систем применимы быстрые распределённые алгоритмы с локальным покрытием.
Краткая рекомендация
- Для больших реальных инстансов применяйте сначала жадный алгоритм и LP‑релаксацию; при необходимости улучшайте локальным поиском или метагевристиками. ILP/Branch‑and‑Bound — для критичных/умеренно больших задач, где нужен оптимум.