Greedy und Tausch verständlich erklärt

Ein Versorger will mehrere Standorte mit Leitungen verbinden, so billig wie möglich. Eine einfache Regel liefert dafür das beste Netz. Kommt eine einzige Zusatzregel dazu, kann dieselbe Regel danebenliegen. Diese Seite zeigt, woran man beides erkennt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Leitungsnetz, so billig wie möglich

Nehmen wir ein ausgedachtes Beispiel. Ein Versorger will fünf Standorte, A bis E, durch Leitungen verbinden. A ist das Depot, von dem die Versorgung ausgeht. Gebaut werden darf nur zwischen manchen Paaren. A–B, A–C und A–D kosten je 1, B–C kostet 3, D–E kostet 5. Gesucht ist die Auswahl, die alle fünf verbindet und am wenigsten kostet.

Ein billigstes Netz enthält nie einen Rundweg, also Leitungen, die im Kreis zum Ausgangsstandort zurückführen, etwa A–B, B–C und A–C. Man könnte eine davon streichen. Alle Standorte blieben verbunden, denn der Weg läuft um den Rundweg herum. Es würde billiger, denn jede Leitung kostet etwas. Ein Netz ohne Rundweg, das alle verbindet, heißt unter Fachleuten Spannbaum.

Die Regel dafür ist einfach. Man sieht die möglichen Leitungen vom billigsten zum teuersten an und nimmt jede, die keinen Rundweg schließt. Im Beispiel kommen A–B, A–C und A–D ins Netz. B–C fällt weg, denn B und C hängen über A schon zusammen. Dann kommt D–E. Eine Regel, die immer das Nächstbeste nimmt und nie zurückgeht, heißt gierig (englisch greedy).

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Der erste Knopf unten öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht. Sie ist ein vereinfachtes Rechenbild (Fachwort: Modell). Es erzeugt zufällige Pläne, also Karten mit sechs bis neun Standorten, deren Leitungskosten der Entfernung folgen. Sie probiert alle möglichen Netze durch und kennt deshalb das billigste.

Drei Zeichen, an denen man die Regel erkennt

Dass die Regel das billigste Netz findet, ist ein bekannter Satz der Fachwelt. Die Demo fragt anders: Woran sieht man es? Sie misst drei Zeichen.

Erstes Zeichen: Nur die Reihenfolge zählt. Die Regel fragt nur, welche Leitung billiger ist, nie um wie viel. Rechnet man die Kosten um, sodass teurer teurer bleibt, kommt dasselbe Netz heraus. Ein Beispiel ist, jede Kostenzahl mit sich selbst malzunehmen. Die Demo prüfte das auf 40 Plänen mit sieben Standorten und fünf solchen Umrechnungen, zusammen 200 Vergleiche. Das Netz änderte sich in keinem.

Zum Vergleich dient das Netz der kürzesten Wege vom Depot. Es änderte sich bei der Umrechnung „hoch drei“ (Kosten mal Kosten mal Kosten) auf 36 der 40 Pläne. Es addiert Strecken. Ob zwei Teilstrecken zusammen kürzer sind als eine lange, hängt von den Kosten selbst ab.

Zweites Zeichen: Jeder Zwischenstand ist der beste. Angenommen, das Geld geht nach einigen Leitungen aus. Dann hat die Regel mit genau so vielen Leitungen schon das Billigste gebaut, was ohne Rundweg möglich ist. Das gilt für jede Anzahl, nicht erst am Ende. Auf dem Plan, den die Demo beim Öffnen zeigt (sieben Standorte), prüfte sie das für alle sechs Anzahlen. Dass es für jeden Plan gilt, ist der bekannte Satz.

Drittes Zeichen: Tauschen schadet nie. Ein Tausch heißt: eine Leitung hinein, eine heraus. Nehmen wir ein Netz, das alle verbindet, aber nicht das billigste: A–B, B–C, A–D und D–E. Legt man A–C dazu, entsteht ein Rundweg aus A–B, B–C und A–C. Nimmt man daraus B–C heraus, die teuerste dieser drei, bleiben alle verbunden. Das Netz ist billiger geworden. So klappt es immer, wenn die entfernte Leitung teurer ist als die neue. Das ist das Tauschargument.

Tauscht man so lange, bis kein Tausch mehr Geld spart, endet man bei einem billigsten Netz. Auf dem Plan der Demo klappte das von einem zufälligen Startnetz aus in drei Tauschen. Ein falscher Endpunkt hieße lokales Optimum: Kein einzelner Tausch hilft weiter, und doch gibt es ein billigeres Netz. Ohne Zusatzregel blieb keine gemessene Tauschreihe an einem solchen Punkt hängen.

Eine Zusatzregel, und alles kippt

Nun kommt eine einzige Bedingung dazu. An jedem Standort dürfen nur wenige Leitungen enden, so wie ein Verteiler nur wenige Steckplätze hat. Die Zahl der Leitungen an einem Standort heißt sein Grad, die Obergrenze Gradschranke. Die Demo erlaubt höchstens drei oder höchstens zwei. Das Beispiel nimmt zwei, die Messungen weiter unten drei. Die Regel bleibt dieselbe. Sie lässt jetzt zusätzlich eine Leitung aus, die einen Standort über die Grenze brächte.

Im Beispiel nimmt die Regel erst A–B und A–C. Damit sind die zwei Steckplätze von A belegt, und A–D wird ausgelassen. B–C schließt einen Rundweg und fällt weg. D–E schließt keinen Rundweg und bringt keinen Standort über die Grenze, also kommt sie ins Netz. Nun hängen D und E nur aneinander, nicht am Rest. Nur A–D führt zu ihnen, doch die Regel blickt nie zurück. Ihr Ergebnis verbindet nicht alle Standorte. Es gibt Netze, die es tun, etwa A–D, D–E, A–B und B–C.

Die Demo stellt das nach. Ein Schalter macht die Leitungen am Depot billig, denn sonst gerät die Regel selten an die Grenze. Ohne billige Depotleitungen hätte ihr Netz die Grenze von drei auf keinem der 40 Pläne mit sieben Standorten überschritten. Vermutlich enden die billigsten Leitungen dann an verschiedenen Standorten. Auf einem Plan mit billigen Depotleitungen und der Grenze drei kostete das Netz der Regel 126, das billigste 115. Die Regel lag also knapp ein Zehntel darüber.

Auch das Tauschen verliert seine Sicherheit. Ein Tausch, der billiger macht, kann einen Standort über die Grenze bringen und ist dann verboten. Auf demselben Plan blieb das Tauschen von einem Startnetz aus über dem Billigsten stehen, wenn zufällig getauscht wurde. Wählte man stets den Tausch mit der größten Ersparnis, kam es von demselben Startnetz zum billigsten. Das gilt für diesen einen Start.

Häufige Missverständnisse

• „Es gibt immer genau ein billigstes Netz.“ Nein. Bei gleichen Kosten können mehrere gleich billig sein. Auf dem größten Plan der Demo (neun Standorte) waren es zwei unter 1160 Netzen, und die Regel findet eines davon.
• „Scheitert die Regel mit Zusatzregel, scheitert jedes Verfahren.“ Nein. Es gibt andere Verfahren, etwa systematisches Durchprobieren mit frühem Aussortieren aussichtsloser Fälle. Die Demo führt nur diese eine Regel vor.

Woran Sie das im Alltag erkennen

• Ein knapper Platz, etwa ein Steckplatz oder ein Sitzplatz, wird früh vergeben. Später fehlt er dort, wo er gebraucht wird.
• Eine Zusatzregel stört nur, wenn sie wirklich eng ist. „Höchstens vier Personen je Tisch“ ändert bei einer Feier mit lauter Paaren nichts.

Wie ernst ist das Rechenbild zu nehmen?

Die Pläne sind klein, zufällig erzeugt und haben höchstens neun Standorte. Alle Messungen gelten für sie, nicht für echte Netze. Dass die Regel ohne Zusatzregel gewinnt, ist ein bekannter Satz. Die Messung bestätigt ihn nur an diesen Plänen und beweist ihn nicht.

Was Sie mitnehmen:

• Fragen Sie bei einer Faustregel, ob sie anders entschiede, wenn dieselben Werte nur anders skaliert, aber gleich geordnet wären.
• Fragen Sie bei einer Zusatzregel, an welcher Stelle sie wirklich eng wird.
• „Kein Tausch hilft mehr“ heißt nur dort „das Beste“, wo es keine falschen Endpunkte gibt.

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.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst Modell und Methodik der Demo zusammen und leitet die drei Beobachtungen her, die sie misst.

• Aufgabe: Gegeben ist ein zusammenhängender Graph \(G = (V, E)\) mit Standorten \(V\), \(n = |V|\), möglichen Leitungen \(E\) und ganzzahligen Kosten \(c_e\). Gesucht ist ein Spannbaum \(T \subseteq E\) (zusammenhängend, kreisfrei, \(|T| = n - 1\)) mit kleinsten Gesamtkosten. Auf Wunsch gilt eine Gradschranke \(d\): An keinem Standort enden mehr als \(d\) Leitungen von \(T\).
• Pläne: \(n\) liegt zwischen 6 und 9 (voreingestellt 7). Standort A ist das Depot in der Mitte, die übrigen liegen zufällig. Mögliche Leitungen sind ein kürzestes Gerüst, damit der Plan zusammenhängt, plus die kürzesten übrigen Paare, insgesamt \(m = \min\{n(n-1)/2,\, 2n-2\}\): 12 bei \(n = 7\), 16 bei \(n = 9\). Die Kosten sind die Länge mal 100, auf ganze Zahlen gerundet.
• Schalter: Die „billige Nabe“ (voreingestellt aus) senkt die Kosten der Leitungen am Depot auf 40 % davon. Die Gradschranke \(d\) ist aus (voreingestellt), 3 oder 2. Der Wert 1 fehlt, weil es dann bei mehr als zwei Standorten keinen Spannbaum gibt.
• Greedy: Die Leitungen werden nach (Kosten, Nummer) sortiert; die Nummer ist die Position in der nach Standortpaaren geordneten Liste (A–B, A–C, …), bei gleichen Kosten gewinnt also die kleinere Nummer. Der Reihe nach wird jede genommen, die keinen Kreis schließt und, mit Schranke, keinen Standort über \(d\) bringt.
• Prüfung: Bei höchstens 16 Leitungen zählt die Demo alle Spannbäume und alle Wälder auf. Daraus folgen das Optimum, die Zahl der optimalen Bäume und der billigste Wald je Größe. Kreisfreiheit und Zusammenhang prüft eine Tiefensuche, unabhängig von der Datenstruktur, die Greedy für die Kreisprüfung benutzt (Union-Find).
• Tausch-Lauf: Von einem gleichverteilt gezogenen zulässigen Startbaum aus wird ein verbessernder Tausch ausgeführt, bis keiner mehr erlaubt ist. Die Regel „zufällig“ wählt gleichverteilt unter allen verbessernden Tauschen, „bester“ den mit der größten Ersparnis.
• Umrechnungen: Fünf streng wachsende Funktionen der Kosten \(c\): \(c^3\), \(\ln c + 10\), \(c + 1000\), die Exponentialfunktion von \(c\) geteilt durch fünfzig, \(\sqrt{c}\) (in der Demo „hoch 3“, „Logarithmus“, „plus 1000“, „Exponentialfunktion“, „Wurzel“). Die Zahlen zum Baum der billigsten Wege gelten nur für diese Formen. Zum Vergleich dient der Baum der billigsten Wege vom Depot (Dijkstra).

Die Formeln

Minimiert werden die Gesamtkosten des Spannbaums:

\[\sum_{e \in T} c_e\]

Mit Schranke muss zusätzlich für jeden Standort \(v\) gelten, dass die Zahl \(\deg_T(v)\) der Leitungen von \(T\) an \(v\) höchstens \(d\) ist:

\[\deg_T(v) \le d\]

Legt man zu einem Spannbaum \(T\) eine Leitung \(e \notin T\) hinzu, enthält \(T \cup \{e\}\) genau einen Kreis \(C(T, e)\). Für jede Leitung \(f\) dieses Kreises ist der getauschte Baum wieder ein Spannbaum:

\[T - f + e\]

Er ist billiger als \(T\), genau wenn \(c_f > c_e\) gilt. Ein verbessernder Tausch ist ein solcher mit \(f \in C(T, e)\) und \(c_f > c_e\); mit Schranke ist er nur erlaubt, wenn \(T - f + e\) die Schranke einhält.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo. Es sind Standardargumente; die Sätze selbst sind bekannt.

