En el problema de la cobertura de conjuntos, se nos da un universo U, de modo que | U | = n, y los conjuntos S1, ......, Sk son subconjuntos de U. Una cubierta de conjunto es una colección C de algunos de los conjuntos de S1, ... ..., Sk cuya unión es el universo entero U.

Estoy tratando de encontrar un algoritmo que encuentre el número mínimo de cobertura de conjunto para que pueda mostrar que el algoritmo codicioso para la cobertura de conjunto a veces encuentra más conjuntos.

Lo siguiente es lo que se me ocurrió:

Repita para cada conjunto. 1. Cover <-Seti (i = 1 ,,, n) 2. si un conjunto no es un subconjunto de ningún otro conjunto, entonces tome ese conjunto en la cubierta.

pero no funciona para algunos casos. Por favor, ayúdame a encontrar un algoritmo para encontrar la cobertura mínima establecida.

Todavía tengo problemas para encontrar este algoritmo en línea. Alguien tiene alguna sugerencia?