Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Abondar (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | Жадный алгоритм: на <math>k</math>-ом шаге добавляем элемент <math>x_{k}</math>, который содержится в наибольшем числе изначальных подмножеств, не содержащих ни один из элементов <math>x_{k-1}, \ldots, x_{1}</math>. | |
| − | + | ||
| + | Пусть на <math>k</math>-ом шаге осталось <math>X_{k}</math> подмножеств, в которых не содержаться ни один из элементов <math>x_{k-1}, \ldots, x_{1}</math>. Пусть также размер оптимального hitting seta равен <math>M</math>, а изначально было <math>J</math> подмножеств. Тогда на <math>k</math> - ом шаге будет покрыто не менее <math>\frac{X_{k}}{M}</math> объектов. Действительно, иначе оптимальный hitting set не покрывал бы и оставшиеся подмножества. В результате, | ||
| + | <math> | ||
| + | X_{k + 1} \le X_{k} - \frac{X_{k}}{M}, | ||
| + | </math> | ||
| + | А значит, | ||
| + | <math> | ||
| + | X_{k} \le J(1 - \frac{1}{M})^{k} \le J\exp(-\frac{k}{M}), | ||
| + | </math> | ||
| − | + | Требуя, чтобы правая часть неравенства была меньше единицы, то есть полное покрытие всего семейства получам, что | |
| − | < | + | <math> |
| + | \frac{k_{1}}{M} \le 1 + \ln(J) | ||
| + | </math> | ||
| + | |||
| + | Но <math>k_{1}</math> - и есть число элементов в жадном hitting set-е. Значит получена оценка на точность. | ||
| + | |||
| + | [[Категория:На проверку]] | ||
Версия 08:02, 7 октября 2014
Жадный алгоритм: на -ом шаге добавляем элемент , который содержится в наибольшем числе изначальных подмножеств, не содержащих ни один из элементов .
Пусть на -ом шаге осталось подмножеств, в которых не содержаться ни один из элементов . Пусть также размер оптимального hitting seta равен , а изначально было подмножеств. Тогда на - ом шаге будет покрыто не менее объектов. Действительно, иначе оптимальный hitting set не покрывал бы и оставшиеся подмножества. В результате, А значит,
Требуя, чтобы правая часть неравенства была меньше единицы, то есть полное покрытие всего семейства получам, что
Но - и есть число элементов в жадном hitting set-е. Значит получена оценка на точность.