Programm um einen Fahrplan auszulesen

[auxilium]

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.


Wie sollte ich am besten vorgehen?

Ich tippe hier sind viele kompetente Java Programmierer, die mir helfen können.

 

[martram]

Letztendlich ist das ja keine Java-, sondern eine Algorithmenfrage. :wink:

Wenn du wirklich die zeitlich (oder entfernungstechnisch) garantiert beste Lösung haben willst, wirst du wohl wirklich alle Knoten untereinander überprüfen müssen. Eine mögliche, aber auch nicht so viel bringende Optimierung ist es wohl, schlechtere Lösungen (bereits absehbar, noch nicht vollständig!) als die bisher gefundene beste zu verwerfen.

Ansonsten gefällt mir z.B. dein Ansatz für die Praxis schon ganz gut. Du könntest den Bahnhöfen eine Gewichtung geben und z.B. erstmal nur zu Bahnöfen mit großen Wertigkeiten "fahren". Desto näher man an das Ziel kommt (z.B. Luftlinie), desto kleiner werden die notwendigen Gewichtungen, um überprüft zu werden.

Für die weitere Lektüre, halte dich z.B. an die folgenden Algorithmen: A*(-Algorithmus), Bellman-Ford oder Dijkstra-Algorithmus.

 

[Hanz53]

Hi,
unser info prof hat mal was für schulen erstellet .... da wird der algo. erklärt
http://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm

 

[auxilium]

hey habe das nun mittels arraylisten und 2 Klassen: Knoten und Verbindung mal umgesetzt.
Allerdings bekomme ich jetzt schon einen OutofMemoryError und ich möchte nur die Verbindung eines Bahnhofs ( Knoten) ausgeben.

Hier mal der Code:


Routenberechnung

import java.util.ArrayList;
import java.util.Scanner;

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

   public static int liesEineZahlEin()
   {
      boolean ok = false;
      int rueckgabewert = 0;

      while (!ok)
      {
         try
         {
            rueckgabewert = new Scanner(System.in).nextInt();
            ok = true;
         }
         catch (Exception e)
         {
            System.out.println("Keine Zahl eingegeben!");
            ok = false;
         }
      }
      return rueckgabewert;
   }

   public static String liesEineZeichenketteEin()
   {
      boolean ok = false;
      String rueckgabe = "";

      while (!ok)
      {
         try
         {
            rueckgabe = new Scanner(System.in).next();
            ok = true;
         }
         catch (Exception e)
         {
            System.out.println("Kann Text nicht lesen!");
            ok = false;
         }
      }

      return rueckgabe;
   }

   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");

      k1.addKinderknoten(k2);

      k2.addKinderknoten(k1);
      k2.addKinderknoten(k3);
      k2.addKinderknoten(k9);

      k3.addKinderknoten(k2);
      k3.addKinderknoten(k4);
      k3.addKinderknoten(k9);

      k4.addKinderknoten(k3);
      k4.addKinderknoten(k5);
      k4.addKinderknoten(k7);
      k4.addKinderknoten(k9);

      k5.addKinderknoten(k4);
      k5.addKinderknoten(k6);
      k5.addKinderknoten(k7);

      k6.addKinderknoten(k5);
      k6.addKinderknoten(k7);

      k7.addKinderknoten(k4);
      k7.addKinderknoten(k5);
      k7.addKinderknoten(k6);
      k7.addKinderknoten(k8);

      k8.addKinderknoten(k7);
      k8.addKinderknoten(k9);

      k9.addKinderknoten(k2);
      k9.addKinderknoten(k3);
      k9.addKinderknoten(k8);

      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[5];
     test[0] = k2;
     test[1] = k3;
     test[2] = k4;
     test[3] = k5;
     test[4] = k6;
    
      
     Verbindung v1 = new Verbindung();
     v1.addStationen(test);
     
     k1.addVerbindung(v1);
     

   }

   public static void main(String args[])
   {
      initialisiereKnoten();
      haltestellen.get(0).gibVerbindungenaus();

     
   }
}

Knoten

import java.util.ArrayList;

	public class Knoten
	{
	   private String            name;

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

	   private boolean            besucht         = false;

	   public Knoten(String name)
	   {
	      this.name = name;
	   }
	   
	   public String getName()
	   {
	      return name;
	   }
	   
	   public void addKinderknoten(Knoten kind)
	   {
	      kinderknoten.add(kind);
	   }
	   
	   public void addVerbindung(Verbindung v){
		   verbindungen.add(v);
	   }
	   
	   public void gibVerbindungenaus(){
		   for (Verbindung verb : verbindungen){
			   System.out.println();
			   verb.gibStationenaus();
		   }
	   }
	   
	   public void gibDeineKindKnotenAus()
	   {
	      for (Knoten kind : kinderknoten)
	      {
	         System.out.println(kind.getName());
	      }
	   }

	   
	   
	   
	   
	   
	   public int gibRouteAus(Knoten ziel, int schritte)
	   {
	      if(besucht)
	      {
	         return -1;
	      }
	      
	      System.out.println("Besuche " + name);
	      besucht = true;
	      
	      if(ziel.equals(this))
	      {
	         System.out.println("Ziel " + name + " erreicht");
	         return schritte;
	      }

	      schritte = schritte+1;
	      
	      for (Knoten kind : kinderknoten)
	      {
	         int weg = kind.gibRouteAus(ziel, schritte);
	         
	         if(weg >= 0)
	         {
	            return weg;
	         }
	      }

	      return -1;
	   }
	}

und Verbindungen

import java.util.ArrayList;

public class Verbindung {

	String verbname;
	boolean frei = true;

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

	public void addStationen(Knoten[] stationen) {
		int i = 0;
		while (i <= stationen.length - 1) {
			verb.add(stationen[i]);
		}
		
	
		}

	
	public void gibStationenaus(){
		for (Knoten help: verb){
			help.getName();
		}
	}
}

 

[auxilium]

fehler gefunden, hab i nicht hochgezählt bei addStationen() von der Verbindungs Klasse.