Steinerbaumproblem – einfach erklärt

Grundidee und Definition

Das Steinerbaumproblem ist ein Problem der kombinatorischen Optimierung und eine Verallgemeinerung des Problems des minimalen Spannbaums. Gesucht wird ein kürzestes Wegenetz, das endlich viele vorgegebene Punkte miteinander verbindet. Diese vorgegebenen Punkte heißen Terminale. Beim minimalen Spannbaum dürfen nur die Terminale verbunden werden. Beim Steinerbaumproblem dürfen zusätzlich Punkte aus einer gegebenen Menge von Nichtterminalen verwendet werden. Solche hinzugefügten Verzweigungspunkte heißen Steinerpunkte oder Steinerknoten.

Das Ergebnis ist ein Baum, also ein zusammenhängender Graph ohne Kreise. Die Schwierigkeit besteht vor allem darin, eine geeignete Auswahl der Steinerpunkte zu treffen. Anwendungen liegen unter anderem in der Planung von Wege- und Telekommunikationsnetzen sowie im Entwurf integrierter Schaltkreise.

Allgemein kann eine Menge V gegeben sein, auf der eine Metrik definiert ist. Eine Metrik beschreibt Abstände und erfüllt insbesondere die Dreiecksungleichung. Die Terminalmenge T ist eine endliche Teilmenge von V. Gesucht wird ein Graph, der alle Knoten aus T verbindet und bei dem die Summe der Abstände minimal ist. Falls nötig, dürfen Knoten aus V\T als Steinerpunkte verwendet werden.

In der Graphen-Variante ist G=(V,E) ein zusammenhängender, ungerichteter Graph ohne Mehrfachkanten. V ist die Knotenmenge, E die Kantenmenge, und jede Kante besitzt ein positives reelles Gewicht. Gesucht ist eine gewichtsminimale Teilmenge der Kanten, die alle Terminale verbindet; dabei dürfen auch Nichtterminale benutzt werden. Für eine Aufgabenstellung kann es mehrere minimale Steinerbäume geben, in manchen Metriken auch gar keinen oder unendlich viele. Der Ausdruck „minimaler Steinerbaum“ ist normalerweise überflüssig, weil „Steinerbaum“ bereits den minimalen Baum bezeichnet; gelegentlich wird der Begriff aber auch für einen strukturell geeigneten Kandidaten verwendet.

Die metrische und die graphentheoretische Definition sind nicht vollständig äquivalent. In einem Graphen fehlen gewöhnlich Kanten zwischen manchen Knoten; dies würde einem Abstand Unendlich entsprechen, während eine Metrik immer reelle Werte besitzt. Praktisch kann man fehlende Kanten durch sehr große Gewichte ersetzen, die größer als die Summe aller vorhandenen Kantengewichte sind. Außerdem wird in der Graphen-Variante die Dreiecksungleichung nicht verlangt. Deshalb kann ein Umweg über Steinerpunkte günstiger sein als eine direkte Kante.

Nichtmetrische Kantengewichte lassen sich auf den metrischen Fall zurückführen: Man bildet einen vollständigen Graphen M und definiert das Gewicht zwischen A und B als die Länge eines kürzesten Pfades zwischen A und B in G. Nach der Lösung in M werden Kanten, die in G durch einen kürzeren Pfad ersetzt werden können, durch solche kürzesten Pfade ersetzt. Die Gesamtlänge bleibt dabei unverändert.

Euklidisches Steinerbaumproblem

Beim euklidischen Steinerbaumproblem liegen die Punkte in der Ebene, und die Länge einer Verbindung wird durch die euklidische Geometrie bestimmt. Die Menge möglicher Nichtterminale ist dabei unendlich, sogar überabzählbar; endlich bleibt nur die Zahl der Terminale. Diese Variante ist besonders anschaulich.

Für drei Punkte bildet das Dreieck den einfachsten nichttrivialen Fall. Falls jeder Winkel des Dreiecks kleiner als 120° ist, ist der erste Fermat-Punkt der einzige Steinerpunkt. Der Steinerbaum besteht dann aus den drei Verbindungslinien von diesem Punkt zu den drei Ecken. Ist dagegen ein Winkel größer oder gleich 120°, besteht der Steinerbaum aus den beiden Schenkeln dieses Winkels. In beiden Fällen enthält der Steinerbaum des Dreiecks keinen Winkel kleiner als 120°.

Daraus folgen wichtige notwendige Eigenschaften:

An keiner Stelle des Steinerbaums darf ein Winkel zwischen zwei Kanten kleiner als 120° sein. Das gilt sowohl für Terminals als auch für Steinerpunkte, weil sich ein solcher Winkel durch den Steinerbaum des zugehörigen Dreiecks verkürzen ließe.
Von jedem Steinerpunkt gehen genau drei Kanten aus. Die Winkel zwischen ihnen betragen jeweils 120°. Weniger als drei Kanten wären unnötig, mehr als drei würden die Winkelbedingung verletzen.
Sind alle n Terminale Blätter des Baums, spricht man von einem vollen Steinerbaum. Dann gibt es genau n−2 Steinerpunkte. Wenn nicht alle Terminale Blätter sind, gibt es weniger als n−2 Steinerpunkte.
Jeder Steinerbaum kann eindeutig in kantendisjunkte volle Steinerbäume zerlegt werden. Terminale, die keine Blätter sind, gehören dabei zu zwei oder drei Komponenten, je nachdem, wie viele Kanten von ihnen ausgehen.

Im Beispiel mit fünf Flughäfen gibt es zwei Steinerpunkte. Der Punkt S ist kein Blatt; deshalb enthält der Baum weniger als 5−2=3 Steinerpunkte. Er lässt sich in zwei volle Steinerbäume mit den Terminalmengen {I,S} und {L,S,K,G} zerlegen. Der Winkel bei S ist größer als 120°, die übrigen relevanten Winkel betragen 120°.

Diese Eigenschaften sind notwendig, aber nicht hinreichend für Minimalität. Ein Baum mit n Blättern, n−2 inneren Punkten, Grad 3 und 120°-Winkeln muss nicht die kürzeste Lösung sein. Ebenso muss eine Vereinigung von Steinerbäumen nicht für die gesamte Terminalmenge minimal sein, selbst wenn die Winkelbedingung an den Verbindungsstellen gilt.

Die Konstruktion über Fermat-Punkte kann iterativ auf mehr als drei Punkte erweitert werden. Sie liefert im Allgemeinen jedoch nur lokal minimale Bäume: Eine Verschiebung eines einzelnen Steinerpunkts verkürzt den Baum nicht mehr. Ein globales Minimum erhält man dadurch nur, wenn alle sehr zahlreichen möglichen Varianten geprüft werden.

Graphentheoretisches Modell und Beispiel

Beim graphentheoretischen oder diskreten Steinerbaumproblem sind die möglichen Punkte und Verbindungen durch einen Graphen festgelegt. Ein anschauliches Beispiel ist ein Staat, der sein bestehendes Schienennetz elektrifizieren möchte. Neue Gleise dürfen nicht gebaut werden, und das Budget reicht nicht für das gesamte Netz. Es sollen daher so viele vorhandene Strecken mit Oberleitungen versehen werden, dass man von jeder Großstadt mit einer Elektrolokomotive in jede andere Großstadt fahren kann. Fahrten durch Kleinstädte sind erlaubt. Die Gesamtkosten hängen in der Vereinfachung nur von den Streckenlängen ab.

Das Schienennetz wird als Graph dargestellt: Städte sind Knoten, vorhandene Bahnstrecken sind Kanten, und die Streckenlänge ist das Kantengewicht. Die Großstädte bilden die Terminale. Gesucht wird eine gewichtsminimale Teilmenge der Kanten, die alle Großstädte verbindet. Die nicht als Terminale benötigten Städte können als Steinerknoten dienen.

Im angegebenen Beispiel benötigt der gefundene Steinerbaum 190 km Oberleitung. Mit weniger Leitung lässt sich die Zielsetzung nicht erfüllen. Für größere Schienennetze mit mehr Städten ist es jedoch für Menschen und Computer praktisch unmöglich, eine optimale Lösung immer direkt zu finden.

Komplexität und Approximationsalgorithmen

Die Entscheidungsvariante des graphentheoretischen Steinerbaumproblems fragt bei natürlichen Kantengewichten und einer natürlichen Zahl k, ob ein Steinerbaum mit Gewicht höchstens k existiert. Eine solche Ja-Instanz gehört zu den 21 klassischen NP-vollständigen Problemen, deren Zugehörigkeit zu dieser Klasse Richard Karp 1972 zeigen konnte. Das Optimierungsproblem ist damit NP-schwer.

In der Praxis können auch sehr große Instanzen mit teilweise Millionen von Kanten innerhalb kurzer Zeit optimal gelöst werden. Theoretisch ist dies jedoch nicht garantiert. Deshalb verwendet man Approximationsalgorithmen. Sie liefern möglicherweise keine optimale, aber eine nachweislich begrenzte Lösung.

Ist die Zahl der Nichtterminale durch eine feste Zahl k beschränkt, kann ein Enumerationsalgorithmus einen minimalen Steinerbaum in polynomialer Zeit berechnen. Der Spezialfall k=0 entspricht dem minimalen Spannbaum. Der Dreyfus-Wagner-Algorithmus ist polynomial, wenn die Zahl der Terminale logarithmisch in der Graphgröße beschränkt ist, also höchstens c·log(|V|) für eine vorgegebene Konstante c beträgt. Der Spezialfall |T|=2 ist die Suche nach einem kürzesten Pfad.

Falls P ungleich NP ist, gibt es keine polynomialen Algorithmen, die beliebig gute approximative Lösungen für das allgemeine Problem liefern. Zu den kombinatorischen Verfahren mit bester bekannter Approximationsgüte gehören der relative Greedy-Algorithmus mit 1+ln 2+ε<1,694 und der Loss-Kontraktions-Algorithmus mit 1+ln(3/2)+ε<1,550. Bei beiden wird vermutet, dass die Analyse noch nicht bestmöglich ist; deshalb ist unklar, ob der relative Greedy-Algorithmus nicht doch besser approximiert. Beide Verfahren approximieren sogenannte k-Steinerbäume. Ein LP-basierter Algorithmus erreicht eine bessere Approximationsgüte von ln(4)+ε<1,39.

Diese Verfahren sind Approximationsschemata: Für jedes beliebig kleine ε>0 können sie die angegebene Güte erreichen. Ihre Laufzeit wächst allerdings stark, wenn ε kleiner wird, sodass sie für reale Anwendungen unbrauchbar sein können. Für Graphen mit Distanzen 1 und 2 ist ein Polynomialzeit-Algorithmus mit Approximationsgüte 1,25 bekannt.

Schneller sind die Algorithmen von Kou, Markowsky und Berman sowie von Mehlhorn. Das Verfahren von Kou, Markowsky und Berman hat Approximationsgüte 2 und Laufzeit O(|V|² · log|V| + |V| · |E|). Es berechnet einen Distanzgraphen und darauf einen minimalen Spannbaum. Mehlhorn verbessert die Laufzeit auf O(|V| · log|V| + |E|), indem er statt eines vollständigen einen modifizierten Distanzgraphen verwendet. Auch dieser Algorithmus hat Approximationsgüte 2. Die Analysen beider Verfahren gelten als bestmöglich.

Komplexität spezieller Varianten

Durch Einschränkungen und zusätzliche Bedingungen versucht man, den Suchraum des Steinerbaumproblems zu verkleinern und die Berechnung zu beschleunigen. Trotzdem bleibt das Problem NP-vollständig, wenn man es auf bipartite ungewichtete Graphen oder auf metrische Graphen beschränkt.

Beim metrischen Steinerbaumproblem kann die Knotenmenge auch unendlich sein, etwa wenn die gesamte Ebene als Knotenmenge betrachtet wird. Die Knoten sind dann entsprechend der verwendeten Metrik paarweise verbunden; nur die Zahl der Terminale bleibt endlich. Für die euklidische Metrik und die in praktischen Anwendungen häufige Manhattan-Metrik gibt es polynomielle Approximationsschemata. Dadurch können auch für mehrere Tausend Knoten gute Lösungen gefunden werden.

Für die Manhattan-Metrik lässt sich das Problem mithilfe des Hanangitters auf ein Steinerbaumproblem in Graphen reduzieren. Für die euklidische Metrik ist dagegen nicht bekannt, ob das Steinerbaumproblem NP-vollständig ist, weil bereits die Zugehörigkeit zur Komplexitätsklasse NP unbekannt ist.