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

Question

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

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

Ниже то, что я придумал:

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

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

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

Answer 1

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

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

РЕДАКТИРОВАТЬ

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

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 вместо. Что ж.