Задача о покрытии множествами

Эта задача обобщает NP-полную задачу о вершинном покрытии, но использованный там приближенный алгоритм здесь не применим. Поэтому рассмотрим жадный алгоритм; даваемое им решение хуже оптимального в log n, где n - длина входа. С увеличением n качество решения ухудшается, но логарифмическая функция растет довольно медленно.

Постановка задачи следующая: X – конечное множество, Á - семейство его подмножеств, и каждый элемент X принадлежит хотя бы одному из SÎÁ. Ищем минимальное число подмножеств из Á, покрывающих Á. Пусть Â такое семейство. Пример задачи о покрытии на рис.37.3.

Рис.37.3.

Опишем решающий задачу жадный алгоритм. Идея такого алгоритма:

в каждый момент мы выбираем множество, покрывающее максимальное число еще не покрытых элементов.

Greedy-Set-Cover(X,Á)

1. U X

2. Æ

3. while U ¹ Æ

4. do выбираем S ÎÁ с наибольшим çSÇU÷

5. U U \ S

6. Â ÂÈ{S}

7. returnÂ

В каждый момент работы алгоритма множество U содержит еще не покрытые элементы, а семейство Â - уже включенные в покрытие подмножества. Когда U = Æ, Â становится покрытием множества X.

Легко видеть, что алгоритм полиномиален: количество повторений цикла не превосходит min(çXô,çÁô), а каждое повторение реализовывается за O(çXô,çÁô) операций.

Теорема. Размер покрытия, возвращаемого алгоритмом Greedy-Set-Cover(X,Á) превосходит минимальное покрытие не более чем в

H(max {çSï: S ÎÁ}) раз.

Доказательство. Жадный алгоритм отбирает на каждом шаге то подмножество из Á, которое покрывает больше всего непокрытых элементов X. Представим себе, что на каждом шаге имеется один доллар, который распределяется между всеми вновь покрытыми элементами. Каждый элемент получает деньги только один раз и получит тем больше, чем меньше новых элементов покрывается на том же шаге. Элемент x, попадающий впервые на i-ом шаге в множество S_i , получит c_x = 1/ çS_i \ (S₁ÈS₂È…ÈS_i-1)÷ долларов. Всего потрачено ê ê долларов. Покажем, что минимальное покрытие X содержит не намного меньше множеств, чем построенное. В этом можно убедиться, показав, что для любого множества SÎÁ общая сумма денег, полученная всеми элементами S, не превосходит H(çSï) (суммы первых çSï членов гармонического ряда), тогда, чтобы выбрать общую сумму çÁï, потребуется не менее çÂï/ H(max{çSï: SÎÁ}) элементов оптимального покрытия. Для полученного покрытия  и оптимального покрытия Â*:

ç ê = S c_x £ S S c_x и будет показано, что S c_x £ H(çSï),

xÎX SÎÂ* xÎS xÎS

так что çÂ ê £ S H(çSï) £ çÂ* ê× H(max{ çS ê: SÎÁ}), ч.т.д.

SÎÂ*

Докажем неравенство S c_x £ H(çSï). Пусть S ÎÁ и S содержит

xÎS

u элементов. Каждый из этих элементов получил какую-то сумму денег, покажем, что общая сумма для всех элементов S не превосходит H(u)=

1+1/2+…+1/u. Каждый из S, получивший свои деньги раньше других элементов S, получил не более 1/u; общее количество элементов, получивших деньги на этом шаге не меньше u, так как жадный алгоритм выбирает множество, покрывающее наибольшее число еще не покрытых элементов, и не может выбрать множество, худшего S.

Следствие.Алгоритм Greedy-Set-Cover дает решение задачи о покрытии, хуже оптимального не более чем в (ln çX ê+1) раз.

Алгоритм Greedy-Set-Cover дает хорошие приближения, если множества, из которых составляется покрытие, содержат мало элементов.