Bei einem Universum U von n Elementen ist eine Sammlung von Teilmengen von U say S = {S1, S2…,Sm} wobei jede Teilmenge Si eine hat verbundene Kosten. Finden Sie eine Untersammlung mit minimalen Kosten von S , die alle Elemente von U abdeckt.

Beispiel:

Warum ist es nützlich?Es war eines von Karps NP-vollständigen Problemen, das 1972 gezeigt wurde. Andere Anwendungen: Kantenabdeckung, Vertexabdeckung
Interessantes Beispiel: IBM findet Computerviren (Wikipedia)
Elemente- 5000 bekannte Viren
Sets- 9000 Teilzeichenfolgen von 20 oder mehr aufeinanderfolgenden Bytes von Viren, die nicht in ‚gutem‘ Code gefunden wurden.
Es wurde ein Setcover von 180 gefunden. Es genügt, nach diesen 180 Teilzeichenfolgen zu suchen, um die Existenz bekannter Computerviren zu überprüfen. Ein weiteres Beispiel: General Motors muss eine bestimmte Menge an verschiedenen Materialien kaufen, und es gibt Lieferanten, die verschiedene Angebote für verschiedene Materialkombinationen anbieten (Lieferant A: 2 Tonnen Stahl + 500 Fliesen für $ x; Lieferant B: 1 Tonne Stahl + 2000 Fliesen für $ y; usw.). Sie könnten set covering verwenden, um den besten Weg zu finden, alle Materialien zu erhalten und gleichzeitig die Kosten zu minimieren
Quelle: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Set Cover ist NP-hart:
Für dieses Problem gibt es keine Polynomzeitlösung, da das Problem ein bekanntes NP-hartes Problem ist. Es gibt einen Polynomialzeit-Greedy-Approximationsalgorithmus, der Greedy-Algorithmus liefert einen Logn-Approximationsalgorithmus.

Beispiel:
Betrachten wir das obige Beispiel, um den Greedy-Algorithmus zu verstehen.

Erste Iteration:
I = {}

Die Kosten pro neuem Element für S1 = Kosten(S1)/|S1 – I| = 5/3

Die Kosten pro neuem Element für S2 = Kosten(S2)/|S2 – I| = 10/2

Die Kosten pro neuem Element für S3 = Kosten(S3)/|S3 – I| = 3/4

Da S3 den Mindestwert S3 hat, wird I { 1,4,3,2}.

Zweite Iteration:
I = {1,4,3,2}

Die Kosten pro neuem Element für S1 = Cost(S1)/|S1 – I| = 5/0
Beachten Sie, dass S1 kein neues Element zu I hinzufügt.

Die Kosten pro neuem Element für S2 = Cost(S2)/|S2 – I| = 10/1
Beachten Sie, dass S2 nur 5 zu I hinzufügt.

Der Greedy-Algorithmus bietet die optimale Lösung für das obige Beispiel, bietet jedoch möglicherweise nicht immer die optimale Lösung. Betrachten Sie das folgende Beispiel.

Beweis, dass der obige Greedy-Algorithmus Logn-approximativ ist.
Lassen Sie OPT die Kosten der optimalen Lösung sein. Angenommen, (k-1) Elemente werden vor einer Iteration des obigen gierigen Algorithmus abgedeckt. Die Kosten des k-ten Elements i, das vor dem aktuellen Schritt des gierigen Algorithmus nicht abgedeckt wurde und in OPT vorhanden ist. Da der gierige Algorithmus das kostengünstigste Si auswählt, müssen die Kosten pro Element in der ausgewählten Menge kleiner sein als OPT geteilt durch die verbleibenden Elemente. Daher Kosten des k-ten Elements Kosten des gierigen Algorithmus = Summe der Kosten von n Elementen

Quelle: