dat un univers U de n elemente, o colecție de subseturi de U Spune S = {S1, S2…,Sm} unde fiecare subset Si are un cost asociat. Găsiți o subcolecție cost minim de S, care acoperă toate elementele de U.

exemplu:

De ce este util?
A fost una dintre problemele NP-complete ale lui Karp, care s-a dovedit a fi așa în 1972. Alte aplicații: acoperire margine,capac vertex
exemplu interesant: IBM găsește viruși de calculator (wikipedia)
elemente – 5000 de viruși cunoscuți
seturi – 9000 de subșiruri de 20 sau mai mulți octeți consecutivi din viruși, care nu se găsesc în codul ‘bun’.
A fost găsită o copertă de 180. Este suficient să căutați aceste 180 de subșiruri pentru a verifica existența virușilor de calculator cunoscuți.

Un alt exemplu: luați în considerare că General Motors trebuie să cumpere o anumită cantitate de consumabile variate și există furnizori care oferă diverse oferte pentru diferite combinații de materiale (furnizor A: 2 tone de oțel + 500 plăci pentru $x; furnizor B: 1 tonă de oțel + 2000 plăci pentru $y; etc.). Ai putea folosi acoperire set pentru a găsi cel mai bun mod de a obține toate materialele în timp ce minimizarea costurilor Sursa:http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

capacul Set este NP-Hard:
nu există nici o soluție de timp polinomiale disponibile pentru această problemă ca problema este o problemă cunoscută NP-Hard. Există un algoritm aproximativ greedy timp polinomial, algoritmul greedy oferă un algoritm aproximativ Logn.

exemplu:
să luăm în considerare exemplul de mai sus pentru a înțelege algoritmul Greedy.

prima iterație:
I = {}

costul per element nou pentru S1 = Cost (S1) / / S1-I / = 5/3

costul per element nou pentru S2 = Cost (S2)| / S2 – I / = 10/2

costul per element nou pentru S3 = Cost(S3)/|S3 – I| = 3/4

deoarece S3 are valoarea minimă se adaugă S3, i devine {1,4,3,2}.

A doua iterație:
I = {1,4,3,2}

costul per element nou pentru S1 = Cost(S1)|| S1 – I/ = 5/0
rețineți că S1 nu adaugă niciun element nou la I.

costul per element nou pentru S2 = Cost(S2)|| S2 – I / = 10/1
rețineți că S2 adaugă doar 5 la I.

algoritmul greedy oferă soluția optimă pentru exemplul de mai sus, dar este posibil să nu ofere soluția optimă tot timpul. Luați în considerare următorul exemplu.

dovada că algoritmul greedy de mai sus este Logn aproximativă.
să OPT fi costul de soluție optimă. Spune (k-1) elementele sunt acoperite înainte de o iterație a algoritmului greedy de mai sus. Costul elementului k ‘ TH i care nu a fost acoperit înainte de Pasul actual al algoritmului greedy și este acolo în OPT. Deoarece algoritmul greedy alege cel mai rentabil Si, per-element-cost din setul ales trebuie să fie mai mic decât OPT împărțit la elementele rămase. Prin urmare, costul elementului k ‘ costul algoritmului Greedy = suma costurilor n elemente

Sursa: