алгоритм поиска минимального размера набора покрытия для задачи Set-cover

Question

В задаче «Покрытие множества» нам дан юниверс U, такой, что | U | = n, и множества S1, ……, Sk являются подмножествами U. Покрытие множества - это набор C некоторых из множеств изS1, ……, Sk, объединением которого является вся вселенная U.

Я пытаюсь придумать алгоритм, который найдет минимальное количество наборов покрытия, чтобы я мог показать, что жадный алгоритм для наборапокрытие иногда находит больше наборов.

Вот что я придумал:

повтор для каждого набора.1. Cover <-Seti (i = 1 ,,, n) 2. если набор не является подмножеством других наборов, возьмите этот набор в покрытие. </p>

, но в некоторых случаях он не работает,Пожалуйста, помогите мне выяснить алгоритм, чтобы найти минимальный набор покрытия.

Мне все еще не удается найти этот алгоритм в Интернете.У кого-нибудь есть предложения?

Answer 1

Обложка набора сложна с точки зрения NP, поэтому маловероятно, что будет алгоритм намного более эффективный, чем просмотр всех возможных комбинаций множеств и проверка, является ли каждая комбинация покрытием.

В основном, смотрите на все комбинации 1 набора, затем 2 набора и т. Д., Пока они не сформируют покрытие.

EDIT

Это пример псевдокода. Обратите внимание, что я не утверждаю, что это эффективно. Я просто утверждаю, что не существует гораздо более эффективного алгоритма (алгоритмы будут хуже полиномиального времени, если не будет обнаружено что-то действительно классное)

for size in 1..|S|:
    for C in combination(S, size):
          if (union(C) == U) return C

, где combination(K, n) возвращает все возможные наборы размера n, элементы которых происходят от K.

EDIT

Однако я не слишком уверен, зачем вам нужен алгоритм, чтобы найти минимум. В вопросе вы утверждаете, что хотите показать, что жадный алгоритм для покрытия множеств иногда находит больше множеств. Но это легко достигается с помощью контрпример (и контрпример показан в записи в википедии для покрытия обложки). Так что я довольно озадачен.

EDIT

Возможная реализация combination(K, n):

if n == 0: return [{}] //a list containing an empty set
r = []
for k in K:
    K = K \ {k} // remove k from K.
    for s in combination(K, n-1):
        r.append(union({k}, s))
return r

Но в сочетании с проблемой покрытия, вероятно, вместо этого нужно выполнить тест покрытия из базового случая n == 0. Ну.