Der Steiner-Baum verständlich erklärt

Vier Häuser sollen an dieselbe Leitung. Wer nur Haus mit Haus verbindet, kann mehr Leitung bauen als nötig. Eine Kreuzung ohne Haus, an der sich die Leitung teilt, kann Strecke sparen. Diese Seite zeigt, wie viel und warum die richtige Kreuzung schwer zu finden ist.

Zuletzt aktualisiert: 11. November 2026

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

Vier Häuser, neun Kreuzungen

Stellen Sie sich ein kleines Dorf vor. Seine Straßen bilden ein Gitter aus drei mal drei Kreuzungen. Zwischen zwei benachbarten Kreuzungen liegt ein Straßenabschnitt. Alle Abschnitte sind gleich lang.

Vier Häuser stehen an den Kreuzungen links, rechts, oben und unten von der mittleren Kreuzung. Auf der mittleren Kreuzung steht kein Haus. Alle vier Häuser sollen an dieselbe Wasserleitung, die an einem der Häuser eingespeist wird. Dieses Haus heißt Depot. Jeder Abschnitt, in dem Leitung liegt, kostet gleich viel. Gesucht ist das Netz mit den wenigsten Abschnitten.

Erster Versuch: Man verbindet nur Haus mit Haus. Von einem Haus zum nächsten sind es zwei Abschnitte. Drei solche Verbindungen schließen alle vier Häuser an. Das macht sechs Abschnitte.

Zweiter Versuch: Die Leitung darf sich an der mittleren Kreuzung teilen. Von jedem Haus führt ein Abschnitt dorthin. Das macht vier Abschnitte, also zwei weniger. Die vier Häuser teilen sich die Mitte, statt jede Verbindung einzeln zu bezahlen.

Fachleute nennen eine Kreuzung ohne Haus, die das Netz benutzt, einen Steinerpunkt. Die Mitte ist hier einer, und an ihr verzweigt sich die Leitung. Das kürzeste Netz ohne Schleife, das alle Häuser verbindet und Steinerpunkte nutzen darf, heißt Steiner-Baum, weil es sich verzweigt wie ein Baum.

Wann Verzweigen spart

Eine Verzweigung spart, wenn mehrere Häuser ein Stück Weg gemeinsam nutzen können. Im Dorf ist das so, weil die vier Häuser rund um die Mitte liegen. Stehen Häuser dagegen Tür an Tür, ist jedes schon einen Abschnitt vom nächsten entfernt.

Die richtige Kreuzung zu finden ist schwer

Im Dorf sieht man die Mitte sofort. In einer Stadt mit vielen Kreuzungen nicht. Bei jeder Kreuzung ohne Haus lautet die Frage: Soll sich die Leitung hier teilen, ja oder nein? Alle Kombinationen durchzuprobieren dauert bei vielen Kreuzungen zu lange. Ein Verfahren, das bei vielen Häusern schnell immer die beste Lösung findet, kennt man bis heute nicht.

Deshalb arbeitet man mit Faustregeln (Fachwort: Heuristiken). Sie finden schnell ein gutes Netz, aber nicht immer das kürzeste. Vier Faustregeln:

• Wege zusammenlegen. Man wählt zuerst die kürzesten Verbindungen von Haus zu Haus, die alle Häuser verknüpfen, jede auf dem kürzesten Weg. Laufen zwei Verbindungen über dasselbe Straßenstück, wird es nur einmal gebaut. Überflüssiges lässt man weg.
• Vom Depot aus wachsen. Das Netz beginnt am Depot. Dann hängt man immer das Haus an, das dem bisherigen Netz am nächsten liegt, über den kürzesten Weg.
• Von jedem Haus aus wachsen. Wie die vorige Regel, aber man probiert jedes Haus als Start und behält das kürzeste Netz.
• Verbessern. Man startet mit dem kürzesten Netz, das die anderen Faustregeln gefunden haben. Dann prüft man Kreuzung für Kreuzung, ob das Netz kürzer wird, wenn die Kreuzung dazukommt oder wegfällt. Wird es kürzer, ändert man es.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser. Der erste Knopf unten öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie das Programm nicht.

