Rekursions Probleme / frage

[Darnok]

Hallo,
Ich habe momentan die Aufgabe in einem Flug System wo es einzelne Flüge von A nach B gibt etwas zu schreiben was auch alle Routen ausgeben kann die zb. Von A nach C Nach D Nach B sind also mehre flughäfen mit mehreren verbindungen (gerichtete flüge).
Nun erinnert mich dies stark an Knoten und Kanten aus dem Informatik Unterricht.

Ich hatte jetzt die idee dieses problem rekursiev anzugehen stoße aber immer wieder auf das problem das beim aufrufen einer methode ja sich herrausstellen kann das es mehre wege gibt wie es weiter gehen kann und ich jeden pfad verfolgen muss. Jetzt habe ich noch nicht alzuviel erfahrung mit rekursion und bin mir unsicher wie man sowas am besten löst.
Mein Problem ist das ich nicht ganz verstehe wie ich damit umgehen soll wenn ich plötzlich wieder mehrere Wege finde und wie ich das dann gescheit weiter verfolge da sich dann ja mehrere routen bilden und ich nicht weiß wie ich das gut Speicher.

Hoffe es war verständlich genug.
Vielen dank Schonmal

 

[Oneixee5]

Suche mal danach im Netz:
Das Travelling Salesman Problem ist ein kombinatorisches Optimierungsproblem. Ein Händler soll eine Anzahl von Städten besuchen, wobei jede Stadt nur einmal besucht werden soll, und am Ende zu seinem Ausgangspunkt zurückkehren. Die Aufgabe besteht darin, die kürzeste mögliche Route zu finden.
Oder: https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

 

[8u3631984]

Hallo.
Also ich verstehe die Aufgabe etwas anders :
Ich vertehe es so, dass du nach Eingabe einer Verbindug ( A -> B) auch weitere Verbindundungen von A -> C oder B -> D oder E -> A.

Wie sieht denn dein Datenmodell aus. Also wie speicherst du die Flugdaten ?

 

[MarvinsDepression]

Ich denke, Backtracking wäre eine geeignete Vorgehensweise. Die läßt sich auch schön rekursiv umsetzen, weil in der Regel ein eh Stack verwendet wird.

in Pseudocode sähe eine primitive Lösung in etwa so aus:

rekusion(pfad, aktuellerknoten, zielKnoten) : wahrheitswert
    aktuellerKnoten an pfad anhängen
    
    wenn aktuellerKnoten gleich zielKnoten : wahr zurückgeben
    
    für alle nächsterKnoten aus alleDirektErreichbareKnoten :
        wenn nächsterKnoten NICHT im pfad enthalten ist :
            wenn rekursion(pfad, nächsterKnoten, zielknoten) wahr ist : wahr zurückgeben
    
    aktuellerKnoten aus pfad entfernen
    fasch zurückgeben
rekursion ende

Du musst dir halt noch überlegen, wie du die Knoten und Kanten in Klassedefinitionen umsetzt.

 

[Darnok]

Danke habe es inzwischen anders gelöst ohne rekursion
trotzdem vielen dank für die hilfe