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:
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
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: