Жадные алгоритмы покрытия множества: различия между версиями

Пусть дано семейство 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 объектов, каждый из которых имеет неотрицательный вес <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>, получим задачу о взвешенном покрытии множества).

[[Жадный алгоритм]] решения задачи о взвешенном покрытии множества строит покрытие путем многократного выбора множества s, минимизирующего отношение веса <math>w_s \;</math> к количеству элементов в s, еще не покрытого выбранными множествами. Алгоритм останавливает работу и возвращает выбранные множества, как только они образуют покрытие:

   3. Выбрать <math>s \in S \;</math>, минимизирующий стоимость на элемент <math>w_s / [f(C \cup \{ s \}) - f(C)]</math>.

   4. Положить <math>C \gets C \cup \{ s \}</math>.

''Доказательство''. Когда жадный алгоритм выбирает множество s, предположим, что он назначает цену за элемент на этой итерации каждому элементу, впервые покрытому множеством s. Тогда совокупный вес множеств, выбранных алгоритмом, равен общей сумме назначенных цен, при этом каждому элементу цена назначается только один раз.

Рассмотрим любое множество <math>s = \{ x_k, x_{k - 1}, ... , x_1 \} \;</math> в оптимальном покрытии множества C*. Без потери общности предположим, что жадный алгоритм покрывает элементы s в следующем порядке: <math>x_k, x_{k - 1}, ..., x_1 \;</math>. К началу итерации, на которой алгоритм покрывает элемент <math>x_i \;</math> множества s, не менее i элементов s остаются без покрытия. Таким образом, если на этой итерации жадный алгоритм собирается выбрать s, он выплатит стоимость за каждый элемент не превышающую <math>w_s/i \;</math>. Следовательно, на этой итерации жадный алгоритм выплачивает не более <math>w_s/i \;</math> за каждый покрытый элемент. Таким образом, за покрытие элемента <math>x_i \;</math> он назначает не более <math>w_s/i \;</math>. Выполнив суммирование по i, получим, что общая сумма, назначенная за элементы s, не превышает <math>w_s H_k \;</math>. Выполнив суммирование по <math>s \in C^* \;</math> и заметив, что каждый элемент принадлежит к некоторому множеству в C*, получим, что общая сумма, назначенная за все элементы, не превышает <math>\sum_{s \in C^*} w_s H_k = H_k OPT \;</math>.  □

Эту теорему для невзвешенного случая (<math>w_s = 1 \;</math> для всех s) вначале доказали Джонсон [6], Ловас [9] и Стейн [14], после чего Хватал [2] расширил ее для взвешенного случая.

Вспомним схему назначения стоимости из доказательства теоремы 1. Согласно предыдущему наблюдению, элементу <math>x_i \;</math> назначается стоимость не более OPT/i. Таким образом, общая стоимость элементов <math>x_n, ..., x_i \;</math> не превышает <math>(H_n - H_{i - q})OPT \;</math>. В силу предположения о том, что каждый вес <math>w_s \le 1 \;</math>, стоимость каждого из оставшихся элементов не превышает 1 за элемент. Таким образом, совокупная стоимость всех элементов не превышает <math>i - 1 + (H_n - H_{i - 1})OPT \;</math>. Обозначив <math>i = 1 + \lceil OPT \rceil</math>, получаем, что совокупная стоимость не превышает <math>\lceil OPT \rceil + (H_n - H_{ \lceil OPT \rceil })OPT \le 1 + OPT(1 + ln(n/OPT))</math>. □

Было показано, что коэффициент аппроксимации жадного алгоритма составляет ln n — ln ln n + O(1) [12]. Для специального случая систем множеств, дополнения которых имеют конечную размерность Вапника — Червоненкиса (VC-размерность), другие алгоритмы демонстрируют заметно лучший коэффициент аппроксимации [ ]. Известны алгоритмы аппроксимации с постоянным коэффициентом для тесно связанных с ними геометрических вариантов таких задач, как метод k-медиан и задача о размещении объектов.

Жадный алгоритм можно естественным образом обобщить на множество задач. Например, для определенной выше задачи минимизации линейной функции относительно субмодулярных ограничений естественное расширение жадного алгоритма дает решение с Hk-аппроксимацией, где k = maxs2Sf(fsg) — f(;), в предположении, что f является целочисленной функцией[10].

Обобщая задачу о покрытии множества, можно потребовать, чтобы каждый элемент x содержался в произвольном числе множеств rx; только в этом случае он будет считаться элементом покрытия. Для этого обобщения существует алгоритм O(log n)-аппроксимации с полиномиальным временем выполнения [8].

Для специального случая, когда каждый элемент принадлежит не более чем к r множествам, имеется более простой алгоритм r-аппроксимации ([15] § 15.2). Если множества имеют однородные веса (ws = 1), алгоритм сводится к следующему: выбрать любой максимальный набор элементов, никакие два из которых не содержатся в одном множестве; вернуть все множества, содержащие выбранный элемент.

В варианте «Максимальное k-покрытие» требуется, чтобы набор множеств, суммарный вес которых не превышает k, покрывал максимально возможное количество элементов. Для этого варианта существует алгоритм (1 — 1/e)-аппроксимации ([15], задача 2.18) (см. [7] для варианта множеств с неоднородными весами).

Широкое обсуждение применения жадных методов для аппроксимации задачи комбинаторной оптимизации можно найти в главе 4 работы [5]).

Наконец, в свете весьма правдоподобных теоретико-сложностных допущений, коэффициент аппроксимации ln n является практически лучшим для любого алгоритма с полиномиальным временем выполнения [3, 4].

Задача о покрытии множествами и ее обобщения и варианты являются фундаментальными для множества областей применения. Несколько примеров:

* [[Локальный поиск для метода k-медиан и задачи о размещении объектов]]