No problema Cobertura de conjuntos, recebemos um universo U, de modo que | U | = n, e os conjuntos S1, ……, Sk são subconjuntos de U. Uma capa de conjunto é uma coleção C de alguns dos conjuntos de S1,… …, Sk cuja união é o universo inteiro U.

Estou tentando criar um algoritmo que encontre o número mínimo de cobertura de conjuntos, para que eu possa mostrar que o algoritmo ganancioso para cobertura de conjuntos às vezes encontra mais conjuntos.

A seguir, é o que eu vim com:

repita para cada conjunto. 1. Capa <-Seti (i = 1 ,,, n) 2. se um conjunto não for um subconjunto de outros conjuntos, leve-o para a cobertura.

mas não está funcionando em alguns casos. Por favor, ajude-me a descobrir um algoritmo para encontrar a cobertura mínima do conjunto.

Ainda estou com problemas para encontrar esse algoritmo online. Alguém tem alguma sugestão?