Verfahren zur Wegsuche am Beispiel öffentlicher, innerstädtischer Verkehrsnetze
Nummer: DA-Z13
Autorin: Hedwig Matl
Kurzfassung:
Die vorliegende Diplomarbeit beschäftigt sich mit der minimalen Wegsuche in
komplexen Netzwerken, den so genannten Wegesuch-Algorithmen, mit der
Zielsetzung, unterschiedliche Verfahren zu evaluieren und ihre Anwendung bei
Verkehrsnetzen zu studieren. Zuerst wird ein Überblick über derzeit verwendete
Standardverfahren zur minimalen Wegsuche gegeben. Es werden die verschiedenen Anwendungsgebiete fur die minimale Wegsuche beschrieben und die Bedeutung von Wegesuch-Algorithmen für die Praxis dargelegt. Zum besseren Verständnis wird eine kurze Einführung in Algorithmenkomplexität und Graphentheorie gegeben und es werden Methoden zur Bearbeitung von Graphen behandelt.
Hauptthema der Diplomarbeit ist die Untersuchung von Algorithmen für die
Wegsuche in hierarchische Graphen. Dabei werden typische Einsatzgebiete für eine hierarchische Wegsuche erläutert und unterschiedliche Ansätze zur Erstellung einer Hierarchie untersucht. Anhand eines Softwaredemonstrators wird die Vorgehensweise bei hierarchischen Wegesuch-Algorithmen in Verkehrsnetzen erklärt und veranschaulicht. Der Softwaredemonstrator verwendet einen hierarchischen Algorithmus zur Wegsuche in öffentlichen, innerstädtischen Verkehrsnetzen und bietet eine graphische Oberfläche zur Interaktion. Er ist als persönlicher Assistent konzipiert, der typischerweise auf einem Pocket PC verwendet wird. Der Softwaredemonstrator wurde in der Programmiersprache C# unter Verwendung des .NET Compact Frameworks realisiert.