Algorithmus Mengenüberdeckung

Question

Gegeben eine Menge U und eine Menge S, die Teilmengen von U enthält. Eine Überdeckung ist die kleinste Teilmenge C von S, deren Vereinigung U ergibt. Für die TeilmengenS1 = (1; 3; 5), S2 = (2; 4), S3 = (1; 4) und S4 = (2; 5) wäre beispielsweise (S1; S2) eine Überdeckung von U = (1; 2; 3; 4; 5).

Finden Sie ein Gegenbeispiel für den folgenden Algorithmus zum Finden einer Überdeckung:
Wähle immer die Teilmenge mit der größten Anzahl an noch nicht überdeckten
Elementen aus, solange bis alle Elemente aus U abgedeckt sind.



Ich habe mehrere Aufgaben dieser Art, weiß aber nicht wirklich wie ich es angehen soll. Wenn mir das jemand an dem Beispiel erklären könnte, würde mir das bestimmt weiterhelfen.

Comments

Vom Duplikat:

Titel: Algorithmus - Mengenüberdeckung

Stichworte: algorithmus,informatik

Gegeben eine Menge U und eine Menge S, die Teilmengen von U enthält. Eine Überdeckung ist die kleinste Teilmenge C von S, deren Vereinigung U ergibt. Für die TeilmengenS1 = (1; 3; 5), S2 = (2; 4), S3 = (1; 4) und S4 = (2; 5) wäre beispielsweise (S1; S2) eine Überdeckung von U = (1; 2; 3; 4; 5).

Finden Sie ein Gegenbeispiel für den folgenden Algorithmus zum Finden einer Überdeckung:
Wähle immer die Teilmenge mit der größten Anzahl an noch nicht überdeckten
Elementen aus, solange bis alle Elemente aus U abgedeckt sind.

Ich habe mehrere Aufgaben dieser Art, weiß aber nicht wirklich wie ich es angehen soll. Wenn mir das jemand an dem Beispiel erklären könnte, würde mir das bestimmt weiterhelfen.

Answer 1

Wähle immer die Teilmenge mit der größten Anzahl an noch nicht überdeckten Elementen aus.

U = {1, 2, 3, 4, 5, 6}, S = {{1, 2, 3, 4}, {1, 2, 5}, {3, 4, 6}}

wie ich es angehen soll.

Probieren. Wenn's fehlschlägt, dann überlege, woran es gescheitert ist.