Ein Tausch auf dem Kreis erhält den Spannbaum.

• Schritt 1: Sei \(e = \{u, w\} \notin T\). Ein Baum ist zusammenhängend und kreisfrei, also gibt es in \(T\) genau einen Weg \(P\) von \(u\) nach \(w\). Daher ist \(C(T, e) = P \cup \{e\}\) der einzige Kreis in \(T \cup \{e\}\).
• Schritt 2: Sei \(f \in P\). Jeder Weg in \(T\), der \(f\) benutzt, kann stattdessen über \(e\) und \(P - f\) laufen. Also ist \(T - f + e\) zusammenhängend und hat \(n - 1\) Leitungen, ist also ein Spannbaum.
• Schritt 3: Die Kosten ändern sich um \(c_e - c_f\). Mit Schranke erhöht \(e\) die Grade seiner beiden Endpunkte, und \(f\) senkt die Grade der seinen; ob die Schranke hält, muss man prüfen.

Erstes Zeichen: Greedy kennt nur die Reihenfolge.

• Schritt 1: Greedy benutzt die Kosten nur in der Sortierung nach (Kosten, Nummer), also nur in Vergleichen zweier Kosten auf kleiner, gleich oder größer.
• Schritt 2: Eine streng wachsende Umrechnung \(\varphi\) erhält jeden dieser Vergleiche, auch die Gleichheiten. Die Sortierung ist dieselbe, also treffen die Entscheidungen dieselben Leitungen. Die Kosten des Baums ändern sich, der Baum nicht.
• Schritt 3: Der Baum der billigsten Wege hängt von Summen ab. Ein Beispiel dieser Seite, nicht aus der Demo: Eine direkte Leitung kostet 3, ein Umweg aus zwei Leitungen zu je 2 kostet zusammen 4, direkt ist billiger. Quadriert man alle Kosten (streng wachsend für positive Kosten), stehen 9 gegen 4 + 4 = 8, und der Umweg ist billiger. Die Umrechnung kippt diese Entscheidung.

Zweites Zeichen: Greedy ist für jede Größe optimal (ohne Schranke). Seien \(g_1, \dots, g_k\) die ersten \(k\) von Greedy genommenen Leitungen und \(F\) ein beliebiger Wald (kreisfreie Leitungsmenge) mit \(k\) Leitungen. Zu zeigen ist, dass die \(g\)-Leitungen zusammen höchstens so viel kosten wie \(F\).

• Schritt 1: Ordne \(F\) nach (Kosten, Nummer) als \(f_1 < \dots < f_k\). Es genügt, \(c_{g_i} \le c_{f_i}\) für jedes \(i\) zu zeigen; die Summe über \(i\) liefert dann die Behauptung.
• Schritt 2: Fixiere \(i\). Die Menge \(\{f_1, \dots, f_i\}\) ist ein Wald mit \(i\) Leitungen, \(\{g_1, \dots, g_{i-1}\}\) einer mit \(i - 1\). Nach der bekannten Austauscheigenschaft der Wälder (ist ein Wald kleiner als ein anderer, lässt sich ihm eine Leitung des größeren hinzufügen, ohne einen Kreis zu schließen) gibt es ein \(f_j\) mit \(j \le i\), \(f_j \notin \{g_1, \dots, g_{i-1}\}\), sodass \(\{g_1, \dots, g_{i-1}, f_j\}\) kreisfrei ist.
• Schritt 3: Läge \(f_j\) in der Sortierung vor \(g_i\), hätte Greedy sie beim Ansehen genommen: Sie schließt auch mit der damaligen, kleineren Auswahl keinen Kreis. Das widerspricht \(f_j \notin \{g_1, \dots, g_{i-1}\}\). Also liegt \(f_j\) nach \(g_i\), und es gilt \(c_{g_i} \le c_{f_j} \le c_{f_i}\).
• Schritt 4: Mit Schranke scheitert Schritt 2: Die Austauscheigenschaft gilt für Wälder mit Gradschranke nicht. Das zeigt das durchgerechnete Beispiel unten.

