Hardprob/Minimum Test Collection — различия между версиями
Материал из DISCOPAL
3xMike (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 2: | Строка 2: | ||
* Коллекция <em>C</em> подмножеств конечного множества <em>S</em>. | * Коллекция <em>C</em> подмножеств конечного множества <em>S</em>. | ||
| − | * Найти подколлекцию <em>C'⊆ C</em>, такую, что для каждой пары различных элементов <m>x_1, | + | * Найти подколлекцию <em>C'⊆ C</em>, такую, что для каждой пары различных элементов (и для каждого элемента этой пары) <m>x_1, x_2 ∈ S</m>, есть некоторое подмножество <m>c∈C'</m>, которое содержит точно один элемент из этой пары. |
* Минимизировать мощность этой подколлекции <em>|C'|</em>. | * Минимизировать мощность этой подколлекции <em>|C'|</em>. | ||
| + | |||
| + | Для понимания названия задачи, представим, что <em>S</em> — это множество возможных болезней, а подмножества — это симптомы (или «тесты»), которые могут быть характерны для нескольких болезней. И мы должны выбрать такой набор симптомов-тестов, чтобы имея результаты, мы могли отличить у пациента любые пары болезней. | ||
---- | ---- | ||
| Строка 19: | Строка 21: | ||
</small> | </small> | ||
<!-- end --> | <!-- end --> | ||
| − | |||
[[Категория:ClassicHardProblems]] | [[Категория:ClassicHardProblems]] | ||
Текущая версия на 15:07, 11 апреля 2024
- Коллекция C подмножеств конечного множества S.
- Найти подколлекцию C'⊆ C, такую, что для каждой пары различных элементов (и для каждого элемента этой пары) , есть некоторое подмножество , которое содержит точно один элемент из этой пары.
- Минимизировать мощность этой подколлекции |C'|.
Для понимания названия задачи, представим, что S — это множество возможных болезней, а подмножества — это симптомы (или «тесты»), которые могут быть характерны для нескольких болезней. И мы должны выбрать такой набор симптомов-тестов, чтобы имея результаты, мы могли отличить у пациента любые пары болезней.
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP6»