Rekursion beim Fahrplan

wittkowsky

Grünschnabel
Hallo,

ich möchte gerne einen Routenplaner für Bahnverbindungen auszulesen programmieren.
Leider hapert es noch ein bisschen an der Umsetzung, grundsätzliche Gedanken habe ich mir bereits gemacht, aber vllt finde ich hier ja noch weiter Inspirationen bzw. werde eines besseren belehrt.

Also bisher habe ich mich mit dem U-Bahn Algorithmus beschäftigt, bei dem ich jedem Knotenpunkt( U-Bahnstation) die U-Bahnstationen angegeben habe(Kindknoten) mit den die jeweilige Station direkt verbunden ist.
Nun möchte ich das in der Form erweitern, dass ich die Knotenpunkte beibehalte und jedem Knotenpunkt mehrere Verbindungen zuweise, die eine Liste von Stationen enthält, die von der Station erreichbar sind.
Im Prinzip sollte das ja funktionieren wie das U-Bahn Problem, nur dass ich jetzt nicht die Kindknoten überprüfe, sondern die Verbindungen, ob ein bestimmter Bahnhof in der verbindung ist , ansonsten die Verbindungen des nächsten Bahnhofs und so weiter.

Nur über mehrere Stationen kann das ziemlich komplex werden:

Beispiel:

Bahnhöfe:
München
Stuttgart
Frankfurt
Köln
Nürnberg
Hamburg
Kiel
Paris
Rom


sagen wir mal München fährt:

München - Hamburg - Rom - Paris


München - Stuttgart - Rom




Stuggart fährt:
Stuttgart - Rom - Kiel
Stuttgart - Köln -Rom

und Kiel fährt:

Kiel - Rom - Paris
Kiel- Frankfurt

Und ich steige in München an und möchte nach Frankfurt.

Da muss ich ja im Prinzip jeden Teilbahnhof auf seine Unterverbindungen überprüfen, was doch erheblicher Rechenaufwand sein dürfte.

Im einfachen Beispiel würde ich erstmal von München gucken ob eine Direktverbindung besteht und dann die erste Verbindung überprüfen : München - Hamburg - etc

Dabei muss ich im Prinzip ja jeden Bahnhof auf seine Unterstationen überprüfen und deren Unterstationen und deren Unterstationen und so weiter.....,

und dann käme ich erst an die 2. Verbindung
und dann würde ich zum Glück sehen, dass man von Stuttgart nach Kiel fahren kann.

und von Kiel nach Frankfurt.


Muss ich so vorgehen oder kann man das vereinfachen?
In der Praxis kann ich mir vorstellen wird wohl davon ausgegangen, dass es Hauptbahnhofe gibt, die bestimmte Bereiche abdecken, z.b. München für Bayern , ohne dass ich in Baden Würtemberg jeden Bahnhof durchsucht haben muss, ob da eine Verbindung zu einem kleinen Ort in Bayern ist.


Also ich habe da schon mal was umgesetzt:

Code:
import java.util.ArrayList;
import Prog1Tools.IOTools;

public class Routenberechnung
{
static ArrayList<Knoten> haltestellen = new ArrayList<Knoten>();

 

public static void initialisiereKnoten()
{
Knoten k1 = new Knoten("Trier");
Knoten k2 = new Knoten("Stuttgart");
Knoten k3 = new Knoten("Ulm");
Knoten k4 = new Knoten("Mainz");
Knoten k5 = new Knoten("Koblenz");
Knoten k6 = new Knoten("Hamburg");
Knoten k7 = new Knoten("Ravensburg");
Knoten k8 = new Knoten("Karlsruhe");
Knoten k9 = new Knoten("Augsburg");


haltestellen.add(k1);
haltestellen.add(k2);
haltestellen.add(k3);
haltestellen.add(k4);
haltestellen.add(k5);
haltestellen.add(k6);
haltestellen.add(k7);
haltestellen.add(k8);
haltestellen.add(k9);

Knoten[] test = new Knoten[2];
test[0] = k2;
test[1] = k3;

 

Knoten[] test2 = new Knoten[2];
test2[0] = k4;
test2[1] = k5;

Knoten[] test3 = new Knoten[1];
test3[0] = k9;

Knoten[] test4 = new Knoten[1];
test4[0] = k8;

Knoten[] test5 = new Knoten[2];
test5[0] = k4;
test5[1] = k6;


Verbindung.verbindungmachen(k1, test, "Verbindung 1");
Verbindung.verbindungmachen(k1, test2, "Verbindung 2");
Verbindung.verbindungmachen(k3, test3, "Verbindung 3");
Verbindung.verbindungmachen(k9, test4, "Verbindung 4");
Verbindung.verbindungmachen(k9, test5, "Verbindung 5 ");

 

 


}

public static void main(String args[])
{
initialisiereKnoten();

System.out.println("Sie wollen nach "+haltestellen.get(5).getName());
haltestellen.get(0).testeVerbindung(haltestellen.get(5));

haltestellen.get(0).getVerbindungen().get(0).getVerb().get(1);

 

}
}


