Étant donné un univers U de n éléments, une collection de sous-ensembles de U disons S = {S1, S2…, Sm} où chaque sous-ensemble Si a un coût associé. Trouvez une sous-collection de coût minimum de S qui couvre tous les éléments de U.

Exemple:

Pourquoi est-ce utile?
C’était l’un des problèmes NP-complets de Karp, montré comme tel en 1972. Autres applications: couverture de bord, couverture de sommet
Exemple intéressant: IBM trouve des virus informatiques (wikipedia)
Éléments – 5000 virus connus
Ensembles – 9000 sous-chaînes de 20 octets consécutifs ou plus provenant de virus, introuvables dans le  » bon  » code.
Un ensemble de couverture de 180 a été trouvé. Il suffit de rechercher ces 180 sous-chaînes pour vérifier l’existence de virus informatiques connus.

Un autre exemple: Considérons que General Motors doit acheter une certaine quantité de fournitures variées et qu’il existe des fournisseurs qui proposent diverses offres pour différentes combinaisons de matériaux (Fournisseur A: 2 tonnes d’acier + 500 tuiles pour $ x; Fournisseur B: 1 tonne d’acier + 2000 tuiles poury y; etc.). Vous pouvez utiliser set covering pour trouver le meilleur moyen d’obtenir tous les matériaux tout en minimisant les coûts
Source: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Set Cover est NP-Dur:
Il n’y a pas de solution de temps polynomial disponible pour ce problème car le problème est un problème NP-dur connu. Il existe un algorithme approximatif gourmand en temps polynomial, l’algorithme gourmand fournit un algorithme approximatif Logn.

Exemple:
Considérons l’exemple ci-dessus pour comprendre l’algorithme gourmand.

Première Itération:
I={}

Le coût par nouvel élément pour S1 = Coût(S1)/|S1–I|=5/3

Le coût par nouvel élément pour S2 = Coût(S2)/|S2–I|=10/2

Le coût par nouvel élément pour S3 = Coût(S3)/|S3–I|=3/4

Puisque S3 a la valeur minimale S3 est ajouté, I devient { 1,4,3,2 }.

Deuxième Itération:
I= {1,4,3,2}

Le coût par nouvel élément pour S1 = Cost(S1)|/S1–I/=5/0
Notez que S1 n’ajoute aucun nouvel élément à I.

Le coût par nouvel élément pour S2 = Cost(S2)|/S2–I/=10/1
Notez que S2 n’ajoute que 5 à I.

L’algorithme greedy fournit la solution optimale pour l’exemple ci-dessus, mais il peut ne pas fournir la solution optimale tout le temps. Considérons l’exemple suivant.

Preuve que l’algorithme gourmand ci-dessus est approximatif Logn.
Soit le coût de la solution optimale. Disons que (k-1) les éléments sont couverts avant une itération de l’algorithme gourmand ci-dessus. Le coût du k’th élément i qui n’a pas été couvert avant l’étape actuelle de l’algorithme gourmand et il est là en OPT. Étant donné que l’algorithme greedy choisit le Si le plus rentable, le coût par élément dans l’ensemble sélectionné doit être inférieur à OPT divisé par les éléments restants. Par conséquent coût du k’th élément Coût de l’algorithme Gourmand = Somme des coûts de n éléments

Source: