Задача о покрытии множества

Дано множество объектов $A$ и множество $B$ подмножеств множества $A$.

$$\forall b\in B,b\subseteq A$$

Нужно найти наименьшее подмножество $B$ которое при объединении совпадает с множеством $A$.

Сложность задачи $\mathcal{O}(n!)$, задача относится к NP-полным.

Ссылки

• Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 8. Жадные алгоритмы. Задача о покрытии множества

Ссылки на эту заметку

• NP-полные задачи

Эта заметка на GitHub

Обсудить на форуме