Steinerbaum

Das Steinerbaumproblem (oft mit STEINER TREE notiert), ein nach dem Schweizer Mathematiker Jakob Steiner benanntes Problem der Graphentheorie, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Beim Steinerbaumproblem sucht man in einem umgebenden Graphen einen kleinsten Teilgraphen (den Steinerbaum), welcher eine Menge vorgegebener Endpunkte (die Terminale) miteinander verbindet.

Das Steinerbaumproblem gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.

Praktische Anwendung findet die Berechnung von Steinerbäumen unter anderem beim Entwurf von integrierten Schaltkreisen^[1] und von Telekommunikationsnetzen.

Definition

Sei G=(V, E) ein zusammenhängender, ungerichteter Graph ohne Mehrfachkanten, wobei V die Knotenmenge und E die Kantenmenge ist. Weiterhin sei T, die Menge der sogenannten Terminale, eine Teilmenge von V. Des Weiteren sei eine Funktion gegeben, die jeder Kante aus E einen positiven reellen Wert, ihr Gewicht, zuordnet, G ist also ein kantengewichteter Graph.

Gesucht ist nun ein Teilgraph, der alle Knoten aus T verbindet und bei dem die Summe der Kantengewichte minimal ist. Dabei können, falls nötig, auch Knoten aus V \ T verwendet werden; diese Knoten werden dann Steinerknoten oder Steinerpunkte genannt. Es ist leicht einzusehen, dass der Teilgraph ein Baum ist. Dieser wird Steinerbaum genannt.

Beispiel

Karte des Schienennetzes des gedachten Staats. Großstädte sind rot eingezeichnet, Kleinstädte schwarz.

Ein Staat möchte sein marodes Schienennetz modernisieren, damit es mit Elektrolokomotiven befahren werden kann. Dafür sollen die vorhandenen Gleise mit Oberleitungen versehen werden; neue Gleise sollen nicht verlegt werden. Allerdings reicht das Budget nicht für eine Elektrifizierung des gesamten Netzes, weshalb sich die Regierung entschließt, nur so viele Strecken zu elektrifizieren, dass es möglich ist, von jeder Großstadt mit einer E-Lok in jede andere Großstadt zu fahren (dabei wird nicht ausgeschlossen, dass die E-Lok auch durch Kleinstädte fährt). Gleichzeitig sollen die Gesamtkosten für die Modernisierung möglichst gering gehalten werden. Vereinfachend wird in diesem Beispiel davon ausgegangen, dass die Kosten der Modernisierung nur von der Streckenlänge abhängen, nicht etwa von Geländebeschaffenheit usw.

Graphrepräsentation des Schienennetzes. Die Zahlen stehen für Streckenlängen in km. Der Steinerbaum ist rot markiert.

Graphentheoretisch kann man das Streckennetz als Graph betrachten, bei dem die Knoten Städte repräsentieren und die Kanten vorhandene Bahnstrecken zwischen den Städten. Jeder Kante wird ein Zahlenwert (ihr Gewicht) zugewiesen, der der Streckenlänge entspricht. Man kann nun die zu verbindenden Großstädte als Terminale auffassen. Die Aufgabe ist somit, eine gewichtsminimale Teilmenge der Kanten zu finden, die alle Terminale verbindet; sprich: ein Oberleitungsnetz zu finden, das alle Großstädte verbindet und dabei so kostengünstig wie möglich ist. Die Suche nach dieser Teilmenge entspricht der Suche nach einem Steinerbaum.

Der rechts abgebildete Steinerbaum repräsentiert all die Strecken, die elektrifiziert werden müssen, um alle Großstädte zu verbinden. Hierfür sind in diesem Beispiel 190 km Oberleitung nötig; mit weniger Leitung ist die Zielsetzung nicht zu erreichen.

Während es bei diesem Beispiel noch relativ leicht ist, den Steinerbaum zu finden, ist es für größere Schienennetze mit mehr Städten für Computer ebenso wie für Menschen praktisch unmöglich, eine optimale Lösung zu finden.

Komplexität des allgemeinen Problems

Da das Steinerbaumproblem NP-vollständig ist, ist es nach heutigem Kenntnisstand aussichtslos, Problemstellungen ab einer bestimmen Größe optimal lösen zu wollen. Aus diesem Grund ist sinnvoll, Methoden zu untersuchen, welche durch Approximierung eine vielleicht nicht optimale, aber noch „gute“ Lösung für ein gegebenes Steinerbaumproblem liefern.

Approximierbarkeit

Mit Hilfe eines Enumerationsalgorithmus ist die Berechnung eines minimalen Steinerbaumes in polynomieller Zeit möglich, falls die Zahl der Nicht-Terminale beschränkt ist, d.h. falls man sich auf Instanzen beschränkt, bei denen für ein vorgegebenes k nicht mehr als k Nicht-Terminale enthalten sind. Ein Spezialfall ist hier k=0, der mit der Suche nach einem minimalen Spannbaum identisch ist.

Der Dreyfus-Wagner-Algorithmus liefert einen minimalen Steinerbaum in polynomieller Zeit, falls die Zahl der Terminale beschränkt ist, d.h. falls man sich auf Instanzen beschränkt, bei denen für ein vorgegebenes k nicht mehr als k Terminale enthalten sind. Ein Spezialfall ist hier k=2, der mit der Suche nach einem kürzesten Pfad identisch ist.

Falls P ungleich NP ist (siehe P-NP-Problem), so gibt es auch keine polynomiellen Algorithmen, die beliebig gute approximative Lösungen liefern (PAS).^[2]

Die Approximationsalgorithmen mit der besten bekannten Approximationsgüte sind der relative Greedy-Algorithmus (Approximationsgüte 1 + ln2 < 1,694) und der Loss-Kontraktions-Algorithmus (Approximationsgüte 1 + ln(3 / 2) < 1,550^[3]). Für beide Algorithmen wird vermutet, dass ihre Analyse bisher nicht bestmöglich ist. Insofern ist nicht klar, ob der relative Greedy-Algorithmus nicht doch besser als der Loss-Kontraktions-Algorithmus approximiert. Beide Algorithmen versuchen sogenannte k-Steinerbäume zu approximieren. Streng genommen handelt es sich bei beiden Algorithmen um Approximationsschemata, also eine Menge von Algorithmen, deren Approximationsgüte sich wenigstens den genannten Werten nähert. Ihre Laufzeit ist für reale Anwendungen allerdings unbrauchbar.

Effizientere Approximationsalgorithmen

Der Algorithmus von Kou, Markowsky und Berman erreicht Approximationsgüte 2 und ist mit Laufzeit O(|V|² · log|V| + |V| · |E|) wesentlich schneller als der relative Greedy-Algorithmus oder der Loss-Kontraktions-Algorithmus. Er berechnet dazu einen Distanzgraphen und darauf einen minimalen Spannbaum. Die Berechnung des Distanzgraphen bestimmt im wesentlichen die Laufzeit des Algorithmus. Der Algorithmus von Mehlhorn verbessert diese Laufzeit auf O(|V| · log|V| + |E|), indem er statt eines vollständigen nur einen modifizierten Distanzgraphen berechnet.^[4] Auch der Algorithmus von Mehlhorn erreicht Approximationsgüte 2. Die Analyse der Algorithmen von Kou-Markowsky-Berman bzw. Mehlhorn ist bestmöglich.

Komplexität spezieller Varianten

Wie bei vielen anderen schweren Problemen der theoretischen Informatik gibt es auch für das Steinerbaumproblem zahlreiche einschränkende Varianten. Hierbei versucht man, durch Einschränkungen und Nebenbedingungen den Suchraum des Problems drastisch zu verkleinern und somit die Berechnung einer Lösung stark zu beschleunigen.

Das Steinerbaumproblem bleibt jedoch weiterhin NP-vollständig, wenn man sich auf bipartite ungewichtete Graphen beschränkt. Auch bei Beschränkung auf metrische Graphen bleibt das Problem noch NP-vollständig.

Oft wird das metrische Steinerbaumproblem auch so verallgemeinert, dass die Menge der Knoten unendlich ist, zum Beispiel wird bei vielen Problemstellungen die Ebene als Knotenmenge betrachtet. Die Knoten sind dann paarweise durch eine Kante entsprechend der verwendeten Metrik verbunden. Lediglich die Zahl der Terminale bleibt dann weiter endlich. Für euklidische Metriken oder die Manhattan-Metrik, die in praktischen Anwendungen relativ häufig gegeben sind, existieren polynomielle Approximationsschemata, so dass sich selbst für mehrere Tausend Knoten gute Lösungen des Problems finden lassen.

Siehe auch

• Chipentwurf
• Floorplanning

Einzelnachweise

1. ↑ Siehe z. B.: Chiang, C., Sarrafzadeh, M., Wong, C.K. Global routing based on Steiner min-max trees. In: IEEE Transactions on Computer-Aided Design. Vol. 9, No. 12, 1990. ISSN 0278-0070
2. ↑ Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Hans Jürgen Prömel. Lower Bounds for Approximation Algorithms for the Steiner Tree Problem. In: Lecture Notes in Computer Science. Bd. 2204/2001. Springer, ISSN 0302-9743, S. 217. (PS; 239 KB)
3. ↑ G. Robins, A. Zelikovsky. Improved Steiner tree approximation in graphs. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2000, 770-779 (PDF; 260 KB)
4. ↑ K. Mehlhorn. A Faster Approximation Algorithm for the Steiner Problem in Graphs. Information Processing Letters, 27(2):125-128, 1988.

Literatur

• Hans Jürgen Prömel, Angelika Steger. The Steiner Tree Problem. A Tour through Graphs, Algorithms, and Complexity, Vieweg 2002, ISBN 3528067624.

Weblinks

• Ein Open Source Computerprogramm in C zur "exakten" Berechnung von minimalen euklidischen Steinerbäumen
• Ein Java-Applet zur Approximation von minimalen euklidischen Steinerbäumen
• Vorlesung zum Thema (auf Englisch) von Ronald L. Graham: The Shortest Network Problem (1988)