Bibliograph. Daten | Vollmer, Peter: Beschleunigte Berechnung von ressourcenbeschränkten kürzesten Wegen. Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 19 (2013). 37 Seiten, deutsch.
|
CR-Klassif. | G.2.2 (Discrete Mathematics Graph Theory) G.1.6 (Numerical Analysis Optimization)
|
Kurzfassung | Die Lösung NP-schwerer Probleme wie die ressourcenbeschränkten kürzesten Wege Berechnungen ist zur Zeit exakt nicht in akzeptabler Zeit möglich. Bisher lassen sich akzeptable Lösungen nur durch Abstriche im Hinblick auf den optimalen Pfad und lange Berechnungszeiten finden. In dieser Arbeit behandeln wir, wie durch Vorberechnung einer Contraction Hierarchy eine Beschleunigung einer Lösungsheuristik für ressourcenbeschränkte kürzeste Wege Berechnungen erreicht werden kann. Dazu haben wir ein Werkzeug erstellt, mit dem man die Vorberechnung vornehmen kann. Anschließend wurde auf den erstellten CH-Graphen getestet, wie erfolgreich die Beschleunigung ist. In unseren Messung wir, dass sich die Antwortzeiten um den Faktor 141-248 beschleunigen lassen.
|
Volltext und andere Links | PDF (489158 Bytes)
|
Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik
|
Betreuer | Storandt, Sabine |
Eingabedatum | 14. März 2013 |
---|