Steinerbaumproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Das Steinerbaumproblem, ein nach dem Schweizer Mathematiker Jakob Steiner benanntes mathematisches Problem, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Hier wie dort wird der kürzeste Graph gesucht, der endlich viele gegebene Punkte (die Terminale) miteinander verbindet und der auf diese Weise das kürzeste Wegenetz zwischen diesen Punkten bildet. Beim Problem des minimalen Spannbaums wird dieser Graph nur zwischen den Terminalen aufgespannt, beim Steinerbaumproblem kann man dagegen aus einer ebenfalls gegebenen Menge (den Nichtterminalen) endlich viele weitere Punkte (die Steinerpunkte) zu den Ausgangspunkten hinzufügen, die dann als zusätzliche Verzweigungen im Wegenetz dienen, um dieses dadurch weiter zu verkürzen. Das Ergebnis ist wie beim minimalen Spannbaum ein ungerichteter zusammenhängender kreisfreier Graph, also ein Baum im Sinne der Graphentheorie. Die theoretische und praktische Schwierigkeit beim Lösen des Steinerbaumproblems besteht darin, eine geeignete Auswahl der Steinerpunkte zu treffen.

Ist die Menge der Nichtterminale endlich, so lässt sich das Steinerbaumproblem als rein graphentheoretisches Problem auffassen, in welchem aus dem Graphen aller, der terminalen wie der nichtterminalen Punkte ein Teilgraph bestimmt wird, der mindestens die Terminale enthält. Andere Steinerbaumprobleme, bei denen die Terminale Punkte in der Ebene oder einem anderen metrischen Raum sind, beziehen oft den gesamten Raum als Nichtterminale ein; diese Menge ist dann nicht endlich, also insbesondere nicht Knotenmenge eines Graphen.

Das graphentheoretische 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 bei der Planung von Wege- und Telekommunikationsnetzen und dem Entwurf von integrierten Schaltkreisen[1].

Definition[Bearbeiten]

Sei V eine Menge, auf der eine Metrik definiert ist. Sei weiter T, die Menge der sogenannten Terminale, eine endliche Teilmenge von V.

Ist auch die Menge V endlich, dann kann man sie als kantengewichteten Graphen auffassen, dessen Kantengewichte die Abstände sind. Der obige Teil der Definition liest sich dann so:

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.

Ausgehend von einer der beiden Auslangslagen ist nun jeweils ein Graph gesucht, der alle Knoten aus T verbindet und bei dem die Summe der Abstände bzw. 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 Graph ein Baum ist. Dieser wird Steinerbaum genannt. Es kann für eine Aufgabenstellung mehrere minimale solche Bäume geben, also mehrere Steinerbäume.

Der Begriff „minimaler Steinerbaum“ ist entweder pleonastisch, weil ein Steinerbaum sich durch Minimalität auszeichnet, oder aber undefiniert, wenn der Verwender einen allgemeineren Begriff von Steinerbaum im Sinn hatte, unter denen er die minimalen sucht. Man sollte einen Begriff „Steinerbaum“ ohne Minimalitätseigenschaft am besten vermeiden, oder aber eindeutig definieren. Der in der englischsprachigen Literatur mitunter verwendete Begriff „Steiner minimal tree“ (etwa „Steinerscher Minimalbaum“) vermeidet diese sprachliche Falle.

Die beiden Definitionen sind auch für endliche V nicht ganz genau äquivalent:

  • Der Graph wird in der Regel Paare von Knoten enthalten, zwischen denen es keine Kante gibt. Dem würde ein Abstand Unendlich in der Metrik entsprechen; eine Metrik ist aber immer reell. In der Praxis spielt das keine Rolle: man kann ja den nicht vorhandenen Kanten Gewichte zuordnen, die größer sind als die größten zwischen den Terminalen auftretenden Kantensummen, solche Kanten können dann im Steinerbaum nicht vorkommen.
  • Die Dreiecksungleichung wird in der zweiten Definition nicht gefordert. Damit kann der Fall eintreten, dass eine direkte Kante durch einen Umweg über einen oder mehrere Steinerpunkte ersetzt werden muss, um den Graphen zu minimieren. Auch solche Beispiele dürften keine praktische Relevanz haben.

Beispiel (graphentheoretische Variante des Problems)[Bearbeiten]

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.

