Steinerbaumproblem

Steinerbaumproblem

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.

Inhaltsverzeichnis

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 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

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 + ln 2 < 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

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 3-528-06762-4.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Steiner Tree — 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… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Steinerbaum-Problem — 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… …   Deutsch Wikipedia

  • Cliquenproblem — Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie. Das Cliquenproblem ist eines der 21 klassischen NP vollständigen Probleme, deren Zugehörigkeit zu dieser Klasse Richard M. Karp 1972 bewies.… …   Deutsch Wikipedia

  • Erfüllbarkeitsproblem der Aussagenlogik — Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von engl. satisfiability) ist ein Entscheidungsproblem. Es fragt, ob eine aussagenlogische Formel erfüllbar ist. Anwendungen finden sich unter anderem in der Komplexitätstheorie, Verifikation und… …   Deutsch Wikipedia

  • Feedback Vertex Set — Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP vollständig ist. Definition Es fragt, ob es zu einem ungerichteten Multigraphen G = (V,E) …   Deutsch Wikipedia

  • Hamiltonkreisproblem — Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Ob ein solcher Kreis in einem gegebenen Graph besteht, ist ein fundamentales Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren… …   Deutsch Wikipedia

  • Hitting-Set-Problem — Das Hitting Set Problem ist ein NP vollständiges Problem aus der Mengentheorie. Es gehört zur Liste der 21 klassischen NP vollständigen Probleme von denen Richard M. Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte. Gegeben ist eine… …   Deutsch Wikipedia

  • Jakob Steiner — (* 18. März 1796 in Utzenstorf; †  1. April 1863 in Bern) war ein Schweizer Mathematiker. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Karps 21 NP-vollständige Probleme — Eines der bedeutendsten Resultate der Komplexitätstheorie ist der von Stephen Cook im Jahr 1971 erbrachte Nachweis, dass das Erfüllbarkeitsproblem der Aussagenlogik (meist nur kurz SAT genannt) NP vollständig ist. 1972 griff Richard Karp diese… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”