Visualisierung der Arbeitsweise von maximalen Fluss Algorithmen auf grossen Graphen (eBook)

Michael Balsfulland (Autor)

eBook Download: PDF

2003 | 1., Auflage
53 Seiten
GRIN Verlag
978-3-638-18718-3 (ISBN)

Infos

Diplomarbeit aus dem Jahr 2002 im Fachbereich Informatik - Programmierung, Note: gut, Universität Paderborn (FB Informatik), Sprache: Deutsch

---

Einleitung
Das Ziel meiner Diplomarbeit ist es, die Arbeitsweise von maximalen Fluß-Algorithmen zu visualisieren und zu veranschaulichen.
Folgendes Beispiel soll zeigen, daß solche Probleme auch in der Praxis relevant sind:

Ein Unternehmen transportiert Waren von einer Produktionsstätte zu einem Distributionszentrum. Es werden dafür Transportunternehmen beauftragt, die feste planmäßige Routen fahren und die maximale Kapazitäten transportieren können.
Es stellt sich nun sowohl die Frage, wie die Menge der transportierten Güter maximiert werden kann als auch die Frage, wieviele Fahrzeuge/h durch eine Stadt mit vorgegebenen Straßenkapazitäten maximal gelangen können.
In der Informatik sind solche Probleme als maximale Fluß Probleme auf gerichteten gewichteten Graphen bekannt.
Bei dem Studium von Algorithmen, die zur Lösung von maximalen Fluß Problemen bekannt sind, entstand die Idee, solche Algorithmen grafisch animiert darzustellen. Bei der Suche nach schon fertigen Programmen, die diese Idee verwirklichen, habe ich einige gefunden, die aber nur eine "nahe“ Sicht auf einem Graphen animieren, um die Funktionsweise im Detail zu zeigen.
Das Ziel meiner Diplomarbeit ist es dagegen, eine weiter entfernte Sicht auf Graphen und Algorithmen zu realisieren, um deren Verhalten zu visualisieren.
Um dieses umzusetzen war es nötig, Visualisierungstechniken und Verfahren zu finden und auszuwählen, die das Ziel einer möglichst expressiven und effektiven Visualisierung erreichen lassen.
Dabei wird zuerst ein Graph-Generator entwickelt, mit dem es ermöglicht werden soll, verschiedene Klassen von Graphen zu generieren. Auf diesen verschiedenartigen Graphen sollen dann exemplarisch zwei Algorithmen animiert werden können. Dies wird im zweiten Teil der Arbeit realisiert werden.
Außerdem war es bei der Darstellung von großen Graphen nötig, durch geeignete Verfahren das Problem des ”zu kleinen Bildschirms“ zu lösen.
Die Intention der Arbeit ist nicht die Implementierung eines möglichst effizienten, schnellen Algorithmus, sondern die Visualisierung der Arbeitsweise der Algorithmen. Die dabei von mir realisierte Software kann und sollte auch insbesondere zu Lehrzwecken eingesetzt werden, um Studierenden einen sehr anschaulichen Zugang zu diesem komplexen Thema zu ermöglichen.
Bei den beiden Implementierungen handelt es sich um zwei unterschiedliche Ansätze zum Lösen des maximalen Fluß Problems.

Produkt-Details

• Erscheint lt. Verlag: 24.4.2003
• Verlagsort: München
• Sprache: deutsch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Schlagworte: Algorithmen • Arbeitsweise • Fluss • Graphen • Visualisierung
• ISBN-10: 3-638-18718-7 / 3638187187
• ISBN-13: 978-3-638-18718-3 / 9783638187183