|
|
| (не показано 15 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| − | Жадный алгоритм: на <math>k</math>-ом шаге добавляем элемент <math>x_{k}</math>, который содержится в наибольшем числе изначальных подмножеств, не содержащих ни один из элементов <math>x_{k-1}, \ldots, x_{1}</math>.
| + | Предложите детерминированный приближенный алгоритм для [[Minimum Hitting Set]] и оцените его точность. |
| | | | |
| − | Пусть на <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 не покрывал бы и оставшиеся подмножества. В результате,
| + | {{needjupyternotebook}} |
| − | <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-е. Значит получена оценка на точность.
| + | |
| − | | + | |
| − | [[Категория:На проверку]] | + | |
Версия 15:49, 20 мая 2020
Предложите детерминированный приближенный алгоритм для Minimum Hitting Set и оцените его точность.
Решение, по возможности, оформите в виде jupyter notebook.