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