Модель, формулировка
- Вход: конечное множество элементов (универсум) $U=\{e_1,\dots ,e_n\}$ и семейство подмножеств $\mathcal{S}=\{S_1,\dots ,S_m\}$, $S_j\subseteq U$. Цель — выбрать подмножество $\mathcal{C}\subseteq \mathcal{S}$ такое, что ${\bigcup }_{S\in \mathcal{C}}S=U$ и количество выбранных множеств минимально.
- Решение (оптимизационная задача): минимизировать $|\mathcal{C}|$ при покрытии всех элементов.
Целочисленная (0–1) модель (ILP):
$$\begin{array}{rl}& \min \sum _{j=1}^m{x}_j\\ & \text{при}\sum _{j:e_i\in S_j}{x}_j\ge 1\forall i=1,\dots ,n,\\ & x_j\in \{0,1\}\forall j.\end{array}$$
Применения в информатике (с конкретными отображениями)
- Минимизация тестов (test suite minimization): $U$ — набор возможных дефектов/условий, $S_j$ — множество дефектов, обнаруживаемых тестом $j$. Требуется минимальный набор тестов, покрывающий все дефекты.
- Разметка датасетов (active learning / selective labeling): $U$ — множество «информативных» признаков/классов/сценариев, $S_j$ — объекты, разметка которых покрывает определённые признаки; задача — выбрать минимальное подмножество объектов для разметки, чтобы «покрыть» необходимые признаки.
- Размещение сенсоров, покрытие требований безопасности, документная индексация/резюмирование (каждый документ покрывает ключевые факты) и др.
NP-полнота (доказательство)
- Решение задачи принадлежит NP: сертификат — набор индексов $J$ таких, что $|J|\le k$; проверка за полиномиальное время.
- NP-трудность (редукция из Vertex Cover). Пусть задан граф $G=(V,E)$ и число $k$. Построим задачу Set Cover: $U:=E$ (элементы — рёбра), для каждого вершины $v\in V$ определим $S_v:=\{e\in E:e\text{инцидентно}v\}$. Тогда существует вершинное покрытие размера $\le k$ в $G$ тогда и только тогда, когда в построенной задаче существует покрытие $U$ не более чем $k$ множествами (множества соответствуют вершинам). Следовательно, Set Cover — NP‑полная задача.
Приближённые алгоритмы и эвристики с гарантиями
1) Жадный алгоритм (стандартный)
- Идея: итеративно выбирать множество, покрывающее наибольшее число ещё непокрытых элементов.
- Гарантия: если $n=|U|$, то жадный алгоритм даёт приближение $H_n={\sum }_{i=1}^n\frac{1}{i}\le \ln n+1$. Формально: пусть OPT — размер оптимального покрытия ($k^{\ast }$). Тогда жадный алгоритм вернёт покрытие размера $\le k^{\ast }{H}_n$.
- Короткая схема доказательства: в любой итерации остаётся $r$ непокрытых элементов; оптимум покрывает их с помощью $\le k^{\ast }$ множеств, значит одно из этих множеств покрывает $\ge r/k^{\ast }$ элементов, следовательно жадный шаг уменьшает $r$ по крайней мере на этот размер. Анализ «суммирования по шагам» даёт оценку $k^{\ast }{H}_n$.
2) Релаксация LP и рандомизированное округление
- LP-релаксация: заменить $x_j\in \{0,1\}$ на $x_j\in [0,1]$.
$$\begin{array}{rl}& \min \sum _{j=1}^m{x}_j\\ & \text{при}\sum _{j:e_i\in S_j}{x}_j\ge 1\forall i,\\ & 0\le x_j\le 1.\end{array}$$ - Округление: выполнить рандомизированное округление с масштабированием $x_j$ (например, выбрать $S_j$ с вероятностью $\min (1,c\cdot x_j\ln n)$ с подходящей константой $c$). Тогда с постоянной вероятностью все элементы будут покрыты, а ожидаемое число выбранных множеств $O(\ln n)\cdot {\text{LP}}^{\ast }\le O(\ln n)\cdot OPT$. Следовательно, даётся приближение $O(\ln n)$.
- Интеграционный разрыв LP для Set Cover — $\Theta (\ln n)$, т.е. алгоритмы на базе LP не превзойдут логарифмический фактор в худшем случае.
3) Примал-дуальный (deterministic) алгоритм
- Построен на двойственной LP и даёт ту же гарантию $H_n$. Полезен для потоковых/онлайн версий.
Трудности приближения (жёсткая нижняя граница)
- Теоретический результат: задача Set Cover не допускает приближения с фактором $(1-ϵ)\ln n$ для любого фиксированного $ϵ>0$ в полиномиальном времени, если не выполняются сильные предположения из теории сложности (результат Feige). Иными словами — логарифмический фактор приближения ближе к оптимальному.
Практические эвристики (без доказуемой гарантии, часто эффективны)
- Локальный поиск (удаление/замена множеств), жадный с весами (учёт стоимости/веса множеств), имитация отжига, генетические алгоритмы, жадные с предобработкой и кластеризацией элементов.
- Гибриды: LP → раунд → локальный поиск для уменьшения избыточности.
Краткие рекомендации
- Для гарантий используйте жадный алгоритм или LP/примал‑дуальный подход (фактор $H_n\approx \ln n$).
- Для практических задач с дополнительной структурой (ограниченные перекрытия, маленький максимальный размер множеств, плотные/редкие структуры) часто работают локальные эвристики и кастомные формулировки, которые могут значительно превзойти общую логарифмическую границу на реальных данных.
Если нужно, могу: 1) привести формальное доказательство оценки для жадного алгоритма по шагам; 2) показать пример построения для конкретной прикладной задачи (тестирование/разметка).