Das Euklidische Steinerbaumproblem[Bearbeiten]

Als Beispiel eines Steinerbaumproblems in einem metrischen Raum mit unendlich (sogar überabzählbar) vielen Punkten sei hier das Euklidische Steinerbaumproblem genannt, also das Finden eines minimalen Wegenetzes zwischen endlich vielen Punkten in der Ebene. Es ist die anschaulichste und deswegen auch geschichtlich als erste erforschte Variante. Der einfachste nichttriviale Fall, der Steinerbaum für drei Punkte in der Ebene, ist seit dem 17. Jahrhundert durch Evangelista Torricelli gelöst: Falls jeder Winkel des gebildeten Dreiecks kleiner als 120° ist, ist der erste Fermat-Punkt des Dreiecks einziger Steinerpunkt und der Steinerbaum besteht aus den drei Verbindungslinien von dort zu den drei Ecken des Dreiecks (Beweis hier). Ist ein Winkel größer oder gleich 120°, so wird der Steinerbaum von dessen beiden Schenkeln gebildet.

Die Konstruktion lässt sich iterativ auf mehr als drei Punkte ausweiten. Allerdings führt sie im Allgemeinen zwar zu lokal minimalen Bäumen (d.h. der Baum wird bei keiner Verlagerung eines einzelnen Steinerpunkts kürzer), jedoch kommt man so nur dann zu einem globalen Minimum, wenn man alle der sehr zahlreichen Möglichkeiten durchprobieren würde, die sich bei jedem Schritt ergeben.

Das graphentheoretische Steinerbaumproblem[Bearbeiten]

Komplexität des allgemeinen Problems[Bearbeiten]

Da das Steinerbaumproblem NP-vollständig ist, ist es nach heutigem Kenntnisstand aussichtslos, beliebig große Problemstellungen immer optimal in vertretbarer Zeit zu lösen. Aus diesem Grund ist es sinnvoll, Methoden zu untersuchen, welche durch Approximierung eine vielleicht nicht optimale, aber dennoch „gute“ Lösung für ein gegebenes Steinerbaumproblem liefern.

Approximierbarkeit[Bearbeiten]

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 logarithmisch in der Größe des Graphen beschränkt ist, d.h. falls man sich auf Instanzen beschränkt, bei denen für eine vorgegebene Konstante c nicht mehr als c \cdot\log(|V|) Terminale enthalten sind. Ein Spezialfall ist hier |T|=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 kombinatorischen Approximationsalgorithmen mit der besten bekannten Approximationsgüte sind der relative Greedy-Algorithmus (Approximationsgüte 1+\ln 2 + \varepsilon< 1,694) und der Loss-Kontraktions-Algorithmus (Approximationsgüte 1+\ln(3/2) + \varepsilon <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. Eine bessere Approximationsgüte von \ln(4) + \varepsilon <1,39[4] erreicht ein LP-basierter Algorithmus. Bei allen genannten Algorithmen handelt es sich um Approximationsschemata, also eine Menge von Algorithmen, die die genannte Approximationsgüte für jedes beliebig kleine \varepsilon > 0 erreichen. Ihre Laufzeit steigt allerdings sehr stark mit fallendem \varepsilon und ist daher für reale Anwendungen unbrauchbar.

Effizientere Approximationsalgorithmen[Bearbeiten]

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.[5] 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[Bearbeiten]

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. Während sich das Steinerbaumproblem für die Manhattan-Metrik mit dem Hanangitter auf das Steinerbaumproblem in Graphen reduzieren lässt[6], ist für das Steinerbaumproblem in der euklidischen Metrik nicht bekannt, ob es NP-vollständig ist, da die Zugehörigkeit zur Komplexitätsklasse NP unbekannt ist.

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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. Goemans, Michel X. and Olver, Neil and Rothvoß, Thomas and Zenklusen, Rico. Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations. In: Proceedings of the 44th Symposium on Theory of Computing. STOC 2012, 1161-1176
  5. K. Mehlhorn. A Faster Approximation Algorithm for the Steiner Problem in Graphs. Information Processing Letters, 27(2):125-128, 1988.
  6. M. Hanan, On Steiner’s problem with rectilinear distance, J. SIAM Appl. Math. 14 (1966), 255 - 265.

Literatur[Bearbeiten]

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

Weblinks[Bearbeiten]