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
Literaturverzeichnis
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.