un algorithme pour trouver la couverture de jeu de taille minimum pour le problème Set-cover

Question

Dans le problème Set Covering, on nous donne un univers U, tel que | U | = n, et les ensembles S1, ......, Sk sont des sous-ensembles de U. Une couverture d'ensemble est une collection C de certains des ensembles de S1, ......, Sk dont l'union est l'univers entier U.

J'essaie de trouver un algorithme qui va trouver le nombre minimum de mettre en couverture pour que je puisse montrer que l'algorithme glouton pour la couverture de l'ensemble trouve parfois plus de sets.

Voici ce que je suis venu avec:

répétition pour chaque ensemble. 1. Couvrir < -Seti (i = 1 ,,, n) 2. Si un ensemble n'est pas un sous-ensemble d'autres ensembles, alors prenez ce jeu en couverture.

mais cela ne fonctionne pas dans certains cas. S'il vous plaît aidez-moi à trouver un algorithme pour trouver la couverture minimale.

Je rencontre toujours des problèmes pour trouver cet algorithme en ligne. Quelqu'un a une suggestion?

Answer 1

La couverture de l'ensemble est NP-difficile, il est donc peu probable qu'il y ait un algorithme beaucoup plus efficace que de regarder toutes les combinaisons d'ensembles possibles et de vérifier si chaque combinaison est une couverture.

Fondamentalement, regardez toutes les combinaisons de 1 jeu, puis 2 jeux, etc. jusqu'à ce qu'ils forment un couvercle.

EDIT

Voici un exemple pseudocode. Notez que je ne prétends pas que c'est efficace. Je demande simplement qu'il n'y a pas un algorithme beaucoup plus efficace (algorithmes sera pire que le temps polynomiale à moins que quelque chose vraiment cool est découvert)

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

où combination(K, n) retourne tous les ensembles possibles de taille n dont les éléments proviennent de K.

EDIT

Cependant, je ne suis pas trop sûr pourquoi vous avez besoin d'un algorithme pour trouver le minimum. Dans la question, vous indiquez que vous voulez montrer que l'algorithme glouton pour la couverture d'ensemble trouve parfois plus de jeux. Mais ceci est facilement réalisé via un contre-exemple (et un contre-exemple est montré dans l'entrée wikipedia pour la couverture du set). Donc je suis assez perplexe.

EDIT

Une mise en œuvre possible de combination(K, n) est:

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 

Mais en combinaison avec le problème de la couverture, on veut probablement effectuer le test de la couverture du boîtier de base n == 0 à la place. Bien.