Das Programm erzeugt am Rechner Stadtpläne: ein leicht verzerrtes Gitter aus Kreuzungen, ein Teil der Straßen gesperrt, einige Kreuzungen als Häuser. Das Programm legt die vier Faustregeln nebeneinander. Zum Vergleich rechnet es die beste Lösung aus, aber nur bis dreizehn Häuser: Dieser Rechenweg probiert alle Teilgruppen von Häusern durch und braucht mit jedem weiteren Haus länger. Das ist ein vereinfachtes Rechenbild (Fachwort: Modell), in dem nur die Länge der Leitung zählt. Die Aussagen im Folgenden beschreiben diese erzeugten Pläne, nicht echte Netze.

Was die Messung zeigt

Die Zahlen gelten für Pläne mit acht mal acht Kreuzungen und sieben Häusern, gemessen an 50 Plänen.

Spart das Verzweigen etwas? Verglichen wird mit der Summe der Wege, wenn jedes Haus einzeln an das nächste angeschlossen wird; überlappende Stücke zählen dabei mehrfach. Ein Teil der Ersparnis kommt also schon vom Zusammenlegen. In 92 % der Pläne war die beste Lösung kürzer, im Mittel um knapp 9 %.

Stehen die Häuser dagegen in Gruppen beieinander, sieht es anders aus. Bei neun Häusern in Gruppen sparte das Verzweigen nur in 50 % der Pläne etwas, im Mittel etwa 2 %. Eine Vermutung dazu: Das Programm setzt die Häuser einer Gruppe auf benachbarte Kreuzungen, und zwischen ihnen gibt es wenig zu teilen.

Keine Faustregel traf immer die beste Lösung. Das Wachsen vom Depot aus traf sie bei sieben Häusern in 30 % der Pläne. Probierte man jedes Haus als Start, waren es 56 %. Das Verbessern traf sie in 62 %.

Im Dorf vom Anfang haben viele Wege die gleiche Länge, etwa vom linken zum unteren Haus über die Mitte oder über die Ecke. Bei Gleichstand entscheidet im Programm eine feste Regel, und sie führt für zwei der drei Wege außen herum. Deshalb finden das Zusammenlegen und das Wachsen vom Depot aus nur sechs Abschnitte. Das Wachsen von jedem Haus aus und das Verbessern finden vier.

Das Verbessern ändert immer nur eine Kreuzung auf einmal. Ein Bild dazu: Wer im Nebel nur bergab geht, bleibt in einer Mulde stehen, auch wenn dahinter ein tieferes Tal liegt. „Bergab“ heißt hier: Das Netz wird kürzer. Manchmal wird das Netz erst kürzer, wenn mehrere Kreuzungen zugleich wegfallen.

Häufige Missverständnisse

• „Jede Kreuzung ohne Haus, die das Netz benutzt, ist ein Verteiler.“ Nein. Verzweigt wird erst, wo sich mindestens drei Leitungen treffen. Sonst läuft die Leitung nur hindurch. In der Messung (sieben Häuser, fünf Pläne, mittlere Werte) benutzte das beste Netz neun Kreuzungen ohne Haus, weil die Leitungen zwischen den Häusern über Kreuzungen laufen. Nur an dreien davon verzweigte es.
• „Eine Faustregel mit Garantie ist fast so gut wie die beste Lösung.“ Die Garantie für das Zusammenlegen und das Wachsen sagt nur: Das Netz wird nie mehr als doppelt so lang wie das beste. Sie muss auch für den ungünstigsten denkbaren Plan stimmen und ist deshalb grob. In der Messung lag das schlechteste Ergebnis des Zusammenlegens gut 20 % darüber.

Woran Sie das im Alltag erkennen

• Mehrere Geräte hängen an einer Steckdosenleiste, statt dass jedes ein eigenes Kabel zur Wand hat. Die Leiste ist ein Verzweigungspunkt, der selbst kein Gerät ist.
• Im Garten läuft ein Hauptschlauch, von dem Seitenschläuche zu den Beeten abzweigen, statt Schlauchstücke von Beet zu Beet zu legen.

Was Sie mitnehmen

• Fragen Sie bei einem Netz zu mehreren Zielen nicht nur, wer mit wem verbunden wird, sondern auch, wo sich die Leitung teilen darf.
• Probieren Sie eine Faustregel von mehreren Startpunkten aus und behalten Sie das kürzeste Ergebnis.
• Wie viel das Teilen bringt, hängt vom Plan ab. Prüfen Sie es am eigenen Plan.