Drittes Zeichen: Ohne verbessernden Tausch ist ein Spannbaum optimal (ohne Schranke). Sei \(T\) ein Spannbaum, für den für jedes \(e \notin T\) und jedes \(f \in C(T, e)\) gilt: \(c_f \le c_e\).

• Schritt 1: Unter allen billigsten Spannbäumen sei \(T^*\) einer mit möglichst vielen Leitungen gemeinsam mit \(T\). Angenommen, \(T^* \ne T\); wähle \(g \in T^* \setminus T\).
• Schritt 2: Entfernt man \(g\) aus \(T^*\), zerfällt \(T^*\) in zwei Teile. Der Kreis \(C(T, g)\) enthält \(g\) und führt von dem einen Teil in den anderen, muss also eine weitere Leitung \(f\) enthalten, die beide Teile verbindet. Es gilt \(f \in T\), und \(f \notin T^*\), weil \(T^* - g\) keine Leitung zwischen den Teilen hat.
• Schritt 3: \(T^* - g + f\) ist ein Spannbaum. Wegen der Annahme gilt \(c_f \le c_g\), er kostet also höchstens so viel wie \(T^*\) und ist damit auch billigst. Er hat eine Leitung mehr mit \(T\) gemeinsam als \(T^*\): Das widerspricht der Wahl von \(T^*\). Also ist \(T = T^*\) optimal.
• Schritt 4: Mit Schranke kann \(T^* - g + f\) die Schranke verletzen. Der Schluss bricht, und falsche lokale Optima werden möglich.

Durchgerechnet: ein kleines Netz mit Schranke

Rechnung dieser Seite, keine Messung der Demo: fünf Standorte A bis E, Leitungen A–B, A–C, A–D je Kosten 1, B–C Kosten 3, D–E Kosten 5, Schranke \(d = 2\). Greedy sortiert in dieser Reihenfolge (bei gleichen Kosten nach Nummer):

Schritt	Leitung	Kosten	Entscheidung
1	A–B	1	genommen
2	A–C	1	genommen (A hat nun zwei Leitungen)
3	A–D	1	ausgelassen: A hätte drei Leitungen
4	B–C	3	ausgelassen: schließt den Kreis A–B–C
5	D–E	5	genommen

Greedy liefert nur einen Wald mit 3 von 4 nötigen Leitungen, keinen Spannbaum. Nur A–D führt zu D und E, also muss jeder Spannbaum sie enthalten und damit auch D–E. A hat dann nur noch einen Platz für B oder C. Es gibt genau zwei Spannbäume mit \(d = 2\): \(\{A\text{–}D, D\text{–}E, A\text{–}B, B\text{–}C\}\) und \(\{A\text{–}D, D\text{–}E, A\text{–}C, B\text{–}C\}\), beide mit Kosten zehn.

Warum die Austauscheigenschaft hier fehlt: Greedys Auswahl \(G = \{A\text{–}B, A\text{–}C, D\text{–}E\}\) ist ein Wald mit \(d = 2\) und 3 Leitungen. Der erste Spannbaum hat 4 Leitungen, und seine Leitungen außerhalb von \(G\) sind B–C und A–D. B–C schließt mit \(G\) den Kreis A–B–C. A–D brächte A auf drei Leitungen. Keine Leitung lässt sich also ergänzen, Schritt 2 der Herleitung zum zweiten Zeichen scheitert. Ohne Schranke nimmt Greedy hier A–B, A–C, A–D und D–E zu Kosten acht.

Befunde

Die Zahlen stammen aus den Messungen der Demo mit festen Plänen. Die Anteile sind Zählungen über 40 feste, immer dieselben Zufallspläne mit sieben Standorten (Tauschpartner: 12 Pläne), nicht Raten für alle Pläne. Die drei Tausch-Läufe je Plan sind nicht unabhängig. Die Schranke „bindet“, wenn der Greedy-Baum ohne Schranke sie verletzt. Pläne ohne Spannbaum unter der Schranke zählen nicht mit.

