Die leere Menge ist in der Menge der unabhängigen Mengen enthalten (diese Bedingung ist offensichtlich erfüllt, da die Summe der Elemente der leeren Menge 0 ist, was kleiner als 20 ist).
Wenn eine Menge B in I ist und A eine Teilmenge von B ist, dann ist auch A in I (diese Eigenschaft nennt man die Heritabilität oder "Vererbungseigenschaft").
Wenn A und B unabhängige Mengen sind und A mehr Elemente als B enthält, dann gibt es ein Element in A, das zu B hinzugefügt werden kann, so dass die resultierende Menge auch unabhängig ist (diese Eigenschaft nennt man die Austauscheigenschaft oder "Exchange-Eigenschaft").
3. Können nichts aus B hinzufügen ohne, dass die 20 überschritten wird und wir dadurch gegen die Definition von der Independence verstoßen
Die neue Aufgabe, die Sie hochgeladen haben, behandelt eine andere Eigenschaft von Matroiden. Es wird ein Unabhängigkeitssystem (E, I) betrachtet und man soll beweisen, dass die beiden folgenden Aussagen äquivalent sind:
(E, I) ist ein Matroid.
Für jede Teilmenge A ⊆ E gilt, dass wenn M und M' in I sind und maximal bezüglich A, dann haben M und M' die gleiche Mächtigkeit (Anzahl der Elemente), d.h. |M| = |M'|.
Eine Menge M wird als maximal bezüglich einer Teilmenge A bezeichnet, wenn M eine unabhängige Menge in I ist, die vollständig in A enthalten ist, und es keine größere unabhängige Menge gibt, die auch vollständig in A enthalten ist.
Um die Äquivalenz dieser Aussagen zu veranschaulichen, kann man das folgende einfache Beispiel verwenden:
Betrachten wir ein Unabhängigkeitssystem (E, I), wobei E = {1, 2, 3, 4} und die unabhängigen Mengen I alle Teilmengen von E sind, die nicht mehr als zwei Elemente enthalten.
Beispiel:
Für die Teilmenge A = {1, 2, 3} von E könnte eine maximale unabhängige Menge M = {1, 2} sein. Eine andere maximale unabhängige Menge M' = {2, 3} ist auch möglich.
Beide Mengen M und M' sind maximal bezüglich A, weil das Hinzufügen eines weiteren Elements von A die Menge nicht mehr unabhängig machen würde (da die Mengen in I definiert sind, um nicht mehr als zwei Elemente zu haben).
In diesem Beispiel haben M und M' die gleiche Mächtigkeit, nämlich |M| = |M'| = 2.
Für das gegebene System (E, I) können wir zeigen, dass die Eigenschaften eines Matroids erfüllt sind:
Es gibt eine Austauscheigenschaft, die besagt, dass, wenn eine unabhängige Menge M mehr Elemente als eine andere unabhängige Menge M' hat, es möglich ist, ein Element von M zu M' hinzuzufügen und M' bleibt unabhängig. Da alle maximalen unabhängigen Mengen bezüglich einer Teilmenge A die gleiche Größe haben, wird diese Bedingung immer erfüllt sein.
Daraus folgt, dass die Eigenschaft, dass alle maximalen unabhängigen Mengen bezüglich einer Teilmenge A die gleiche Mächtigkeit haben, äquivalent dazu ist, dass (E, I) ein Matroid ist.
Diese Übung demonstriert eine der grundlegenden Eigenschaften von Matroiden, nämlich dass in einem Matroid alle maximalen unabhängigen Mengen bezüglich einer beliebigen Teilmenge die gleiche Mächtigkeit haben müssen. Dies ist eine direkte Folge der Austauscheigenschaft von Matroiden.
Die Aufgabe bezieht sich auf die Anwendung des Greedy-Algorithmus (Gierigen Algorithmus) auf Matroide. Das Ziel ist es zu beweisen, dass wenn ein Element e1 in einem gewichteten Matroid (E, I) unabhängig ist, dann existiert eine optimale Teilmenge A von E, die e1 enthält.
Hier sind die Schritte, um dies zu beweisen, zusammen mit einem einfachen Beispiel:
Annahme: Die Elemente von E = {e1, e2, ..., em} sind nach abnehmendem Gewicht sortiert. Das bedeutet, dass e1 das Element mit dem höchsten Gewicht ist.
Unabhängigkeit von e1: Wir nehmen an, dass {e1} eine unabhängige Menge ist. Das bedeutet, dass es eine Teilmenge von E gibt, die nur aus e1 besteht und eine gültige unabhängige Menge in I ist.
Existenz einer optimalen Teilmenge: Wir wollen beweisen, dass es eine optimale Teilmenge A von E gibt, die e1 enthält. Eine optimale Teilmenge ist eine, die das größtmögliche Gesamtgewicht unter allen unabhängigen Mengen hat.
Verwendung des Greedy-Algorithmus: Der Greedy-Algorithmus würde damit beginnen, e1 zu wählen, weil es das Element mit dem höchsten Gewicht ist. Danach würde der Algorithmus weitere Elemente in abnehmender Gewichtsreihenfolge hinzufügen, solange die resultierende Menge unabhängig bleibt.
Optimalität: Angenommen, es gibt eine optimale Teilmenge A*, die e1 nicht enthält. Da e1 das Element mit dem höchsten Gewicht ist, könnte man e1 zu A* hinzufügen, wenn A* nicht bereits maximal ist. Wenn A* maximal ist, könnte man ein Element aus A* entfernen und e1 hinzufügen, um eine neue unabhängige Menge zu bilden, die mindestens so schwer wie A* ist. Dies würde bedeuten, dass A* nicht optimal sein kann, wenn sie nicht e1 enthält.
Einfaches Beispiel:
Angenommen, wir haben ein Matroid (E, I), wobei E = {a, b, c, d} und die Gewichte sind wie folgt: Gewicht(a) > Gewicht(b) > Gewicht(c) > Gewicht(d). Die Menge I besteht aus allen Teilmengen von E, die zwei oder weniger Elemente enthalten.
Nun nehmen wir an, dass {a} eine unabhängige Menge ist, da sie nur ein Element enthält und die Bedingung von I erfüllt.
Der Greedy-Algorithmus würde beginnen, indem er a wählt, weil es das Element mit dem höchsten Gewicht ist. Danach könnte er b hinzufügen, um die Menge {a, b} zu bilden, die immer noch unabhängig ist.
Wenn es eine andere optimale Teilmenge A* gäbe, die a nicht enthält, könnte sie beispielsweise {b, c} sein. Wir könnten dann aber a zu dieser Menge hinzufügen, um {a, b, c} zu bilden, was gegen die Regeln von I verstößt, da I nur Mengen mit bis zu zwei Elementen erlaubt. Stattdessen könnten wir c durch a ersetzen, um {a, b} zu bilden, was eine unabhängige Menge ist und ein höheres Gesamtgewicht als A* hat, wenn A* a nicht enthält. Daher muss jede optimale Teilmenge a enthalten.
Die Lösung, die Sie hochgeladen haben, ist ein formaler Beweis der Aussage, dass in einem gewichteten Matroid, wenn ein Element e1e1 unabhängig ist, dann gibt es eine optimale Teilmenge, die e1e1 enthält. Hier ist eine detaillierte Erklärung der Schritte und ein einfaches Beispiel:
Schritt 1: Trivialer Fall
Wenn kein solches unabhängiges Element e1e1 existiert, dann ist die einzige unabhängige Teilmenge die leere Menge, und die Behauptung ist trivialerweise wahr.
Schritt 2: Annahme einer optimalen Teilmenge ohne e1e1
Angenommen, es gibt eine optimale Teilmenge BB, die e1e1 nicht enthält. Da e1e1 das Element mit dem größten Gewicht ist und unabhängig ist, muss jedes Element in BB ein geringeres Gewicht als e1e1 haben.
Schritt 3: Konstruktion von AA
Beginne mit A={e1}A={e1}.
Nutze die Austauscheigenschaft des Matroids, um Elemente aus BB zu AA hinzuzufügen, ohne die Unabhängigkeit von AA zu verlieren, bis ∣A∣=∣B∣∣A∣=∣B∣.
An diesem Punkt unterscheiden sich AA und BB nur durch ein Element, d.h., AA hat e1e1 und BB hat ein anderes Element ee, und es gilt w(A)≥w(B)w(A)≥w(B).
Schritt 4: Widerspruch und Schlussfolgerung
Da BB optimal ist, gibt es zwei Fälle zu betrachten:
Fall 1: Wenn das Entfernen von ee aus BB und das Hinzufügen von e1e1 zu BB das gleiche Gewicht ergibt, dann ist auch AA optimal.
Fall 2: Wenn AA ein größeres Gewicht als BB hat, dann kann BB nicht optimal sein, was ein Widerspruch ist. Also muss jede optimale Menge e1e1 enthalten.
Nehmen wir an, wir haben ein Matroid mit der Elementmenge E={x,y,z}E={x,y,z} und Gewichten w(x)=3,w(y)=2,w(z)=1w(x)=3,w(y)=2,w(z)=1. Die unabhängigen Mengen sind alle Teilmengen von EE mit höchstens zwei Elementen.
e1e1 ist hier xx, da es das höchste Gewicht hat und unabhängig ist (da jede einzelne Menge in diesem Matroid unabhängig ist).
Angenommen, BB ist die optimale Teilmenge {y,z}{y,z} mit einem Gesamtgewicht von 3.
Wir beginnen mit A={x}A={x} mit einem Gewicht von 3.
Wir können yy nicht zu AA hinzufügen, ohne die Unabhängigkeitsregel zu verletzen, da wir bereits zwei Elemente haben.
Daher ist AA auch eine optimale Teilmenge, die e1e1 enthält, da sie das gleiche Gewicht wie BB hat, aber mit weniger Elementen.
Der Beweis zeigt, dass, wenn man mit dem Element mit dem höchsten Gewicht beginnt und die Austauscheigenschaft nutzt, man am Ende eine optimale Teilmenge konstruieren kann, die dieses Element enthält. Dies ist der Kern der Greedy-Choice-Eigenschaft bei Matroiden.
Um zu beweisen, dass die Struktur (E, I), die in der Aufgabe definiert ist, ein Matroid ist, müssen wir die drei grundlegenden Eigenschaften von Matroiden überprüfen:
Die leere Menge ist in I.
Jede Teilmenge einer Menge in I ist ebenfalls in I (Heritabilität oder Vererbung).
Wenn es zwei Mengen A und B in I gibt, wobei |A| < |B|, dann gibt es ein Element in B, das zu A hinzugefügt werden kann, so dass die resultierende Menge auch in I ist (Austauscheigenschaft).
Die gegebene Aufgabe liefert zwei Lemmata, die uns helfen, die dritte Eigenschaft zu beweisen.
Lemma 1: Ein Jobset kann rechtzeitig fertiggestellt werden, wenn seine Jobs in nicht abnehmender Reihenfolge nach Deadlines geordnet sind.
Lemma 2: Für jedes Jobset A, das aus n Jobs besteht, sind die folgenden Aussagen äquivalent:
Alle Jobs in A können rechtzeitig abgeschlossen werden.
Für alle t = 0, 1, 2, ..., n gilt, dass Nt(A)Nt(A) ≤ t, wobei Nt(A)Nt(A) die Anzahl der Jobs in A ist, deren Deadline t oder früher ist.
Wenn Jobs in A nicht abnehmend nach Deadlines geplant sind, ist kein Job verspätet.
Diese Lemmata zeigen, dass die Struktur (E, I), wo E alle Jobs und I alle Jobsets sind, die rechtzeitig abgeschlossen werden können, ein Matroid ist, weil:
Die leere Menge ist offensichtlich in I, da keine Jobs zu erledigen sind und somit keine Deadlines verpasst werden können.
Heritabilität: Jede Teilmenge eines Jobsets, das rechtzeitig fertiggestellt werden kann, kann auch rechtzeitig fertiggestellt werden, da das Entfernen von Jobs nicht dazu führt, dass verbleibende Jobs verspätet sind.
Austauscheigenschaft: Angenommen, wir haben zwei Jobsets A und B, die rechtzeitig fertiggestellt werden können, und |A| < |B|. Nach Lemma 2 haben wir Nt(A)Nt(A) ≤ t und Nt(B)Nt(B) ≤ t für alle t. Da |A| < |B|, gibt es einen Zeitpunkt t, bei dem Nt(B)>Nt(A)Nt(B)>Nt(A), was bedeutet, dass es einen Job in B gibt, der eine Deadline von t oder früher hat, aber nicht in A ist. Dieser Job kann zu A hinzugefügt werden, ohne die Deadlines zu verletzen, was die Austauscheigenschaft bestätigt.
Beispiel mit Erklärung:
Angenommen, wir haben folgende Jobs und Belohnungen (nach Sortierung):
Job 4: Deadline 4, Belohnung 70
Job 5: Deadline 2, Belohnung 60
Job 6: Deadline 4, Belohnung 50
Job 7: Deadline 3, Belohnung 40
Job 1: Deadline 1, Belohnung 30
Job 2: Deadline 4, Belohnung 20
Job 3: Deadline 6, Belohnung 10
Anwendung des Greedy-Algorithmus:
Wir fügen Job 4 hinzu (X = {4}). Keine Deadline wurde verpasst, N0(X)=N1(X)=0N0(X)=N1(X)=0, N4(X)=1N4(X)=1, alles ist in Ordnung.
Als nächstes fügen wir Job 5 hinzu (X = {4, 5}). N0(X)=N1(X)=0N0(X)=N1(X)=0, N2(X)=1N2(X)=1, was okay ist, weil die Anzahl der Jobs, die bis zur Deadline 2 abgeschlossen sein müssen, nicht größer als 2 ist.
Fügen wir Job 6 hinzu (X = {4, 5, 6}). N3(X)=1N3(X)=1, N4(X)=2N4(X)=2, was immer noch in Ordnung ist.
Job 7 wird hinzugefügt (X = {4, 5, 6, 7}). N3(X)=2N3(X)=2, N4(X)=3N4(X)=3, was immer noch funktioniert, weil die Anzahl der Jobs, die bis zur Deadline 4 abgeschlossen sein müssen, nicht größer als 4 ist.
Fügen wir nun Job 1 hinzu (X = {4, 5, 6, 7, 1}), es zeigt sich, dass N1(X)N1(X) größer als 1 wäre, was bedeutet, dass wir nicht beide Jobs (4 und 1) bis zur Deadline 1 abschließen können. Daher wird Job 1 nicht hinzugefügt.
Versuchen wir Job 2 hinzuzufügen (X = {4, 5, 6, 7, 2}), wir sehen wieder, dass N4(X)N4(X) größer als 4 wäre, was nicht funktioniert. Daher wird Job 2 nicht hinzugefügt.
Schließlich fügen wir Job 3 hinzu (X = {4, 5, 6, 7, 3}). Es gibt keine Überschreitung der Deadlines, alle Jobs können rechtzeitig abgeschlossen werden, also ist X = {4, 5, 6, 7, 3} der finale Plan.
Last changed4 months ago
