Ziel des euklidisches Steinerbaumproblems (ESTP) ist es, n fix lokalisierte Punkte in der euklidischen Ebene distanzminimal
miteinander zu verbinden. Hierbei können, im Gegensatz zum minimalen Spannbaum-Problem, zu den ursprünglichen n Punkten weitere Punkte hinzugefügt werden, um die Länge der Verbindungen zu reduzieren.
Zur Lösung des ESTP sind die folgenden Fragen zu beantworten: Wieviele zusätzliche Punkte sollen den n Ausgangspunkten gegebenenfalls hinzugefügt werden? Wo sind diese zusätzlichen Punkte in der euklidischen Ebene einzubetten? Wie sollen die Punkte der Gesamtknotenmenge miteinander verbunden werden?
Das ESTP lässt sich also kurz und prägnant charakterisieren. Wie sich im weiteren Verlauf dieser Arbeit herausstellen wird, ist es mit wachsender Problemgröße jedoch schwer eine exakte Lösung für diese Fragestellung zu ermitteln.
Das ESTP findet überall dort Anwendung, wo eine gegebene Anzahl von Punkten in der Ebene distanzminimal miteinander zu verbinden ist. Wichtige Anwendungsfelder finden sich demnach vor allem im Bereich des Netzwerkdesigns. Von der Gestaltung von Rohrleitungssystemen, über die Planung von Elektrizitätsnetzwerken, bis hin zur Strukturierung von Telekommunikationsnetzen erstrecken sich breite Anwendungsgebiete.
Inhaltsverzeichnis
1 Einleitung
1.1 Was ist ein euklidisches Steinerbaumproblem ?
1.2 Motivation und praktische Relevanz
2 Grundlegende Definitionen
2.1 Definitionen aus der Graphentheorie
2.2 Spezifische Terminologie zum ESTP
3 Geometrische Lösungen zum ESTP
3.1 Lösung des ESTP für n=3
3.2 Lösung des ESTP für n=4
4 Grundlegende Resultate für das ESTP
4.1 Eigenschaften von euklidischen Steinerbäumen
4.2 Die Steinertopologien
4.3 Die Komplexität des Problems
5 Exakte Algorithmen zum ESTP
5.1 Der Melzak-Algorithmus
5.1.1 Die Funktionsweise des Verfahrens
5.1.2 Beschränkung auf volle Steinertopologien
5.1.3 Erzeugung voller Steinerbäume in linearer Laufzeit
5.2 Der Algorithmus von Smith
5.3 Herausforderungen exakter Algorithmen
5.4 Der Geosteiner-Algorithmus
6 Der minimale Spannbaum
6.1 Der Algorithmus von Prim
6.2 MST als Näherung für den euklidischen Steinerbaum
7 Heuristiken zum ESTP
7.1 Die Beasley-Heuristik
7.2 Ausblick: Weitere Heuristiken
8 Zusammenfassung
9 Anhang
Zielsetzung & Themen
Das Hauptziel dieser Arbeit ist die fundierte Untersuchung des euklidischen Steinerbaumproblems (ESTP), welches darin besteht, eine gegebene Menge von Terminalpunkten in der euklidischen Ebene durch das Hinzufügen zusätzlicher Knoten (Steinerpunkte) distanzminimal zu verbinden. Die Forschungsfrage fokussiert sich dabei sowohl auf die theoretischen Grundlagen und geometrischen Lösungsansätze als auch auf die praktische algorithmische Umsetzbarkeit und Komplexität des Problems.
- Theoretische Grundlagen und graphentheoretische Definitionen des ESTP
- Geometrische Konstruktionsmethoden für kleine Punktemengen (n=3, n=4)
- Analyse der Komplexität und Eigenschaften von Steinertopologien
- Vergleich exakter Algorithmen (Melzak, Smith, Geosteiner)
- Untersuchung heuristischer Verfahren wie der Beasley-Heuristik
Auszug aus dem Buch
5.1.1 Die Funktionsweise des Verfahrens
Der Melzak-Algorithmus ermittelt für eine gegebene Topologie entweder den entsprechenden eindeutigen RMT oder liefert die Information, dass auf der übergebenen Topologie kein solcher existieren kann. Der Algorithmus besteht aus zwei klar trennbaren Phasen, welche nacheinander vollzogen werden. In der ersten Phase, der sogenannten Merging-Phase, wird die Terminalmenge, unter Ausnutzung der Idee aus Bemerkung 5.4, sukzessive reduziert. In jeder Iteration werden zwei zu einem selben Steinerpunkt adjazente Terminale gewählt. Anschließend werden die zwei gewählten Terminale von der Topologie gelöscht und der zugehörige Steinerpunkt auf der Topologie in ein neues Terminal umgewandelt. Die Länge eines jeden um ein Terminal reduzierten Baums mit angepasster Topologie entspricht genau der Länge des Ausgangsbaums mit der ursprünglichen Topologie. Der Pseudocode der Merging-Phase lautet (nach [21] und [19]):
Algorithm 5.2: Der Melzak-Algorithmus: Die Merging-Phase
Data: Eine Terminalmenge und eine zugehörige Topologie.
Result: Der kürzeste Steinerbaum für diese Topologie, sofern existent.
while Es ist mindestens noch ein Steinerpunkt auf der Topologie vorhanden do
Wähle zwei Terminale a und b, welche mit dem gleichen Steinerpunkt p verbunden sind. Sei c der dritte mit p verbundene Punkt. Berechne d1 und d2 als Spitzen der beiden gleichschenkligen Dreiecke über der Kante zwischen den Punkten a und b. Entferne a und b aus der Terminalmenge und von der Topologie.
if c ist ein Terminal then
Wähle von d1 und d2 den Punkt als neues Terminal, für den sich abdi nicht mit dem Dreieck abc überschneidet, und verbinde dieses neue Terminal mit c.
else
Generiere zwei neue Probleme, eines mit d1 und das andere Problem mit d2 als neues Terminal. In beiden Problemen ersetze man den Steinerpunkt p durch das Terminal di.
end
end
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in das euklidische Steinerbaumproblem ein und erläutert dessen praktische Relevanz im Bereich des Netzwerkdesigns.
2 Grundlegende Definitionen: Hier werden die notwendigen graphentheoretischen Grundlagen sowie die spezifische Terminologie für das ESTP definiert.
3 Geometrische Lösungen zum ESTP: Dieses Kapitel behandelt die geometrische Konstruktion von Steinerbäumen für kleine Punktemengen mit drei oder vier Terminalen.
4 Grundlegende Resultate für das ESTP: Es werden die theoretischen Eigenschaften von Steinerbäumen, wie Winkel- und Knotengradbedingungen, sowie die Komplexität des Problems analysiert.
5 Exakte Algorithmen zum ESTP: Dieses Kapitel stellt verschiedene exakte Verfahren zur Lösung des Problems vor, darunter den Melzak-Algorithmus, den Algorithmus von Smith und den Geosteiner-Algorithmus.
6 Der minimale Spannbaum: Der minimale Spannbaum (MST) wird als Alternative definiert und als Näherung für den euklidischen Steinerbaum diskutiert.
7 Heuristiken zum ESTP: Hier werden heuristische Ansätze, insbesondere die Beasley-Heuristik, für die näherungsweise Lösung des ESTP erläutert.
8 Zusammenfassung: Dieses Kapitel bietet einen abschließenden Überblick über die wesentlichen Ergebnisse der Arbeit.
9 Anhang: Der Anhang enthält ergänzendes Material und Visualisierungen zu den Kapiteln.
Schlüsselwörter
Euklidisches Steinerbaumproblem, ESTP, Minimaler Spannbaum, MST, Steinerpunkt, Terminale, Steinertopologie, Melzak-Algorithmus, Geosteiner, NP-Schwere, Beasley-Heuristik, Netzwerkdesign, Optimierung, Geometrische Konstruktion, Knoten-Grad-Bedingung.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt das euklidische Steinerbaumproblem, bei dem eine Menge von Punkten in der Ebene durch Hinzufügen weiterer Punkte so verbunden werden soll, dass die Gesamtlänge der Verbindungen minimiert wird.
Was sind die zentralen Themenfelder?
Zentrale Themen sind die theoretischen Eigenschaften optimaler Steinerbäume, exakte Algorithmen zu deren Berechnung sowie heuristische Verfahren, die bei komplexen Problemen zur Anwendung kommen.
Was ist das primäre Ziel der Forschungsarbeit?
Ziel ist es, ein tiefgreifendes Verständnis für die Struktur von Steinerbäumen zu vermitteln und verschiedene Ansätze zu ihrer exakten und näherungsweisen Bestimmung darzustellen.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit basiert auf einer mathematischen und theoretischen Analyse, ergänzt durch die Vorstellung algorithmischer Lösungsansätze und deren praktische Implementierung mittels MATLAB.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die geometrische Lösungsfindung für kleine Terminalmengen, die mathematische Herleitung von Optimalitätsbedingungen, die Analyse von Algorithmen zur exakten Lösung sowie die Diskussion heuristischer Strategien.
Welche Schlüsselwörter charakterisieren die Arbeit?
ESTP, Steinerbäume, Steinertopologien, NP-Schwere, Melzak-Algorithmus und Beasley-Heuristik sind die prägendsten Begriffe.
Wie unterscheidet sich das Steinerbaumproblem vom minimalen Spannbaum?
Im Gegensatz zum minimalen Spannbaum erlaubt das Steinerbaumproblem das Hinzufügen zusätzlicher Punkte (Steinerpunkte), um die Gesamtlänge des Netzwerks zu verringern.
Warum ist das Problem als NP-schwer eingestuft?
Da die Anzahl der zu untersuchenden Steinertopologien exponentiell mit der Anzahl der Terminale wächst, existiert derzeit kein Algorithmus, der das Problem für alle Instanzen in polynomieller Zeit exakt lösen kann.
- Arbeit zitieren
- Jan Weidner (Autor:in), 2013, Das euklidische Steinerbaumproblem in der Ebene, München, GRIN Verlag, https://www.grin.com/document/372476
