Bachelorarbeit, 2013
53 Seiten, Note: 1,3
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
Der GRIN Verlag hat sich seit 1998 auf die Veröffentlichung akademischer eBooks und Bücher spezialisiert. Der GRIN Verlag steht damit als erstes Unternehmen für User Generated Quality Content. Die Verlagsseiten GRIN.com, Hausarbeiten.de und Diplomarbeiten24 bieten für Hochschullehrer, Absolventen und Studenten die ideale Plattform, wissenschaftliche Texte wie Hausarbeiten, Referate, Bachelorarbeiten, Masterarbeiten, Diplomarbeiten, Dissertationen und wissenschaftliche Aufsätze einem breiten Publikum zu präsentieren.
Kostenfreie Veröffentlichung: Hausarbeit, Bachelorarbeit, Diplomarbeit, Dissertation, Masterarbeit, Interpretation oder Referat jetzt veröffentlichen!
Kommentare