Infelizmente sua tarefa é NP completa.
É óbvio que todos os conjuntos de sua solução devem conter esse único elemento (vamos chamar de x
). Também é óbvio que conjuntos que não contenham x
não podem ser incluídos na solução, então vamos concordar que eles não estarão presentes em S.
Permite criar uma nova coleção de conjuntos S '= {S' k | S k ∈S | S ' k = U \ S k } (ou seja, cada conjunto consiste daqueles itens do universo que ele não continha inicialmente). Em outras palavras, S ' k define os elementos de U
que serão removidos da interseção se tomarmos S k .
Agora, para resolver a tarefa, você deve selecionar o número mínimo de conjuntos de S 'que cobrirá U
. Qual é a definição do problema da Cobertura de Conjuntos que você mencionou no começo.