Frage	Befund
Ist Greedy ohne Schranke optimal? (Voreingestellter Plan: 7 Standorte, 12 mögliche Leitungen, ohne Nabe)	Ja. Es gibt 180 Spannbäume; Greedy und das Optimum kosten beide 156; genau ein Baum ist optimal.
Ändert sich der Greedy-Baum bei streng wachsender Umrechnung der Kosten? (40 Pläne, ohne Nabe, 5 Umrechnungen)	In 0 von 200 Vergleichen. Der Baum der billigsten Wege vom Depot änderte sich bei „hoch 3“ in 36 von 40 Plänen, beim Logarithmus in 4, bei „plus 1000“ in 2, bei der Exponentialfunktion in 6 und bei der Wurzel in 4.
Ist Greedy für jede Größe \(k\) optimal? (Voreingestellter Plan)	Ja, für alle 6 Größen.
Endet verbesserndes Tauschen im Optimum? (Voreingestellter Plan, erster Startbaum, zufälliger verbessernder Tausch)	Ja, nach 3 Tauschen, die Kosten sinken von 220 auf 156.
Ist Greedy mit Nabe und höchstens 3 Leitungen je Standort optimal? (Gleicher Plan mit billiger Nabe)	Nein. Greedy kostet 126, das Optimum 115; Greedy liegt 9,6 % über dem Optimum. Es gibt 152 zulässige Spannbäume. Bei den Größen \(k = 5\) und \(k = 6\) ist Greedy nicht optimal (für \(k = 5\): 86 statt 76).
Endet das Tauschen dort im Optimum? (Derselbe erste Startbaum)	Mit zufälligem Tausch nein: nach 5 Tauschen stehen die Kosten bei 132 (Optimum 115). Mit dem besten Tausch ja, nach 3 Tauschen. Das gilt für diesen einen Start.
Höchstens 2 Leitungen je Standort, ohne Nabe? (Voreingestellter Plan)	Greedy nimmt nur 5 der nötigen 6 Leitungen und findet keinen Spannbaum, obwohl es 24 gibt; der billigste kostet 162.
Was kippt auf 40 Plänen ohne Nabe? (3 Tausch-Läufe je Plan)	Schranke 3: bindet in 0 von 40 Plänen, Greedy ist in allen 40 optimal, das Tauschen bleibt in 1 von 120 Läufen vor dem Optimum hängen. Schranke 2 (37 Pläne haben einen Spannbaum): bindet in 30, Greedy findet in 21 keinen Spannbaum und ist in 1 nicht optimal, das Tauschen hängt in 56 von 111 Läufen.
Was kippt auf 40 Plänen mit Nabe? (3 Tausch-Läufe je Plan)	Schranke 3: bindet in 37 von 40, Greedy ist in 20 nicht optimal und findet in 5 keinen Spannbaum, das Tauschen hängt in 44 von 120 Läufen. Schranke 2: bindet in 37 von 37, Greedy ist in 6 nicht optimal und findet in 22 keinen Spannbaum, das Tauschen hängt in 60 von 111 Läufen. Ohne Schranke gibt es jeweils 0 Abweichungen.
Hat jeder Tausch einen Partner? Gezählt über Tripel \((T_1, T_2, e)\) mit \(e \in T_1 \setminus T_2\): Gibt es \(f \in T_2 \setminus T_1\), sodass \(T_1 - e + f\) (einseitig) und zusätzlich \(T_2 - f + e\) (symmetrisch) zulässig sind? (12 Pläne mit 7 Standorten, ohne Nabe, je 20 Baumpaare)	Spannbäume: bei 694 Tripeln 0 ohne Partner, auch symmetrisch 0. Spannbäume mit höchstens 3 Leitungen je Standort: 44 von 654 (6,7 %) ohne Partner, 152 (23,2 %) ohne symmetrischen. Pfade (höchstens 2 Leitungen je Standort): 356 von 616 (57,8 %) ohne Partner, 546 (88,6 %) ohne symmetrischen.
Größter Plan (9 Standorte, mit Nabe, ohne Schranke)	1160 Spannbäume, Optimum 127 mit 2 optimalen Bäumen; Greedy findet einen davon.

Grenzen: was die Messung zeigt und was nicht

Was sie belegt: Optimum und Zahl der optimalen Bäume sind durch vollständiges Aufzählen bestimmt, nicht geschätzt. Die Zählungen an den festen Plänen sind exakt für diese Pläne. Die Tauschpartner-Zählungen zeigen, dass der Tausch zwischen zwei zulässigen Bäumen bei Gradschranke oft keinen Partner findet. Das ist eine Schwesterform der Austauscheigenschaft aus der Herleitung; dort zeigt nur das durchgerechnete Beispiel das Fehlen.