Wie ernst ist das Rechenbild zu nehmen?

Die Pläne sind erzeugt, und nur die Länge der Leitung zählt. Eine Verzweigung kostet im Rechenbild nichts, ein echter Verteilerkasten kostet Geld und kann den Gewinn schmälern. Die Zahlen gelten für diese Pläne, nicht für ein echtes Netz.

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 beschreibt die Aufgabe, die Verfahren der Demo und ihre Kennzahlen. Eigenschaften der Verfahren (Garantien, Aufwand) und Messungen an der Demo sind getrennt ausgewiesen.

• Problem: Gegeben sind ein zusammenhängender Graph \(G=(V,E)\) mit Kantenlängen \(c_e>0\) (der Stadtplan: Kreuzungen und Straßen) und eine Menge von Terminals \(T\subseteq V\) mit \(t=\lvert T\rvert\) (Depot und Kunden). Gesucht ist ein Baum \(S\subseteq E\) minimaler Gesamtlänge \(c(S)=\sum_{e\in S}c_e\), dessen Knotenmenge \(T\) enthält. Jeder Knoten des Baums außerhalb von \(T\) heißt Steinerknoten. Hat er im Baum mindestens Grad 3 (mindestens drei Baumkanten am Knoten), ist er eine Verzweigung, sonst nur Durchgang. Für \(\lvert T\rvert=\lvert V\rvert\) ist die Aufgabe der minimale Spannbaum, für \(\lvert T\rvert=2\) der kürzeste Weg, mit beliebiger Terminalzahl ist sie NP-schwer (für festes \(t\) löst sie Dreyfus–Wagner in Polynomialzeit).
• Instanz: Der Plan ist ein gestörtes Gitter aus Seite × Seite Kreuzungen (5 bis 14 je Seite, voreingestellt 8). Die Kreuzungen sind um bis zu 15 % des Gitterabstands verschoben, Straßen verbinden Nachbarn, ihre Länge ist der euklidische Abstand der Kreuzungen. Ein Anteil von 0 bis 40 % der Straßen ist gesperrt (voreingestellt 10 %): Es wird in zufälliger Reihenfolge gesperrt, und eine Sperrung, die den Plan zerlegen würde, wird übersprungen. Die Zahl der Terminals ist 3 bis 30 (voreingestellt 7). Sie sind gleichverteilt oder in 2 bis 3 Gruppen gewählt: Je Gruppe gibt es einen Mittelpunkt, und die Terminals besetzen die dem Mittelpunkt nächsten freien Kreuzungen. Das Depot ist das Terminal mit der kleinsten Kreuzungsnummer (zeilenweise nummeriert). Dazu kommt ein festes Lehrbuchbeispiel.
• Basislinie „nur Terminals“: der minimale Spannbaum über die Terminals, wobei der Abstand zweier Terminals ihr kürzester Weg im Plan ist (der Metrik-Abschluss). Er rechnet jede Verbindung mit ihrem vollen Weg, auch wo sich Wege überlappen würden.
• Kou–Markowsky–Berman (KMB): minimaler Spannbaum im Metrik-Abschluss, jede seiner Kanten durch einen kürzesten Weg im Plan ersetzt, auf der Vereinigung dieser Wege erneut ein minimaler Spannbaum, dann werden Blätter abgeschnitten, die keine Terminals sind.
• Takahashi–Matsuyama (TM): Der Baum startet an einem Terminal, hier dem Depot. In jedem Schritt wird das dem Baum nächste Terminal über den kürzesten Weg angehängt (bei Gleichstand: kleinster Abstand, dann kleinstes Terminal, dann kleinster Baumknoten). TM mit bester Wurzel (TMR) probiert jedes Terminal als Start und nimmt das kürzeste Ergebnis.
• Lokalsuche: Der Start ist die Steinerknotenmenge \(X\) des besten der drei Ergebnisse (KMB, TM, TMR). Die Kosten von \(X\) sind die Länge des beschnittenen minimalen Spannbaums des von \(T\cup X\) induzierten Teilgraphen. In jedem Schritt wird die beste Verbesserung durch Einfügen eines Nachbarknotens oder Entfernen eines Steinerknotens ausgeführt, solange die Länge streng fällt.
• Exakt: Dreyfus–Wagner, angeboten bis 13 Terminals.
• Kennzahlen: Mit \(c_{\text{best}}\) als Länge des besten Baums (bis 13 Terminals das Optimum, sonst der beste Fund der Heuristiken) und \(c_{\text{Basis}}\) als Länge der Basislinie ist die Ersparnis \(100\,(1-c_{\text{best}}/c_{\text{Basis}})\), das Steiner-Verhältnis \(c_{\text{Basis}}/c_{\text{best}}\) und der Aufschlag eines Verfahrens mit Länge \(c\) gleich \(100\,(c/c_{\text{best}}-1)\). „Optimal“ heißt Aufschlag 0. Ein Sweep ist eine Reihe von Läufen, in der ein Regler variiert wird und die übrigen Einstellungen fest bleiben; er bildet je Wert den Median über 5 feste Instanzen, die Verteilungen laufen über 50 feste Instanzen (Mittel, Anteil optimal, größter Wert).

Die Formeln

Der Kernsatz macht das Optimum überprüfbar: Jeder Steinerbaum ist ein Baum auf \(T\) und einer Menge \(X\subseteq V\setminus T\) von Steinerknoten, und der billigste Baum auf einer festen Knotenmenge ist der minimale Spannbaum des davon induzierten Teilgraphen \(G[T\cup X]\), der aus den Knoten \(T\cup X\) und allen Kanten von \(G\) zwischen ihnen besteht.

\[\mathrm{OPT} = \min_{X \subseteq V \setminus T} \mathrm{MST}\big(G[T \cup X]\big)\]

Ist \(G[T\cup X]\) nicht zusammenhängend, zählt dieses \(X\) nicht (Ergänzung dieser Seite). Die Aufgabe ist also, ein gutes \(X\) zu finden. Die Zahl der Mengen \(X\) wächst mit \(2^{\lvert V\setminus T\rvert}\). Dreyfus–Wagner umgeht die Aufzählung. Für Teilmengen \(S\) der ersten \(t-1\) Terminals und Knoten \(v\) sei \(D[S][v]\) die Länge des kürzesten Baums, der die Terminals in \(S\) und den Knoten \(v\) verbindet, und \(d(u,v)\) der kürzeste Abstand im Plan. Dann gilt mit den echten Zerlegungen von \(S\) in \(A\) und \(S\setminus A\) (disjunkt und beide nichtleer; mit \(A=S\) wäre die Rekursion zirkulär)

\(D[S][v] = \min_u \big( \min_{\emptyset\ne A\subsetneq S} D[A][u] + D[S\setminus A][u] \big) + d(u, v)\)

Für \(S=\{s\}\) ist \(D[S][v]=d(s,v)\), und das letzte Terminal dient als Wurzel (beides Ergänzung dieser Seite, Standardform). Der Aufwand ist \(O(3^{t} n + 2^{t} n^2)\) mit \(n=\lvert V\rvert\), und eine Rückverfolgung liefert den Baum.

Garantie: KMB und TM liefern höchstens \(2\,(1-1/t)\) mal das Optimum. Der Spannbaum über den Metrik-Abschluss der Terminals ist höchstens \(2\) mal so lang wie der Steinerbaum, im rechtwinkligen Gitter der Ebene (Abstände nach Manhattan) höchstens \(3/2\) mal (Hwang 1976); die Demo prüft das nur auf dem ungestörten, ungesperrten Gitter. In der Literatur steht statt \(t\) die Zahl der Blätter des optimalen Baums, die höchstens \(t\) ist (aus dem Gedächtnis, nicht nachgeprüft).

Herleitung Schritt für Schritt

Zwei Standardargumente, für diese Seite zusammengefasst. Die Demo belegt die Aussagen nur durch Prüfungen an Beispielen (siehe Befunde). Voraussetzung: \(c_e>0\); im Metrik-Abschluss gilt die Dreiecksungleichung, weil Abstände kürzeste Wege sind.

• Schritt 1, Kernsatz: Sei \(S\) ein Steinerbaum mit Knotenmenge \(T\cup X\). Dann ist \(S\) ein Spannbaum von \(G[T\cup X]\), also \(c(S)\ge\mathrm{MST}(G[T\cup X])\). Umgekehrt ist jeder minimale Spannbaum von \(G[T\cup X]\) ein Baum, der \(T\) enthält, also ein zulässiger Steinerbaum. Das Minimum über alle \(X\) ist daher das Optimum.
• Schritt 2, Verdopplung: Verdoppelt man jede Kante eines optimalen Steinerbaums, entsteht ein geschlossener Kantenzug der Länge \(2\,\mathrm{OPT}\), der jede Kante zweimal durchläuft (Euler-Tour). Folgt man ihm und überspringt Knoten, die schon besucht oder keine Terminals sind, bleibt ein Rundweg durch alle \(t\) Terminals. Wegen der Dreiecksungleichung ist die Summe seiner Abstände im Metrik-Abschluss höchstens \(2\,\mathrm{OPT}\).
• Schritt 3, Basislinie: Der Rundweg hat \(t\) Kanten. Lässt man die längste weg, bleibt ein Pfad, also ein Spannbaum der Terminals, mit höchstens dem \((1-1/t)\)-fachen der Rundweglänge, weil die längste Kante mindestens der Durchschnitt ist. Der minimale Spannbaum über die Terminals ist nicht länger, also höchstens \(2\,(1-1/t)\,\mathrm{OPT}\).
• Schritt 4, KMB: Ersetzt man die Kanten dieses Spannbaums durch kürzeste Wege, ist die Vereinigung nicht länger als die Summe der Abstände. Der anschließende minimale Spannbaum und das Abschneiden der Blätter machen sie nicht länger. KMB erreicht daher dieselbe Schranke. Für TM beruht sie auf Takahashi und Matsuyama (1980; aus dem Gedächtnis, nicht nachgeprüft).
• Schritt 5, Aufwand von Dreyfus–Wagner: Es gibt \((2^{t-1}-1)\,n\) Zustände \((S,v)\). Die Paare \((A,S)\) mit \(A\subseteq S\subseteq\{1,\dots,t\}\) sind \(3^t\), weil jedes Terminal in \(A\), in \(S\setminus A\) oder nicht in \(S\) liegt. Für jedes dieser Paare und jeden Knoten \(u\) wird eine Summe gebildet; das sind \(3^t n\) Summen.

Durchgerechnetes Beispiel von Hand

Das Lehrbuchbeispiel ist ein Gitter aus 3 × 3 Kreuzungen, alle Straßen haben die Länge 1, keine ist gesperrt. Vier Terminals liegen links (W), rechts (E), unten (S) und oben (N) um die Mitte M, die kein Terminal ist.

• Basislinie: Je zwei Terminals haben den Abstand 2: die im Kreis benachbarten (W–S, S–E, E–N, N–W) über M oder über eine Ecke, die gegenüberliegenden (W–E, S–N) nur über M. Der Spannbaum über die Terminals nimmt drei Kanten der Länge 2: Kosten 2 + 2 + 2 = 6.
• Mit M als Steinerknoten: Vier Straßen der Länge 1 verbinden alle Terminals mit M: Kosten 4. Das ist das Optimum. Rechnung dieser Seite: Ein Baum der Länge 3 hätte bei ganzzahligen Längen nur vier Knoten, also nur die Terminals, die paarweise nicht benachbart sind und daher keine Kante hätten.
• Verhältnis: \(6/4=3/2\), die Ersparnis ist 33,33 %. Das ist die Schranke für das rechtwinklige Gitter, und das Beispiel erreicht sie.
• KMB und TM mit dem Depot als Wurzel gehen die Wege einzeln und zahlen 6, TM mit der besten Wurzel und die Lokalsuche finden 4. Rechnung dieser Seite zur Ursache: Im Metrik-Abschluss gibt es sechs Kanten der Länge 2; die vier benachbarten Paare haben je zwei kürzeste Wege, einen über M und einen über eine Ecke. Laufen alle drei gewählten Wege über M, vereinigen sie sich zu den vier Straßen und KMB kostet 4. Laufen zwei über Ecken, sind es 6 (eine einzelne Ecke ergäbe 5). Das Ergebnis hängt hier also von der Regel bei gleich langen Wegen ab. Nach einer Nachprüfung dieser Seite am Quelltext der Demo wählt sie für zwei der drei Wege die Ecke.

Befunde

Soweit nicht anders angegeben, gelten die Zahlen für einen Plan mit 8 × 8 Kreuzungen, 7 Terminals, 10 % gesperrten Straßen und gleichverteilten Terminals. Sweeps sind Mediane über 5 feste Instanzen, Verteilungen laufen über 50 feste Instanzen. Die Rechnung hat keinen Zufall im Kern, die Instanzen sind fest. Bis 13 Terminals ist der Bezug der Aufschläge das Optimum, darüber der beste Fund der Heuristiken.

Frage	Befund
Stimmen Kernsatz und Dreyfus–Wagner?	Ja, direkt geprüft: Dreyfus–Wagner liefert dasselbe wie das Minimum über alle Mengen von Steinerknoten (Brute-Force auf 200 Zufallsgraphen mit Gleichständen und 40 Plänen). Der Kernsatz stimmt zusätzlich mit einer davon unabhängigen Aufzählung aller Bäume in 60 Kleingraphen überein.
Was sparen Steinerpunkte je Terminalzahl?	Ersparnis des besten Baums gegen die Basislinie (Median) bei t = 3 bis 13: zwischen 5,8 % (t = 9) und 14,4 % (t = 4), bei t = 7 sind es 14,3 %. Ab 20/30 Terminals (ohne exaktes Verfahren, Bezug: bester Heuristik-Fund): 5,6/2,1 %.
Wie verbreitet ist die Ersparnis über viele Instanzen?	Bei t = 7 sparen Steinerpunkte in 92 % der Instanzen, im Mittel 8,6 %, höchstens 20,5 % (größtes Verhältnis 1,26). Bei t = 11: 98 %/8,5 %/17,9 % (1,22). Bei t = 9 mit 30 % gesperrten Straßen: 100 %/11,6 %/20,2 % (1,25).
Terminals in Gruppen?	Bei t = 9 sparen Steinerpunkte in nur 50 % der Instanzen, im Mittel 2,1 %. Im Median über 5 Instanzen sind es 5,8 % (gleichverteilt) gegen 5,0 % (Gruppen). Bei t = 7 ist die Median-Ersparnis 14,3 % gleichverteilt gegen 0,0 % in Gruppen.
Wirkung gesperrter Straßen?	Ersparnis bei 0/10/20/30/40 % gesperrten Straßen: 6,7/14,3/11,4/15,4/18,0 %; Verzweigungen im besten Baum 1/3/2/2/2. Im Trend steigt die Ersparnis, aber nicht monoton.
Wirkung der Plangröße?	Ersparnis bei 5 bis 14 Kreuzungen je Seite: zwischen 1,1 % (6 je Seite) und 14,3 % (8 je Seite). Kein klarer Trend.
Wie viele Verzweigungen?	Bei t = 7 und 10 % Sperrung hat der beste Baum im Median 9 Steinerknoten, davon 3 Verzweigungen. Die übrigen Steinerknoten sind nur Durchgang (Grad 2).

Güte der Verfahren, gemessen am Optimum:

Verfahren	Befund
KMB	Aufschlag (Median über 5 Instanzen) bei t = 4 bis 13 zwischen +6,1 und +10,2 %, bei t = 3: 0. Über 50 Instanzen bei t = 7: optimal in 26 %, mittlerer Aufschlag 5,12 %, größter 20,11 %. Bei t = 11: 2 %, 5,76 %, 14,35 %.
TM mit Depot als Wurzel	Aufschlag (Median über 5 Instanzen) 0 oder +1,4 bis +6,3 %. Über 50 Instanzen bei t = 7: optimal in 30 %, mittlerer Aufschlag 3,21 %, größter 15,52 %.
TM mit bester Wurzel	Median-Aufschlag 0 bei jedem t. Über 50 Instanzen bei t = 7: optimal in 56 %, mittlerer Aufschlag 1,18 %, größter 6,18 %.
KMB gegen TM (Depot)	TM schlägt KMB in 40 % der Instanzen (t = 7; bei t = 11: 72 %), KMB schlägt TM in 10 % (bei t = 11: 4 %). KMB ist nicht durchgehend schlechter.
Lokalsuche	Median-Aufschlag 0 bei jedem t und jeder Sperrung. Über 50 Instanzen bei t = 7: optimal in 62 %, mittlerer Aufschlag 1,08 %, größter 6,18 %. Sie verbessert den Start (das beste Ergebnis von KMB, TM und TMR) in 6 % der Instanzen (bei t = 11: 22 %). Auf größeren Plänen liegt der Aufschlag (Median über 5 Instanzen) bei 10 und 14 Kreuzungen je Seite bei 2,25 und 2,33 %, bei 12 nur bei 0,17 %.
Steiner-Verhältnis	Höchstens 2 in jedem Graphen (in den Prüfungen über Zufallsgraphen und Pläne nie verletzt). Auf dem ungestörten, ungesperrten Gitter höchstens 1,40 in 300 Instanzen (Schranke 3/2), mit 20 % gesperrten Straßen 1,36.
Aufwand des exakten Wegs	Zustände (Teilmenge, Kreuzung): \((2^{t-1}-1)\,n\), auf dem 8 × 8-Plan bei t = 4/8/12: 448/8128/131 008. Gemessen ca. 1 s bei t = 13 und 3 s bei t = 14 (Plan 10 × 10), daher nur bis t = 13.

Ausgewählte Einzelinstanzen (Plan 8 × 8, 7 Terminals, 10 % gesperrt, wenn nicht anders angegeben). Die Einzelinstanz weicht von den Medianen ab, belastbar sind die Mediane.

Einzelinstanz	Befund
Voreingestellte Instanz (11 gesperrte Straßen)	Basislinie 170,42, Optimum 161,69 (−5,12 %) mit einer Verzweigung; KMB, TM, Lokalsuche und exakt finden dasselbe.
KMB weit über dem Optimum	KMB und TM (Depot) 195,87, genau so viel wie die Basislinie (+18,22 % über dem Optimum 165,68); TM mit bester Wurzel und Lokalsuche 167,29 (+0,97 %).
Lokalsuche bleibt hängen	Lokalsuche 166,75 (+8,71 % über dem Optimum 153,39), KMB 171,22 (+11,62 %); das Optimum hat 2 Verzweigungen, die Lokalsuche 1.
KMB schlägt TM	KMB 161,11 (+4,63 %), TM (Depot) 176,07 (+14,35 %); TM mit bester Wurzel, Lokalsuche und exakt 153,98.
Viele Terminals (Plan 10 × 10, t = 13)	Alle Heuristiken 302,76 (+1,50 % über dem Optimum 298,29); das Optimum hat 4 Verzweigungen, die Heuristiken 2; Ersparnis des Optimums 6,84 % gegen 320,20.
Starke Sperrung (40 %, 45 von 112 Straßen)	Basislinie 312,14, Optimum 251,72 (−19,36 %) mit 5 Verzweigungen; alle Verfahren finden es.
Gruppierte Terminals (t = 9)	Steinerpunkte sparen nichts (99,47 gegen 99,47).

Grenzen und was die Messung zeigt

Das zeigt die Messung:

• Die Referenz: Dreyfus–Wagner und der Kernsatz sind gegen unabhängige Aufzählungen geprüft. Aufschläge bei bis zu 13 Terminals sind daher Abstände zum echten Optimum.
• Die Richtung bei gleichverteilten Terminals: Über 50 Instanzen und mehrere Terminalzahlen sparen Steinerpunkte in den meisten gemessenen Instanzen etwas, und KMB trifft den besten Baum nur in einer Minderheit.
• Die Garantie: \(2\,(1-1/t)\) mal das Optimum wurde in den Prüfungen (Zufallsgraphen, Pläne mit Sperrungen und Gruppierung) nie verletzt. Die gemessenen Aufschläge liegen weit darunter.

Das zeigt sie nicht:

