Grin logo
en de es fr
Shop
GRIN Website
Publish your texts - enjoy our full service for authors
Go to shop › Business economics - Operations Research

Das euklidische Steinerbaumproblem in der Ebene

Title: Das euklidische Steinerbaumproblem in der Ebene

Bachelor Thesis , 2013 , 53 Pages , Grade: 1,3

Autor:in: Jan Weidner (Author)

Business economics - Operations Research
Excerpt & Details   Look inside the ebook
Summary Excerpt Details

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.

Excerpt


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

Zielsetzung und Themenschwerpunkte

Diese Bachelorarbeit befasst sich mit dem euklidischen Steinerbaumproblem (ESTP) in der Ebene. Das Ziel der Arbeit ist es, einen umfassenden Überblick über dieses Problem zu geben, einschließlich seiner Definition, grundlegender Eigenschaften, exakter Lösungsansätze und Heuristiken.

  • Definition und Eigenschaften des euklidischen Steinerbaums
  • Geometrische Lösungen für spezielle Fälle
  • Exakte Algorithmen zur Lösung des ESTP
  • Heuristiken zur Approximation des ESTP
  • Der minimale Spannbaum als Näherungslösung

Zusammenfassung der Kapitel

Die Arbeit beginnt mit einer Einführung in das euklidische Steinerbaumproblem und seiner Bedeutung in der Praxis. Es werden grundlegende Definitionen aus der Graphentheorie und spezifische Terminologien zum ESTP eingeführt.

Kapitel 3 behandelt geometrische Lösungen für das ESTP in einfachen Fällen. Kapitel 4 erörtert wichtige Eigenschaften und Resultate des ESTP, einschließlich der Steinertopologien und der Komplexität des Problems.

Kapitel 5 befasst sich mit exakten Algorithmen zur Lösung des ESTP, insbesondere mit dem Melzak-Algorithmus und dem Algorithmus von Smith. Kapitel 6 untersucht den minimalen Spannbaum als Näherungslösung für den euklidischen Steinerbaum.

Kapitel 7 widmet sich Heuristiken zur Lösung des ESTP, insbesondere der Beasley-Heuristik.

Die Arbeit endet mit einer Zusammenfassung der wichtigsten Ergebnisse und Schlussfolgerungen.

Schlüsselwörter

Euklidisches Steinerbaumproblem, Steinerbaum, Steinerpunkt, Graphentheorie, minimale Spannbäume, exakte Algorithmen, Heuristiken, Approximation, geometrische Lösungen, Komplexität.

Excerpt out of 53 pages  - scroll top

Details

Title
Das euklidische Steinerbaumproblem in der Ebene
College
University of Dortmund  (Fachgebiet Operations Research und Wirtschaftsinformatik)
Grade
1,3
Author
Jan Weidner (Author)
Publication Year
2013
Pages
53
Catalog Number
V372476
ISBN (eBook)
9783668507425
ISBN (Book)
9783668507432
Language
German
Tags
Steinerbaum Topologie Steinerbaumproblem Minimaler Spannbaum Kombinatorische Optimierung Euklidischer Steinerbaum Melzak Algorithmus Minimum Spanning Tree Terminalpunkte Steinertopologie
Product Safety
GRIN Publishing GmbH
Quote paper
Jan Weidner (Author), 2013, Das euklidische Steinerbaumproblem in der Ebene, Munich, GRIN Verlag, https://www.grin.com/document/372476
Look inside the ebook
  • Depending on your browser, you might see this message in place of the failed image.
  • https://cdn.openpublishing.com/images/brand/1/preview_popup_advertising.jpg
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
Excerpt from  53  pages
Grin logo
  • Grin.com
  • Payment & Shipping
  • Contact
  • Privacy
  • Terms
  • Imprint