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

Перейти к навигации Перейти к поиску
Строка 10: Строка 10:
== Основные результаты ==
== Основные результаты ==
[[Жадный алгоритм]] решения задачи о взвешенном покрытии множества строит покрытие путем многократного выбора множества s, минимизирующего отношение веса <math>w_s \;</math> к количеству элементов в s, еще не покрытого выбранными множествами. Алгоритм останавливает работу и возвращает выбранные множества, как только они образуют покрытие:
[[Жадный алгоритм]] решения задачи о взвешенном покрытии множества строит покрытие путем многократного выбора множества 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. Repeat until <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. Return C
   5. Вернуть C
 


Обозначим за Hk значение Pki=1 1/i ^ m k, где k – размер наибольшего множества.
Обозначим за <math>H_k \;</math> значение <math>\sum_{i = 1}^k 1 / i \approx ln \; k</math>, где k – размер наибольшего множества.




Теорема 1. Жадный алгоритм возвращает покрытие множества, вес которого не более чем в Hk раз превышает минимальный вес любого покрытия.
'''Теорема 1. Жадный алгоритм возвращает покрытие множества, вес которого не более чем в <math>H_k \;</math> раз превышает минимальный вес любого покрытия.'''




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




Рассмотрим любое множество s = fxk, x, ,x\) в оптимальном покрытии множества C*. Без потери общности предположим, что жадный алгоритм покрывает элементы s в следующем порядке: xk, xk - 1, x1. К началу итерации, на которой алгоритм покрывает элемент xi множества s, не менее i элементов s остаются без покрытия. Таким образом, если на этой итерации жадный алгоритм собирается выбрать s, он выплатит стоимость за каждый элемент не превышающую ws/i. Следовательно, на этой итерации жадный алгоритм выплачивает не более ws/i за каждый покрытый элемент. Таким образом, за покрытие элемента xi он назначает не более ws/i. Выполнив суммирование по i, получим, что общая сумма, назначенная за элементы s, не превышает ws Hk. Выполнив суммирование по s 2 C* и заметив, что каждый элемент принадлежит к некоторому множеству в C*, получим, что общая сумма, назначенная за все элементы, не превышает X!sec* wsHk = HkOPT.  □
Рассмотрим любое множество <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>.  □




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




Источник — http://pco.iis.nsk.su/wega/index.php/Жадные_алгоритмы_покрытия_множества