kürzeste Route ausgeben!?

[Kiki1988]

Hallo zusammen,

Ich sitze nun schon ziemlich lange an einer Aufgabe und komme überhaupt nicht weiter.

Die Aufgabe ist folgende:

Eine Fluggesellschaft, die mehrere Flugverbindungen zwischen verschiedenen europäischen Städten unterhalt, beauftragt Sie, einen Routenplaner zu entwickeln. Implementieren Sie hierfür eine Klasse RoutePlanner mit der Methode public static void shortestRoute(Airport from, Airport to, int changes), die rekursiv die kürzeste Flugroute mit höchstens changes Umstiegen vom Flughafen from zum Flughafen to ermittelt und auf dem Bildschirm ausgibt.

Zur Lösung haben wir 4 Klassen gegeben (Aufgabe20.zip)

Meine Idee ist die Flugverbindungen von beiden Flughäfen zu überprüfen ob Übereinstimmungen vorhanden sind, wenn ja ist man ja fertig.. dann ist die Route von Startflughafen --> Übereinstimmung --> Ziel

und wenn keine Übereinstimmungen vorhanden sind, dann auf Übereinstimmungen der Flughäfen der Flugverbindung prüfen usw.

Dann erhalte ich mehrere Verbindungen und bei denen müsste man dann schauen, welche die kürzeste ist.

Ist das so umsetzbar? Oder kann mir jemand auf die Sprünge helfen?

Weiß grad überhaupt nicht weiter.

Danke schonmal

Lg Kiki

Aufgabe20.zip

[flashpixx]

Hallo,

Das Problem gehört in die TSP Problematik und ist "NP-hart", die Einschränkung die kürzeste / günstigste / usw Route sind nur zusätzliche Gewichtungen. Mit jedem neuen "Flughafen" steigt die Zahl der Lösungsmöglichkeiten exponentiell.

Eine "gute" Lösung ist, nach dem Nearest-Neighbor-Prinzip die nächste Station auszuwählen.

HTH Phil

[Kiki1988]

Es scheitert schon an der Umsetzung der einfachsten Sachen z.B. wie ich einfach nur einen Zielflughafen von einem bekannten Flughafen ausgeben kann. Ich müsste ja eigentlich über die Mehtode getConnections() an irgendeiner Stelle einen Flughafen erhalten

weil dieser Arrayeintrag ja eine FlightConnection ist habe ich dann noch die Methode getOtherAirport(airport ...) hinten dran geklatscht und meine Ausgabe? LEER

Ich habe erst vor 6 Wochen zum ersten Mal in Java programmiert, vorher nur leichte Sachen in Delphi ^^

Wie setz ich das denn um, dass der nähste Flughafen auswählt wird?

bzw. wie kann ich überhaupt auf diese Flüghafen zugreifen?

LG

[Cadpax]

Allgemeiner in der Informatik auch als Pathfinding bekannt.

Dazu gibt es aber logische Tutorials:

Zum beispiel eins.

[flashpixx]

Hallo,

Es scheitert schon an der Umsetzung der einfachsten Sachen z.B. wie ich einfach nur einen Zielflughafen von einem bekannten Flughafen ausgeben kann.

Das macht doch keinen Sinn. Ein Flughafen enthält keinen Zielflughafen. Eine Route enthält einen Start- und einen Zielflughafen (und weitere, die Du berechnen sollst)

Noch ein paar Sachen zu Deinem Code:

• Benutze keine Arrays sondern Listen, da sie dynamisch sind und Du Elemente hinzufügen kannst, ohne immer alles zu kopieren!
  
• Überlege Dir, wie Du Deine Klassen organisierst: Ein Flughafen ist ein Punkt in Deinem Graph (Weg), eine Route hat mind. Start- und Endpunkt und ggf. Punkte dazwischen
  
• Deine Strecke (Kanten des Graph) sind Gewichtet, nach Deinen Anforderungen (kurz, günstig usw), d.h. Du musst diese Information für Deine Berechnung auch in Deiner Klasse vorhalten
  
• Für die Berechnung wurde einige Ansätze genannt
  
• Du musst Dir auch Gedanken machen, was passiert, wenn keine Route gefunden werden kann
  

HTH Phil

[Kiki1988]

Stimmt so wie ich das geschrieben habe macht das keinen Sinn.

Was ich meinte war, dass jeder Flughafen bestimmte Verbindungen (eben diese FlightConnections) zu anderen Flughäfen hat. Was ich auslesen möchte sind diese ganzen Flughäfen, wo ein Flugzeug von einem bestimmten Flughafen aus hinflilegen kann.

Die Klassen die ich hier rein gestellt habe sind uns so vorgegeben. Listen haben wir erst in der letzen Vorlesung besprochen, daher kommen die hier denke ich noch nicht vor.

Danke für eure Tipps, werde mal versuchen das umzusetzen.

[flashpixx]

Hallo,

bitte versuche mal Deine Klassen und die Zusammenhänge zu verstehen! Die Klassen sind zwar nicht so, wie ich es gedacht hätte, aber der Gedankengang ist daraus erkennbar:

• Die Klasse "Airport" ist nur ein Punkt mit einem Namen - Knoten im Graph
  
• Die Klasse "FlightConnection" ist ein Weg von einem zum anderen Flughafen mit Gewichtung (Distanz) - entspricht der gewichteten gerichteten Kante mit den dazugehörigen Knoten (ein Flug von A nach B ist nicht zwingend auch B nach A, deswegen gerichteter Graph)
  
• Die "Route" Klasse, soll dann der Weg durch den Graph sein
  

Natürlich musst Du auch den bestehende Code so anpassen, dass Du die Daten verarbeiten kannst. Ich gehe natürlich davon aus, dass Du weißt, wie das OOP Konzept aussieht und wie Du entsprechende Klassen konstruierst / veränderst

Phil