4430
правок
Жадные алгоритмы покрытия множества: различия между версиями
Перейти к навигации
Перейти к поиску
Жадные алгоритмы покрытия множества (посмотреть исходный код)
Версия от 11:47, 3 апреля 2018
, 3 апреля 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дано семейство S множеств над совокупностью U. Покрытие множества | Пусть дано семейство S множеств над совокупностью U. ''Покрытие множества'' <math>C \subseteq S \;</math> представляет собой подсемейство множеств, объединением которых является U. ''Задача о покрытии множества'' заключается в нахождении покрытия множествами с минимальной мощностью для заданного S. В ''задаче о взвешенном покрытии множества'' для каждого множества <math>s \in S \;</math> задается вес <math>w_s \ge 0 \;</math>, и цель заключается в нахождении покрытия множества C с минимальным совокупным весом <math>\sum_{s \in C} w_s \;</math>. | ||
Взвешенное покрытие множества представляет собой специальный случай минимизации линейной функции относительно субмодулярных ограничений, определяемый следующим образом. Пусть дано семейство S объектов, каждый из которых имеет неотрицательный вес | Взвешенное покрытие множества представляет собой специальный случай ''минимизации линейной функции относительно субмодулярных ограничений'', определяемый следующим образом. Пусть дано семейство S объектов, каждый из которых имеет неотрицательный вес <math>w_s \;</math>, и неубывающая субмодулярная функция <math>f: 2^S \to \mathbb{R}</math>. Задача заключается в нахождении подсемейства <math>C \subseteq S \;</math>, такого, что <math>f(C) = f(S) \;</math> минимизирует <math>\sum_{s \in C} w_s \;</math>. (Если положить <math>f(C) = |\cup_{s \in C} s|</math>, получим задачу о взвешенном покрытии множества). | ||
== Основные результаты == | == Основные результаты == | ||