ein Algorithmus zum Finden der Mindestgröße für das Set-Cover-Problem

Question

Im Set-Covering-Problem erhalten wir ein Universum U, so dass | U | = n und die Mengen S1, ......, Sk Teilmengen von sind U. Set Cover ist eine Sammlung C von einigen der Sets von S1, ......, Sk, deren Union das gesamte Universum U. ist.

Ich versuche, mit einem Algorithmus zu kommen, der die minimale Anzahl finden wird setze das Cover so, dass ich zeigen kann, dass der gierige Algorithmus für das Set-Covering manchmal mehr Sets findet.

Es folgt, was ich kam mit:

Wiederholung für jeden Satz. 1. Cover < -Set (i = 1 ,,, n) 2. Wenn ein Set keine Untermenge von anderen Sets ist, nehmen Sie das Set in Deckung.

aber es funktioniert nicht für einige Fälle. Bitte helfen Sie mir herauszufinden, einen Algorithmus, um die Mindestmenge Abdeckung zu finden.

Ich habe immer noch Probleme, diesen Algorithmus online zu finden. Hat jemand einen Vorschlag?

Answer 1

Die Abdeckung ist NP-hart, daher ist es unwahrscheinlich, dass ein Algorithmus viel effizienter ist, als alle möglichen Kombinationen von Sätzen zu betrachten und zu prüfen, ob es sich bei jeder Kombination um eine Abdeckung handelt.

Betrachten Sie im Grunde alle Kombinationen von 1 Satz, dann 2 Sätze usw., bis sie eine Abdeckung bilden.

EDIT

Dies ist ein Beispiel Pseudo-Code. Beachten Sie, dass ich nicht behaupte, dass dies effizient ist. Ich behaupte einfach, dass es nicht ein viel effizienter Algorithmus (Algorithmen schlechter als Polynom Zeit sein wird, es sei denn, etwas wirklich cool entdeckt wird)

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

wo combination(K, n) gibt alle möglichen Sätze von Größe n deren Elemente kommen aus K.

EDIT

Aber ich bin nicht sicher, warum Sie einen Algorithmus brauchen das Minimum zu finden. In der Frage geben Sie an, dass Sie zeigen möchten, dass der Greedy-Algorithmus für die Mengenabdeckung manchmal mehr Mengen findet. Dies kann jedoch leicht über ein Gegenbeispiel erreicht werden (und ein Gegenbeispiel wird im Wikipedia-Eintrag für die gesetzte Deckung gezeigt). Ich bin also ziemlich verwirrt.

EDIT

Eine mögliche Implementierung von combination(K, n) ist:

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 

Aber in Kombination mit dem Cover Problem, will man wahrscheinlich den Test der Abdeckung von dem Basisfall n == 0 stattdessen auszuführen. Gut.