Hardprob/Minimum Hitting Set — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Коллекция <em>C</em> подмножеств конечного множества <…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w[^_⊆]*)\s*⊆\s*(\w)</m> на <em>\1 ⊆ \2</em>) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 2: | Строка 2: | ||
* Коллекция <em>C</em> подмножеств конечного множества <em>S</em>. | * Коллекция <em>C</em> подмножеств конечного множества <em>S</em>. | ||
| − | * Найти множество представителей (hitting set) для <em>C</em>, т.е. подмножество < | + | * Найти множество представителей (hitting set) для <em>C</em>, т.е. подмножество <em>S' ⊆ S</em>, такое, что <em>S'</em> содержит по крайней мере один элемент из каждого подмножества из <em>C</em>. |
* Минимизировать размер множества представителей, <m>\vert S'| → \min</m>. | * Минимизировать размер множества представителей, <m>\vert S'| → \min</m>. | ||
Текущая версия на 22:10, 17 апреля 2023
- Коллекция C подмножеств конечного множества S.
- Найти множество представителей (hitting set) для C, т.е. подмножество S' ⊆ S, такое, что S' содержит по крайней мере один элемент из каждого подмножества из C.
- Минимизировать размер множества представителей, .
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP8»