Gitt et univers U av n elementer, en samling av undergrupper Av U si S = {S1, S2…, Sm} hvor hver undergruppe Si Har en tilknyttet kostnad. Finn en minimumskostnadsdelsamling Av S som dekker alle elementene I U.

Eksempel:

Hvorfor er Det nyttig?
Det var En Av Karps np-komplette problemer, vist seg å være så i 1972. Andre programmer: edge dekker, vertex cover
Interessant eksempel: IBM finner datavirus (wikipedia)
Elementer-5000 kjente virus
Sett-9000 substrings av 20 eller flere påfølgende byte fra virus, ikke funnet i ‘ god ‘ kode.
et sett cover av 180 ble funnet. Det er nok å søke etter disse 180 substrings for å verifisere eksistensen av kjente datavirus. Et annet eksempel: Vurder General Motors må kjøpe en viss mengde varierte forsyninger, og det er leverandører som tilbyr ulike avtaler for ulike kombinasjoner av materialer (Leverandør a: 2 tonn stål + 500 fliser for $x; Leverandør B: 1 tonn stål + 2000 fliser for $y; etc.). Du kan bruke set dekker for å finne den beste måten å få alle materialer samtidig minimere kostnadene
Kilde: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Set Cover er NP-Hard:
Det er ingen polynomisk tid løsning tilgjengelig for dette problemet som problemet er en kjent NP-Hard problem. Det er en polynomisk Tid Grådig omtrentlig algoritme, den grådige algoritmen gir En Logn omtrentlig algoritme.

Eksempel:
la oss vurdere eksempelet ovenfor for å forstå Grådig Algoritme.

Første Iterasjon:
I = {}

kostnaden per nytt element For S1 = Kostnad(S1)/|S1 – i| = 5/3

kostnaden per nytt element For S2 = Kostnad(S2)/|S2 – i| = 10/2

kostnaden per nytt element For S3 = Kostnad(S3)/|S3 – I| = 3/4

Siden S3 har minimumsverdi s3 er lagt til, blir jeg {1,4,3,2}.

Andre Iterasjon:
i = {1,4,3,2}

kostnaden per nytt element For S1 = Kostnad (S1) / / S1-I / = 5/0
Merk At S1 ikke legger til noe nytt element Til I.

kostnaden per nytt element For S2 = Kostnad(S2)/|S2 – i| = 10/1
Merk At S2 bare legger til 5 Til I.

den grådige algoritmen gir den optimale løsningen for eksempelet ovenfor, men det kan ikke gi optimal løsning hele tiden. Tenk på følgende eksempel.

Bevis på at den ovennevnte grådige algoritmen Er Logn omtrentlig.
La OPT være kostnaden for optimal løsning. Si (k-1) elementer er dekket før en iterasjon av over grådig algoritme. Kostnaden for k ‘ th-elementet i som ikke er dekket før det nåværende trinnet med grådig algoritme, og det er der I OPT. Siden grådig algoritme plukker den mest kostnadseffektive Si, per-element-kostnad i plukket sett må være mindre ENN OPT delt på gjenværende elementer. Derfor koster k ‘ th element Cost Of Greedy Algorithm = Summen av kostnader for n elementer

Kilde: