Hardprob/Minimum Test Collection

Ссылки сюда (3) →

• Коллекция C подмножеств конечного множества S.
• Найти подколлекцию C'⊆ C, такую, что для каждой пары различных элементов , есть некоторое множество , которое содержит точно один элемент из этой пары.
• Минимизировать мощность этой подколлекции |C'|.

---

Код в «minimum-test-collection.ipynb» на гитлаб или живьем в лабе

---

• Задача в базе NP-полных задач Вигго Кана
• Код задачи в книге «ГД» → «SP6»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.