Code:
import java.util.ArrayList;

public class Knoten {

private String name;

private ArrayList<Verbindung> verbindungen = new ArrayList<Verbindung>();

private boolean besucht = false;

public Knoten(String name) {

this.name = name;

}

public String getName() {

return name;

}

public ArrayList<Verbindung> getVerbindungen() {

return verbindungen;

}

public void setVerbindungen(ArrayList<Verbindung> verbindungen) {

this.verbindungen = verbindungen;

}

public void setName(String name) {

this.name = name;

}

public void addVerbindung(Verbindung v) {

verbindungen.add(v);

}

public void gibVerbindungenaus() {

for (Verbindung verb : verbindungen) {

System.out.println(verb.getVerbname() + " :");

System.out.println();

verb.gibStationenaus();

System.out.println();

}

}

public boolean testeVerbindung(Knoten ziel) {

if (besucht) {

return false;

}

besucht = true;

// System.out.println("Sie fahren nach "+this.getName());

int i = 0;

while (i < verbindungen.size()) {

int i2 = 0;

while (i2 < verbindungen.get(i).getVerb().size()) {

if (verbindungen.get(i).getVerb().get(i2).equals(ziel)) {

System.out.println("Also Benutzen Sie bitte "

+ verbindungen.get(i).getVerbname());

if (i2 > 0) {

System.out.println("Sie fahren über");

}

int i3 = 0;

while (i3 < i2) {

System.out.print(verbindungen.get(i).getVerb().get(i3)

.getName()

+ " ");

i3++;

}

return true;

}

i2++;

}

i++;

}

i = 0;

while (i < verbindungen.size()) {

int i2 = 0;

while (i2 < verbindungen.get(i).getVerb().size()) {

if (verbindungen.get(i).getVerb().get(i2).testeVerbindung(ziel)) {

System.out.println("Fahre "

+ verbindungen.get(i).getVerbname()+" ueber");

int i4 =0;

while(i4<i2){

System.out.print(" "+verbindungen.get(i).getVerb().get(i2).getName());

i4++;

}

return true;

}

i2++;

}

i++;

}

return false;

}

}


Code:
import java.util.ArrayList;

public class Verbindung {

public Verbindung(String verbname) {

this.verbname = verbname;

}

private String verbname;

private boolean frei = true;

private ArrayList<Knoten> verb = new ArrayList<Knoten>();

public void addStationen(Knoten stationen) {

verb.add(stationen);

}

public static void verbindungmachen(Knoten k, Knoten[] verb, String name) {

Verbindung verbin = new Verbindung(name);

int i = 0;

while (i < verb.length) {

verbin.addStationen(verb[i]);

i++;

}

k.addVerbindung(verbin);

}

public void gibStationenaus() {

for (Knoten help : verb) {

System.out.println(help.getName());

}

}

public String getVerbname() {

return verbname;

}

public void setVerbname(String verbname) {

this.verbname = verbname;

}

public boolean isFrei() {

return frei;

}

public void setFrei(boolean frei) {

this.frei = frei;

}

public ArrayList<Knoten> getVerb() {

return verb;

}

public void setVerb(ArrayList<Knoten> verb) {

this.verb = verb;

}

}


Also ich weise jedem Knoten Verbindungen zu, die aus Knoten bestehen.

Jetzt funktioniert die Abfrage soweit durch die Rekursion, nur gibt er mir die Stationen in falscher Reihenfolge aus.

Wie kann man das anders umsetzen oder verbessern?

Sie wollen nach Hamburg
Also Benutzen Sie bitte Verbindung 5
Sie fahren über
Mainz Fahre Verbindung 3 ueber
Fahre Verbindung 1 ueber
Ulm

Das ist die Ausgabe
 
Zuletzt bearbeitet:
Ich würde wiefolgt vorgehen:

