Matroide und Submodularität erklärt
Stellen Sie sich vor: Sieben Standorte sollen durch ein Leitungsnetz verbunden werden, möglichst billig. Sie legen die billigste Leitung, dann die nächstbilligste und überspringen jede, die einen Rundweg schließen würde. So entsteht das billigste Netz. Nun gilt zusätzlich: höchstens drei Leitungen je Standort. Dasselbe Vorgehen liegt in einem Beispiel mit sieben Standorten und einer billigen Nabe 9,6 Prozent über den Kosten des besten Netzes. Wann findet das einfache Vorgehen das Beste, und woran sieht man es vorher?
Dieses Vorgehen heißt Greedy: Man nimmt jeweils das Nächstbeste, solange die Auswahl zulässig bleibt. Ob es das Beste findet, hängt an einer Struktur namens Matroid: einer Regel, welche Leitungsmengen zulässig sind, mit einer Tauscheigenschaft. Gibt es ein größeres zulässiges Netz, lässt sich einem kleineren stets eine Leitung daraus hinzufügen. Die Leitfrage dieser Linie lautet: Wann ist Greedy das Beste, welche Garantie bleibt, wenn eine Regel diese Struktur nicht hat, und was kostet es, das passende Verfahren zu finden?
Siebzehn Stücke gehen dem nach, die meisten am selben Leitungsnetz, das immer neue Regeln bekommt. Die ersten fragen, warum die billigste Leitung zuerst gewinnt, wo sie mit Nebenbedingungen scheitert und wie sich prüfen lässt, ob eine Regel die Tauscheigenschaft hat. Die zweiten verbinden Regeln: ein Netz ohne Rundweg, in dem zugleich je Kabelfarbe höchstens eine Leitung liegt, oder zwei getrennte Netze ohne gemeinsame Leitung. Dazu gehört ein Fall, in dem jede weitere Leitung weniger bringt (die zweite deckt weniger neue Haushalte ab) und Greedy dennoch eine Garantie behält. Die dritten lassen Annahmen los: Leitungsangebote kommen nacheinander, Erfolgschancen sind unbekannt, und am Ende steht die Frage nach dem passenden Verfahren. Die Erklärseite zu Greedy und Tausch erzählt am Leitungsnetz im Alltagsbild, wie die Regel und das Tauschen zusammenhängen.
Was diese Linie ist und was nicht: Es sind Modelle mit gewählten Annahmen, gerechnet an erzeugten Leitungsplänen. Mehrere Demos prüfen die Aussagen nur an kleinen Systemen nach, ohne sie zu beweisen. Eine Garantie beschreibt den schlechtesten Fall; bei zufälligen Kosten liegt Greedy meist deutlich näher am Besten.
In short: Covers matroids and submodular functions: why greedy is optimal exactly on matroids, intersections and unions, the matroid polytope, greedy guarantees under diminishing returns, online and learning variants, the Tutte polynomial and choosing a method
Hintergrund zum Thema: Netzwerkdesign.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Greedy und Tausch verständlich erklärt
Warum die Regel „billigste Leitung zuerst, solange kein Rundweg entsteht“ das billigste Leitungsnetz findet, woran man das erkennt und was kippt, wenn eine Höchstzahl an Leitungen je Standort dazukommt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Herleitungen und Messwerten.
Vom Spannbaum zur Verfahrenswahl: ein Rückgrat, Strukturen und Garantien
Die Wurzel ist Greedy beim Spannbaum: Kruskals Regel findet das Beste, und ein Tauschargument erklärt warum. Die Unabhängigkeitssysteme zeigen, wo dieselbe Regel unter Nebenbedingungen scheitert, das Matroid benennt die Struktur, die den Unterschied macht, und Rang, Basen und Kreise machen sie rechenbar. Greedy genau dann optimal schließt den Kreis in beiden Richtungen; von dort gehen die Wege zur Dualität, zu zwei Strukturen gleichzeitig (Schnitt, gewichteter Schnitt, Vereinigung), zum Polytop und zur Submodularität ab, für den Fall, dass die Struktur kein Matroid mehr ist.
Die Submodularität führt zu Verfahren über Greedy hinaus und zur Minimierung. Angebote nacheinander und unbekannte Nutzen führen zum Sekretärproblem und zu den Bandits, das Tutte-Polynom zählt, was die Struktur hergibt, und die Verfahrenswahl misst, was das Fragen kostet.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Gestrichelt umrandet sind Demos aus anderen Linien: Kruskal aus den Spannbäumen, Greedy-Matching aus dem Matching, die LP-Dualität aus der Linearen Programmierung, die Einflussmaximierung aus der Netzwerkanalyse, Graph Cuts aus dem Netzwerkfluss, das Sekretärproblem aus den Online-Algorithmen, Bandit statt A/B-Test aus den Experimenten und das Tutte-Polynom für Graphen aus dem Abzählen. Doppelt umrandet ist die Verfahrenswahl, in der mehrere Wege zusammenlaufen.
Verwandt in anderen Linien
- Spannbäume — Die Kruskal-Demo zeigt den Ablauf von Greedy am Spannbaum; die Demo Greedy und Tausch fragt nach dem Grund, dem Tauschargument, und misst ihn am Plan. Die Unabhängigkeitssysteme fragen dann, wo dieselbe Regel unter Nebenbedingungen scheitert.
- Matching-Algorithmen — Die Greedy-Matching-Demo nimmt die billigste Zuordnung zuerst; der Matroid-Schnitt erklärt, warum das scheitern kann: Eine Zuordnung ist der Schnitt zweier Matroide, und Greedy erreicht dort mindestens die Hälfte des Optimums, der Austauschgraph das Optimum.
- Lineare Programmierung — Die LP-Dualität liefert Schattenpreise für gewöhnliche lineare Programme; das Matroid-Polytop zeigt, warum das LP einer Matroid-Aufgabe von selbst ganzzahlig ausfällt und Greedy es löst.
- Netzwerkanalyse — Die Einflussmaximierung wählt gierig, wen man zuerst informiert; die Demo Submodularität zeigt, woher die Garantie für diese Gier stammt: der abnehmende Zusatznutzen.
- Netzwerkfluss — Der Min-Cut in der Graph-Cuts-Demo trennt glatte Zonen; die Submodulare Minimierung zeigt ihn als Spezialfall und rechnet auch Kosten, für die es keine Netzdarstellung gibt.
- Online-Algorithmen — Die Sekretärproblem-Demo wählt einen einzigen Zuschlag; das Matroid-Sekretärproblem erlaubt mehrere, solange sie zusammen zulässig bleiben.
- Experimente und Wirkungsmessung — Die Bandit-Demo lernt den besten von mehreren Armen; die Matroid-Bandits lernen eine ganze Basis, bei der jede gewählte Leitung eine eigene Rückmeldung liefert.
- Abzählen und erzeugende Funktionen — Das Tutte-Polynom von Graphen zählt mit dem Frontier-Verfahren; die Matroid-Demo verallgemeinert es auf beliebige Matroide, mit Dualität und Codes.
Greedy und Tausch: Warum die Regel gewinnt
Sehen Sie, wie beim billigsten Leitungsnetz die Greedy-Regel „billigste Leitung zuerst, solange kein Rundweg entsteht“ gewinnt: Auf den gemessenen Plänen ohne Obergrenze zählt nur die Reihenfolge der Kosten, und verbessernder Tausch führt zum Optimum. Ein Regler fügt eine Obergrenze je Standort hinzu. Der Haken: Im Preset mit sieben Standorten (Seed 8), billiger Nabe und höchstens drei Leitungen liegt Greedy 9,6 Prozent über dem Besten.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Unabhängigkeitssysteme: Wo Greedy scheitert und wie schlimm
Verfolgen Sie, wie sich aus einer Regel wie „höchstens drei Leitungen je Standort“ allein ausrechnen lässt, wie weit die Greedy-Regel (immer das Nächstbeste nehmen, solange es zulässig bleibt) hinter dem Optimum zurückfallen kann: Der Rangquotient nennt die Garantie. Mit gezielt gebauten Gewichten erreicht Greedy im Preset 60,0 Prozent des Optimums, bei Rangquotient 0,6. Der Haken: Mit Zufallsgewichten liegt Greedy meist deutlich näher am Optimum; die Garantie beschreibt den Schlimmstfall.
Demo starten →Das Matroid: Austauschaxiom und Beispiele
Sehen Sie, wie sich prüfen lässt, ob eine Zulässigkeitsregel die Struktur hat, auf der Greedy verlässlich arbeitet: Ist eine zulässige Auswahl kleiner als eine andere, muss sich ihr ein Element der größeren hinzufügen lassen (Austauschaxiom; solche Systeme heißen Matroide). Die Demo prüft elf Systeme und zeigt bei einem Verstoß ein Beispielpaar. Der Haken: Bei fünf nummerierten Elementen sind nur 5,4 Prozent aller Regelsysteme Matroide.
Demo starten →Rang, Basen, Kreise, Abschluss
Verfolgen Sie, wie sich dasselbe Matroid auf fünf gleichwertige Weisen beschreiben lässt, etwa durch die größten zulässigen Mengen (Basen) oder die kleinsten unzulässigen (Kreise), und dass ein Tausch im Leitungsnetz dem Rundweg folgt, der beim Dazulegen einer Leitung entsteht. Der Haken: Die Listen sind sehr verschieden lang; auf dem Plan mit sieben Standorten (Seed 8) stehen 32 Kreise gegen 1 316 zulässige Mengen.
Demo starten →Greedy genau dann optimal: Das Matroid als Bedingung
Sehen Sie, dass Greedy für jede Gewichtung genau dann optimal ist, wenn das System ein Matroid ist, und wie sich aus dem Verstoßpaar des Austauschaxioms Gewichte bauen lassen, bei denen Greedy scheitert. Mit Zufallsgewichten scheitert Greedy bei Rundwegverbot plus Farbregel (höchstens eine Leitung je Kabelfarbe; Plan mit sieben Standorten, Seed 8) nur bei 4,2 Prozent von 1 000 Versuchen. Der Haken: Gezeigt ist das nur an kleinen Systemen, kein Beweis.
Demo starten →Dualität und Minoren: Kreis und Schnitt
Verfolgen Sie, wie jedes Matroid ein Gegenstück hat, das Dual: Aus den Basen werden ihre Komplemente, aus den Rundwegen eines Netzes seine minimalen Schnitte, also kleinste Leitungsmengen, deren Wegfall das Netz trennt. Die Demo bestätigt das an allen 497 Matroiden mit höchstens fünf Elementen ohne Abweichung. Der Haken: Als Leitungsnetz zeichnen lässt sich das Dual nur bei kreuzungsfrei zeichenbaren Plänen, und manche Matroide gehören zu gar keinem Netz.
Demo starten →Matroid-Schnitt: Zwei Strukturen auf einmal
Sehen Sie, wie zwei Regeln gleichzeitig gelingen, etwa ein Spannbaum ohne Kreis, in dem jede Kabelfarbe höchstens einmal vorkommt. Greedy, also Nehmen in fester Reihenfolge, bleibt unter dem Optimum: Auf dem Standardplan (7 Standorte, Seed 8, 6 Farben) passiert das in 47,1 Prozent von 1 000 Zufallsreihenfolgen. Tauschzüge in einem Austauschgraphen finden die größte Lösung. Der Haken: Bei drei Regeln gilt es als nicht mehr effizient lösbar (NP-schwer).
Demo starten →Gewichteter Matroid-Schnitt: Der billige Weg
Verfolgen Sie, wie aus dem Austauschgraphen ein Preisschild wird: Jede gewählte Leitung kostet, jede ersetzte spart ihre Kosten, und der kürzeste Weg liefert zu jeder Leitungszahl die billigste zulässige Auswahl. Greedy nach Kosten bleibt auf dem Standardplan (7 Standorte, Seed 8) bei 4 Elementen für 77 stecken, obwohl 5 möglich sind. Der Haken: Bei gleich langen Wegen entscheidet die Knotenzahl, sonst kann eine unzulässige Auswahl entstehen.
Demo starten →Matroid-Vereinigung: Disjunkte Strukturen packen
Verfolgen Sie, wie sich in einem Leitungsnetz getrennte Strukturen packen lassen: zwei Spannbäume ohne gemeinsame Leitung als Ersatz, oder möglichst wenige Wälder für alle Leitungen. Die Vereinigung ist wieder ein Matroid, also eine Struktur mit Austauschregel, und Wege im Austauschgraphen bringen Leitung um Leitung unter. Der Haken: Auf dem Standardplan (7 Standorte, Seed 8) gibt es keine zwei solchen Spannbäume, für alle Leitungen braucht man 3 Wälder.
Demo starten →Matroid-Polytop: Warum das LP ganzzahlig ist
Verfolgen Sie, wie sich der billigste Spannbaum als lineares Programm schreiben lässt, ohne dass Bruchteile herauskommen. Die naheliegende Schnittformulierung hat in einer Messreihe bei 3, 5 und 8 von je 20 Plänen eine Lücke; die Rangungleichungen des Waldes haben bei keinem eine. Ein Schnittebenenlauf ergänzt fehlende Ungleichungen Runde für Runde. Der Haken: Ganzzahlig heißt nicht Matroid, auch viele andere Systeme mit höchstens 5 Elementen haben ganzzahlige Ecken.
Demo starten →Submodularität: Wann Greedy fast optimal ist
Sehen Sie, wie Greedy, also immer die Leitung mit dem größten Zuwachs, auch ohne Matroid eine Garantie behält, wenn der Zusatznutzen abnimmt: Die zweite Leitung deckt weniger neue Haushalte ab. Die Garantie sinkt mit wachsender Leitungszahl auf etwa 63 %. Der Haken: Sie gilt für den schlechtesten Fall; auf 100 Zufallsplänen mit 8 Standorten liegt Greedy im Median beim Optimum, und ohne abnehmenden Zusatznutzen ist sie nicht abgesichert.
Demo starten →Über Greedy hinaus: Schneller, sparsamer, besser
Sehen Sie, was man tut, wenn Greedy zu teuer, zu ungenau oder nicht anwendbar ist: fünf Auswege, darunter Lazy Greedy, das mit gleicher Wahl weniger Berechnungen braucht. Im Standardfall (200 Trassen, k = 10, Seed 8) sind es 263 statt 1 955. Der Haken: Die lokale Suche, die Leitungen tauscht, macht mehr Pläne optimal, hebt aber in dieser Messreihe den schlechtesten Fall unter der Farbregel nicht an.
Demo starten →Matroid-Sekretärproblem: Angebote nacheinander
Verfolgen Sie, wie Leitungsangebote nacheinander eintreffen und jedes sofort angenommen oder endgültig verworfen werden muss, während der Vorgänger Greedy alle Angebote vorab kannte. Im Standardfall mit zufälliger Reihenfolge erreicht „erst kommt, erst bekommt“ 0,215 des Optimums, eine wachsende Stichprobe schon gesehener Angebote 0,561. Der Haken: Kommen die wertvollsten Angebote zuerst, nehmen beide Stichprobenregeln typischerweise nichts an.
Demo starten →Matroid-Bandits: Die beste Basis lernen
Sehen Sie, wie sich beim Verlegen lernen lässt, welche Leitungen sich lohnen, wenn Erfolgschancen unbekannt sind und jede Runde nur Zufallserfolge zeigt. Das Bedauern, der entgangene Nutzen gegenüber der besten Wahl, beträgt im Standardplan nach 2 000 Runden im Mittel über 20 Läufe 217,1 beim optimistischen Verfahren, bei Zufallswahl 1 380,0. Der Haken: Bei kleinem Erfolgsabstand ist der günstige Verlauf selbst nach 8 000 Runden nicht erreicht.
Demo starten →Submodulare Minimierung: Exakt ohne Konvexität
Verfolgen Sie, wie sich unter allen Teilmengen von Leitungen die günstigste exakt finden lässt, wenn sich Kosten beim Bündeln teilen: Dann ist eine stetige Fortsetzung der Funktion konvex, also glatt lösbar. Im Standardfall (Seed 8) bleibt die lokale Suche ab der leeren Menge bei −110, die übrigen Verfahren finden das Minimum −127. Der Haken: Ist die Voraussetzung verletzt, warnt keines der Verfahren.
Demo starten →Tutte-Polynom: Ein Polynom zählt alles
Sehen Sie, wie ein einziges Polynom ersetzt, was die Vorgänger einzeln zählten: Seine Werte an vier Stellen liefern die Zahl der Basen (maximale zulässige Leitungsmengen), der unabhängigen und der aufspannenden Mengen. Beim voreingestellten Plan mit 14 Leitungen und Seed 3 sind es 845 Basen. Der Haken: Eine bekannte Zählformel für Netze ohne Ringe überträgt sich nicht auf jedes Matroid; für das kleine Fano-Beispiel liefert sie ein falsches Ergebnis.
Demo starten →Verfahrenswahl: Welches Verfahren wann
Verfolgen Sie, wie sich testen lässt, ob die Aufgabe ein Matroid ist, obwohl man nur fragen kann, ob eine Leitungsmenge zulässig ist. Greedy ohne Vorprüfung verliert im Mittel über 600 Instanzen 2,02 Prozent des Optimums; erst testen, dann wählen, bei einem Prüfbudget von 300 Aufrufen nur 0,53 Prozent. Der Haken: Ein begrenzter Test lässt manche Nicht-Matroide durch, die vollständige Prüfung verdoppelt sich mit jeder weiteren Leitung.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über alle siebzehn Stücke: Er fragt danach, was man klären will, nicht nach dem Verfahren.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Der Baum ordnet nach der Frage, nicht nach Güte. Wo mehrere Stücke passen, hilft die Verfahrenswahl; ihre Aussagen gelten nur für die dort gemessenen Aufgaben und Größen.
Weitere Linien in diesem Bereich
Abzählen und erzeugende Funktionen
Wie viele Möglichkeiten gibt es, wie schnell wachsen sie, und wann lohnt sich welches Zählverfahren? Sechzehn Stücke von der Rekursion über erzeugende Funktionen und Symmetrie bis zum Entscheidungsdiagramm und zur Verfahrenswahl.