Жадный алгоритм в задачах о покрытии/Задачи/minimum-hitting-set-k — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «Рассмотрим задачу Minimum Hitting Set. Пусть ''k'' — максимальный размер подмножеств из ''C''. Пос…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]]) |
||
| (не показано 7 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| + | <!-- cabook-ex-02-17-p99 --> | ||
| + | |||
Рассмотрим задачу [[Minimum Hitting Set]]. | Рассмотрим задачу [[Minimum Hitting Set]]. | ||
| Строка 7: | Строка 9: | ||
;Hint: [[Minimum Hitting Set]] является обобщением минимального вершинного покрытия. | ;Hint: [[Minimum Hitting Set]] является обобщением минимального вершинного покрытия. | ||
| − | [[Категория: | + | [[Категория:Решенные задачи]] |
Версия 15:49, 20 мая 2020
Рассмотрим задачу Minimum Hitting Set.
Пусть k — максимальный размер подмножеств из C.
Постройте k-оптимальный полиномиальный алгоритм.
- Hint
- Minimum Hitting Set является обобщением минимального вершинного покрытия.