1. Die Einzelknoten tatsächlich aneinanderhängen, so dass ein richtiges Geflecht aller Verbindungen entsteht.
2. Dieses Geflecht in einen binären Suchbaum umwandeln, als Wurzel-Knoten dein Startpunkt (im Beispiel München).
3. Wenn du jetzt nach Frankfurt willst, musst du nur noch den Suchbaum traversieren und kannst alle Zwischenstationen bis zum Zielbahnhof - so vorhanden - ausgeben.
4. Wenn du den Baum richtig aufgebaut hast, bekommst du so auch verschiedene Wege zum Ziel - und kannst z.B. den kürzesten oder den schnellsten mit ausgeben.
 
Wahrscheinlich ist es am einfachsten das ganze in Prolog zu schreiben und Prolog aus Java heraus anzusprechen. (Zumindest wenn man sich ein wenig mit Prolog auskennt ;))
 
Prolog ist ne schöne Variante um die Zuordnung zu finden.
Wenn du dann weitere Daten benötigst wirds nur leider schwer, die an die String-Ausgabe ranzuknüpfen - wobei, möglich ist es :)
 
Das ist mehr oder weniger, was ein einfacher Routenplaner macht.

Man flutet das Netz in alle Richtungen bis man am Ziel ist.

Normalerweise sagt man aber....wenn man sich zu weit vom Ziel entfernt statt nähert, vergisst man diese Route.

Da gibts auch ein Allgorithmus der so geht...aber mir fällt gerade der Name nicht ein.

Aber das ist im Prinzip schon höhere Informatik würd ich sagen.
 
Natürlich kannst du zu jeder Haltestelle noch die Entfernung zu allen anderen speichern.
Wenn dann Umwege über zu viele Haltestellen eine maximale Entfernung überschreiten, dann kannst du die Traversion abbrechen.
 
A* heißt der Algorithmus... Kannst ja mal nach suchen wenn du da noch Infos zu brauchst. In dem Fall wären halt Entfernung und/oder Preis die Faktoren die in die Suche einzubeziehen werden um ein Abbruchkriterium für einen gewählten Pfad zu haben.
 
1. Die Einzelknoten tatsächlich aneinanderhängen, so dass ein richtiges Geflecht aller Verbindungen entsteht.

Wie meinst du das genau, shutdown?

Meinst du den U-Bahn Algorithmus, bei dem ich jeden Knoten mit Kindknoten im Prinzip verbinde?

Also im Prinzip nur sage, Knoten a ist mit Knoten b verbunden.

Das Problem war da bei mir, dass es Verbindungen geben könnten, wo Knoten b überfahren wird, also Knoten a nicht mit Knoten b verbunden ist.
 
Nein so meinte ich das nicht.

Du hast doch derzeit einzelne Stränge

Strang 1: München - Kiel - Frankfurt
Strang 2: Stuttgart - Kiel - Köln
Strang 3: Aachen - Köln - Berlin

Jetzt mach ein Netz daraus.
Da hast du jetzt zwei Möglichkeiten:

Entweder du duplizierst alle Einträge eines anderen Stranges am Strang:

Aus Strang 1 wird so z.B.:
Code:
Strang 1:
München 
 -> Kiel 
      -> Frankfurt
      -> Stuttgart
      -> Köln
          -> Aachen
          -> Berlin


Oder du machst tatsächlich ein Netz daraus - und jetzt bin ich mal gespannt ob ich das zweidimensional darstellen kann :)

Code:
München ->                -> Frankfurt
                      Kiel                          -> Achen
Stuttgart ->                 -> Köln
                                                     -> Berlin


Rekursiv zu verarbeiten ist erst einmal die erste Struktur einfacher.
Geringere Datenmenge bietet die zweite Struktur - und wenn du dir in diesem Netz wie schon beschríeben die Startbahnhof als Wurzel eines binären Suchbaums nimmst und den Baum dann so ordnest, hast du auch hier die Möglichkeit schnell und einfach zu suchen. Natürlich benötigt das Aufbauen des Suchbaums auch wieder Zeit.
 
Ok, wie es mir scheint, ist aber in dem Baum keine klare Richtung vorgegeben, sprich es wäre genauso möglich von Köln nach Stuttgart zu fahren , oder?

Weil das will ich eigentlich nicht, weshalb ich leider auch an der umsetzung eines baums verzweifelt bin.

Will nur, dass man von münchen nach frankfurt über köln fahren kann, aber von frankfurt soll es nicht automatisch dann eine Verbindung nach München zurück geben.
 
Zurück