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

Опубликовано: 27 Февраля, 2023

Для множества U из n элементов набор подмножеств U скажем S = {S 1 , S 2 …, S m }, где каждое подмножество S i имеет связанную стоимость. Найдите подколлекцию S с минимальной стоимостью, покрывающую все элементы U.

Пример:

   U = {1,2,3,4,5}
   S = {S1,S2,S3}
   
   S1 = {4,1,3},    Cost(S1) = 5
   S2 = {2,5},      Cost(S2) = 10
   S3 = {1,4,3,2},  Cost(S3) = 3

Output: Minimum cost of set cover is 13 and 
        set cover is {S2, S3}

There are two possible set covers {S1, S2} with cost 15
and {S2, S3} with cost 13.

Почему это полезно?
Это была одна из NP-полных задач Карпа, что было показано в 1972 году. Другие приложения: покрытие ребер, покрытие вершин.
Интересный пример: IBM находит компьютерные вирусы (википедия)
Элементы - 5000 известных вирусов
Наборы — 9000 подстрок из 20 и более последовательных байтов от вирусов, не встречающихся в «хорошем» коде.
Обложка комплекта 180 была найдена. Достаточно поискать эти 180 подстрок, чтобы убедиться в существовании известных компьютерных вирусов.

Другой пример: предположим, что General Motors необходимо купить определенное количество различных материалов, и есть поставщики, которые предлагают различные предложения для различных комбинаций материалов (поставщик A: 2 тонны стали + 500 плиток за x долларов; поставщик B: 1 тонна стали). + 2000 плиток за $y и т. д.). Вы можете использовать покрытие набора, чтобы найти лучший способ получить все материалы при минимальных затратах.
Источник: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Обложка комплекта NP-Hard:
Для этой задачи не существует решения за полиномиальное время, поскольку она является известной NP-трудной задачей. Существует жадный приближенный алгоритм с полиномиальным временем, жадный алгоритм обеспечивает приближенный алгоритм Логна.

2-приблизительный жадный алгоритм:
Пусть U — совокупность элементов, {S 1 , S 2 , … S m } — набор подмножеств U, а Cost(S 1 ), C(S 2 ), … Cost(S m ) — стоимость подмножеств.

1) Let I represents set of elements included so far.  Initialize I = {}

2) Do following while I is not same as U.
    a) Find the set Si in {S1, S2, ... Sm} whose cost effectiveness is 
       smallest, i.e., the ratio of cost C(Si) and number of newly added 
       elements is minimum. 
       Basically we pick the set for which following value is minimum.
           Cost(Si) / |Si - I|
    b) Add elements of above picked Si to I, i.e.,  I = I U Si

Пример:
Давайте рассмотрим приведенный выше пример, чтобы понять жадный алгоритм.

Первая итерация:
я = {}

Стоимость нового элемента для S 1 = Cost(S 1 )/|S 1 – I| = 5/3

Стоимость нового элемента для S 2 = Cost(S 2 )/|S 2 – I| = 10/2

Стоимость нового элемента для S 3 = Cost(S 3 )/|S 3 – I| = 3/4

Поскольку S 3 имеет минимальное значение, добавляется S 3 , I становится {1,4,3,2}.

Вторая итерация:
я = {1,4,3,2}

Стоимость нового элемента для S 1 = Cost(S 1 )/|S 1 – I| = 5/0
Обратите внимание, что S 1 не добавляет новый элемент к I.

Стоимость нового элемента для S 2 = Cost(S 2 )/|S 2 – I| = 10/1
Обратите внимание, что S 2 добавляет к I только 5.

Жадный алгоритм обеспечивает оптимальное решение для приведенного выше примера, но он может не всегда обеспечивать оптимальное решение. Рассмотрим следующий пример.

S1 = {1, 2}
S2 = {2, 3, 4, 5}
S3 = {6, 7, 8, 9, 10, 11, 12, 13}
S4 = {1, 3, 5, 7, 9, 11, 13}
S5 = {2, 4, 6, 8, 10, 12, 13}

Let the cost of every set be same.

The greedy algorithm produces result as {S3, S2, S1}

The optimal solution is {S4, S5}

Доказательство того, что описанный выше жадный алгоритм является логарифмически приближенным.
Пусть OPT — стоимость оптимального решения. Скажем, (k-1) элементов покрыты до итерации вышеуказанного жадного алгоритма. Стоимость k-го элемента <= OPT / (n-k+1) (Обратите внимание, что стоимость элемента оценивается как стоимость его набора, деленная на количество элементов, добавленных его набором). Как мы получили этот результат? Поскольку k-й элемент еще не покрыт, существует S i , который не был покрыт до текущего шага жадного алгоритма, и он есть в OPT. Поскольку жадный алгоритм выбирает наиболее экономически эффективное S i , стоимость каждого элемента в выбранном наборе должна быть меньше, чем OPT, деленная на оставшиеся элементы. Поэтому стоимость k-го элемента <= OPT/|UI| (Обратите внимание, что пользовательский интерфейс представляет собой набор еще не охваченных элементов в жадном алгоритме). Значение |UI| это n - (k-1), что равно n-k+1.

Стоимость жадного алгоритма = сумма затрат n элементов 
                        [положив k = 1, 2..n в приведенной выше формуле]
                         <= (OPT/n + OPT(n-1) + ... + OPT/n) 
                         <= ОПТ(1 + 1/2 + ...... 1/n)
                        [Поскольку 1 + 1/2 + .. 1/n ≈ Log n]
                         <= ОПТ * Вход

Источник:
http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Эта статья предоставлена Харшитом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.

РЕКОМЕНДУЕМЫЕ СТАТЬИ