Aufgabe

Entwickeln Sie eine Anwendung, die es erlaubt, die kürzeste Strecke zwischen zwei Haltestellen eines regionalen Verkehrsnetzes mithilfe des A*-Algorithmus‘ zu ermitteln. Hierbei werden keine Umsteigezeiten oder Geschwindigkeitsbegrenzungen berücksichtigt, es geht nur um den räumlich kürzesten Weg.

Der A*-Algorithmus ist ein Suchalgorithmus, der es erlaubt, den kürzesten Pfad zwischen zwei Knoten über die Knoten verbindende Kanten eines Graphen zu ermitteln. Die Knoten aus dem Modell entsprechen in diesem Fall den Haltestellen, die durch Kanten verbunden sind. Diese Kanten sind unterschiedlich gewichtet; längere Strecken haben höhere Kantengewichte.

Für diese Aufgabe bietet sich eine graphische Benutzeroberfläche an, beispielsweise um Start- und Zielstation festzulegen und um den resultierenden Pfad graphisch zu visualisieren.

 

Hinweise

Offizielle Angaben vom VBB zu den Haltestellen und Linien (inklusive Koordinaten) im CSV-Format: http://daten.berlin.de/kategorie/verkehr
(CSV = Comma Separated Values)

A*-Algorithmus: http://de.wikipedia.org/wiki/A*-Algorithmus
Dijkstra-Algorithmus als denkbare Alternative: http://de.wikipedia.org/wiki/Dijkstra-Algorithmus

 

Abgabe

Geben Sie ein .tgz-Archiv ab, welches alle Quelltexte Ihres Navigationsprogramms enthält. Darüber hinaus muss eine Datei README im Archiv enthalten sein, die beschreibt, welche Ausbaustufe sie implementiert haben und wie das Programm zu starten ist (Name der main-Klasse, Parameter etc.)