Was sie nicht belegt:

• Kein Beweis. Pläne haben höchstens 9 Standorte und 16 Leitungen, damit sich alle Bäume aufzählen lassen. Die drei Zeichen gelten auf allen gemessenen Plänen ohne Schranke; die Sätze dahinter sind bekannt, die Messung ersetzt sie nicht.
• Kein Maß für echte Pläne. Die Nabe ist eine bewusste Konstruktion, damit die Schranke 3 überhaupt bindet. Ohne Nabe bindet sie bei 7 Standorten auf den 40 festen Plänen nie, bei 9 Standorten in 2 von 40. Die Anteile mit Nabe schätzen nicht, wie oft eine Schranke in echten Plänen stört.
• Hängenbleiben ohne bindende Schranke. Das Tauschen blieb in 1 von 120 Läufen hängen, obwohl die Schranke in keinem Plan band. „Bindet“ meint nur, dass der Greedy-Baum die Grenze verletzt hätte. Eine Erklärung dieser Seite, nicht gemessen: Die Lokalsuche läuft über andere Bäume, und von einem solchen aus kann jeder verbessernde Tausch einen Standort über die Grenze bringen; der Weg zum Optimum führte dann über einen unzulässigen Baum.
• Härte. Für \(d = 2\) ist ein Spannbaum mit Grad höchstens 2 ein Weg durch alle Standorte (Hamiltonpfad); die Aufgabe mit Gradschranke gilt deshalb als NP-schwer (bekannt, hier nicht gemessen). Dass Greedy scheitert, liegt also nicht allein an Greedy.
• Nur eine Art Nebenbedingung. Gemessen ist nur die Gradschranke mit den Werten 3 und 2, und nur die Regel „Greedy mit Gradschranke“, nicht jedes Verfahren für das gradbeschränkte Problem. Andere Nebenbedingungen (Farben, Kapazitäten) und eine Lokalsuche mit größerer Nachbarschaft als einem Tausch sind nicht gemessen.
• Nur ein Gegenbeispiel zum ersten Zeichen. Der Baum der billigsten Wege ist kein Vergleich mit allen Verfahren.
• Gleichstände. Bei gleichen Kosten gibt es oft mehrere beste Bäume; Greedy findet einen davon. „Genau ein optimaler Baum“ ist eine Eigenschaft des voreingestellten Plans.

Erweiterungen und Verweise

Was diese Demo auslässt, behandeln andere Seiten und Demos dieser Website:

• Ablauf von Kruskal: Die Seite Der Kruskal-Algorithmus verständlich erklärt und die Kruskal-Demo zeigen den Ablauf mit Union-Find, den Umweg-Faktor, die Stabilität und Gleichstände.
• Lösungsverfahren mit Gradschranke: Die constrained-mst-demo behandelt Verfahren für die Gradschranke (Lagrange-Untergrenze, Branch and Bound), die cmst-demo den Spannbaum mit Kapazität.
• Wie weit Greedy zurückfallen kann: Die Demo „Unabhängigkeitssysteme: Wo Greedy scheitert und wie schlimm“ rechnet aus einer Zulässigkeitsregel wie „höchstens drei Leitungen je Standort“ aus, wie weit Greedy hinter dem Optimum zurückfallen kann.
• Die Struktur dahinter: Die Demo „Das Matroid: Austauschaxiom und Beispiele“ prüft, ob eine Zulässigkeitsregel die Austauscheigenschaft hat, auf der Greedy verlässlich arbeitet. Die Demo „Greedy genau dann optimal“ zeigt, dass Greedy für jede Gewichtung genau dann optimal ist, wenn das System ein Matroid ist.

Quellen

• Kruskal, J. B. (1956): On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7(1), 48–50.
• Edmonds, J. (1971): Matroids and the greedy algorithm. Mathematical Programming 1, 127–136.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/greedy-austausch-demo.

Die beiden Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus der Beschreibung der Demo. Das Beispiel mit den fünf Standorten im ersten Teil ist erdacht und stammt nicht aus der Demo; die Herleitungen und das durchgerechnete Beispiel sind Rechnungen dieser Seite und keine Messungen.