Praxis der Softwareentwicklung (PSE)

Entwicklung eines Routenplaners

Aufgabenstellung

Ihre Aufgabe ist die Entwicklung eines Routenplanungssystems für den PC. Das System soll über eine graphische Benutzeroberfläche verfügen, über die Anfragen komfortabel an das Programm gestellt werden können. Diese Anfragen sollen von einem von Ihnen implementierten Routingalgorithmus verarbeitet werden, dessen Ergebnisse wiederum die Oberfläche graphisch darstellt.

Es bestehen gewisse Freiheitsgrade beim Entwurf des Systems. So kann Ihr Routenplaner klassisch die schnellste Verbindung zwischen zwei gegebenen Punkten finden, oder z.B. die schönste Wanderstrecke bei benutzerdefinierten Steigungswerten und Streckenlängen berechnen. Zur Kartendarstellung soll eine eigene Renderengine entwickelt werden. Diese und andere Schwerpunkte werden Sie bei Ihrem Projekt selbstständig setzen müssen.

 

Schnelle Routenberechnung

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

  

Teams

Es werden zwei Teams betreut, die beide die gleiche (oben beschriebene) Grundaufgabenstellung bekommen. Die Teams dürfen und sollen unabhängig voneinander ihre Schwerpunkte festlegen.

 

Termine

  • Erstes Treffen: 29.10.13, 14:00 Uhr (Raum 211, Gebäude 50.34)
  • Abgabe Pflichtenheft: 22.10.2013 um 23:59 Uhr
  • Abgabe Entwurf:20.12.2013 um 23:59
  • Implementierung bis:31.01.2014 um 23:59
  • Abnahme:
  • Abschlusspräsentation:

 

Materialien