• Jede Sweep-Zahl ist ein Median aus nur 5 Instanzen. Eine Einzelinstanz kann stark abweichen (die voreingestellte Instanz spart 5,12 %, der Median bei t = 7 ist 14,3 %). Die Reihenfolge benachbarter Werte (Sperrungen, Plangröße, Terminalzahl) ist bei 5 Instanzen je Wert nicht belastbar.
• Gruppierung: Dass Gruppen weniger sparen, zeigt sich klar bei t = 7 und über 50 Instanzen bei t = 9, nur schwach im Median über 5 Instanzen bei t = 9. Mittel über 50 und Median über 5 sind verschiedene Kennzahlen auf verschiedenen Instanzen.
• Der Bezug der Ersparnis ist die Basislinie. Sie rechnet jede Verbindung mit ihrem vollen Weg, auch wo Wege überlappen. Wer ohnehin gemeinsame Wegstücke nur einmal bezahlt, hat einen anderen Bezug (Rechnung dieser Seite, keine Messung der Demo). Das Lehrbuchbeispiel zeigt es: Läuft jeder Weg über M, kostet schon die Vereinigung der Wege 4, die Basislinie bleibt bei 6.
• Aufschläge bei mehr als 13 Terminals sind Abstände zwischen Heuristiken, keine Abstände zum Optimum.
• Graph-Steiner: Steinerpunkte sind hier nur Kreuzungen des Plans. Das euklidische Steiner-Problem mit frei wählbaren Punkten ist ein anderes (bekannte Konstante \(2/\sqrt{3}\approx 1{,}155\), hier weder gebaut noch nachgemessen). Die Schranke 3/2 gilt für das rechtwinklige Gitter und wurde nur auf dem ungestörten, ungesperrten Gitter geprüft.
• Der exakte Weg ist klein. Der Stand der Technik (Reduktionen, Branch-and-Cut, SCIP-Jack, PACE 2018) löst Instanzen mit tausenden Terminals und ist nicht gebaut. Auch die LP-Verfahren von Byrka, Grandoni, Rothvoß und Sanità (2013, Näherungsgüte \(\ln 4+\varepsilon\approx 1{,}39\)) sind nur genannt. Die Sekundenangaben sind Messungen auf einem Rechner.
• Das Modell ist synthetisch: gestörtes Gitter, Länge als einzige Kosten, keine Kosten für Steinerpunkte, keine Kapazitäten. Für echte Netze liegt keine Messung vor.
• Die Lokalsuche kennt nur Einfügen oder Entfernen eines einzelnen Knotens. Sie bleibt hängen, wenn erst ein ganzer Umweg gleichzeitig entfällt.

Erweiterungen und Verweise

Die Basislinie ist der Sonderfall, in dem jede Verbindung ihren eigenen Weg bekommt und nichts geteilt wird. Ihren Spannbaum über die Terminals berechnet das Verfahren von Kruskal (Der Kruskal-Algorithmus verständlich erklärt). Auf dem Steiner-Baum baut der Prize-Collecting-Steiner-Baum auf, bei dem nicht jeder Kunde angeschlossen werden muss, weil der Anschluss einen Erlös bringt; dazu gibt es eine eigene Demo der Spannbaum-Reihe. Die Übersicht steht auf der Seite Spannbäume.

Quellen

• Takahashi, H., & Matsuyama, A. (1980): An approximate solution for the Steiner problem in graphs. Mathematica Japonica 24(6), 573–577.
• Kou, L., Markowsky, G., & Berman, L. (1981): A fast algorithm for Steiner trees. Acta Informatica 15, 141–145.
• Dreyfus, S. E., & Wagner, R. A. (1971): The Steiner problem in graphs. Networks 1(3), 195–207.
• Hwang, F. K. (1976): On Steiner minimal trees with rectilinear distance. SIAM Journal on Applied Mathematics 30(1), 104–114.
• Byrka, J., Grandoni, F., Rothvoß, T., & Sanità, L. (2013): Steiner tree approximation via iterative randomized rounding. Journal of the ACM 60(1) (in der Demo nur genannt, nicht gebaut).
• Quelltext, Messreihen und Prüfungen der Demo: github.com/sebastian-hanisch/steiner-tree-demo.

Die Literaturangaben wurden für diese Seite nicht nachgeschlagen, sondern aus dem Quellenverzeichnis der Demo übernommen. Die Argumente der Herleitung (Verdopplung des Baums, Zählung der Paare) sind Standardwissen der Theorie und stehen nicht in der Demo; deren Prüfungen belegen die Aussagen an Beispielen.