Home | english  | Impressum | Sitemap | KIT

Software-Entwicklung 13

Software-Entwicklung 13
Typ: Praktikum Links:
Lehrstuhl: Prof. Dr. Peter Sanders
Ort:

nach Vereinbarung

Zeit: nach Vereinbarung
Dozent:

Peter Sanders
Veit Batz
Dennis Luxen

SWS: 4
LVNr.: 24033
Prüfung:

ja

Beschreibung

Aufgabenstellung 

Ihre Aufgabe ist die Entwicklung eines Routenplanungssystems für Radfahrer, das auf dem PC läuft. Das System soll in der Lage sein für gegebenen Start- und Zielort optimale Routen zu berechnen. Weiterhin soll das System über eine graphische Benutzeroberfläche verfügen, über die einerseits Routenanfragen komfortabel an das Programm gestellt werden können, und die andererseits das Straßennetz und die berechnete Routen graphisch darstellt.

 

Schnelle Routenberechnung

Das Standardverfahren zur Routenberechung ist der klassische Algorithmus von Dijkstra. Dieser arbeitet für größere Graphen (wie z.B. das deutsche Straßennetz) aber eigentlich zu langsam. Hier helfen sogenannte Speedup-Techniken, die Dijkstras Algorithmus zum Teil um vierstellige Faktoren beschleunigen. Für Ihr Projekt empfehlen wir Ihnen die Verwendung von Arc-Flags, einer einfachen aber recht effektiven Speedup-Technik.

Termine

Das erste Treffen findet am Dienstag, den 25. Oktober 2011 um 17h30 in Raum 131 im Informatikgebäude 50.34 statt.

Materialien