4430
правок
Жадные алгоритмы покрытия множества: различия между версиями
Перейти к навигации
Перейти к поиску
м
Жадные алгоритмы покрытия множества (посмотреть исходный код)
Версия от 10:30, 6 апреля 2018
, 6 апреля 2018→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
== Основные результаты == | == Основные результаты == | ||
[[Жадный алгоритм]] решения задачи о взвешенном покрытии множества строит покрытие путем | [[Жадный алгоритм]] решения задачи о взвешенном покрытии множества строит покрытие путем последовательного выбора множества s, минимизирующего отношение веса <math>w_s \;</math> к количеству элементов в s, еще не покрытых выбранными множествами. Алгоритм останавливает работу и возвращает выбранные множества, как только они образуют покрытие: | ||
'''greedy-set-cover(S, w)''' | '''greedy-set-cover(S, w)''' | ||
1. Инициализировать <math>C \gets \empty \;</math>. Определить <math>f(C) \; \dot= \; |\cup_{s \in C} s|</math>. | 1. Инициализировать <math>C \gets \empty \;</math>. Определить <math>f(C) \; \dot= \; |\cup_{s \in C} s|</math>. | ||
2. Повторять, пока не будет достигнуто <math>f(C) = f(S) \;</math>: | 2. Повторять, пока не будет достигнуто <math>f(C) = f(S) \;</math>: | ||
3. Выбрать <math>s \in S \;</math>, минимизирующий стоимость на элемент <math>w_s / [f(C \cup \{ s \}) - f(C)]</math>. | 3. Выбрать элемент <math>s \in S \;</math>, минимизирующий стоимость на элемент <math>w_s / [f(C \cup \{ s \}) - f(C)]</math>. | ||
4. Положить <math>C \gets C \cup \{ s \}</math>. | 4. Положить <math>C \gets C \cup \{ s \}</math>. | ||
5. Вернуть C | 5. Вернуть C | ||