[Java] OutofMemory Error bei Routenplaner

Dippen · 17 Februar 2008

Hi,
bin gerade dabei einen Routenplaner für Bahnverbindungen zu erstellen.
Dabei gehe ich davon aus, dass jeder Bahnhof ein Knoten ist und über Verbindungen verfügt, die von dem Bahnhof angefahren werden.

Habe mich dabei zuerst am U-Bahn Algorithmus orientiert und jedem Knoten erst einmal Kindknoten zugewiesen.
Jetzt wirds wie o.g. erweitert und Verbindungen zugewiesen.
Habe dazu 2 Klassen erstellt: Knoten und Verbindungen:

Code:

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

     
   }
}

Zuerst einmal erstelle ich Knoten, dann weise ich jedem Knoten Kindknoten zu, also mit denen er direkt verbunden ist.
Danach erstelle ich eine Verbindung v1 mit den Werte aus dem Array und weise diese neue Verbindung k1 zu.
Zum schluss lass ich mir die Verbindungen ausgeben.

Leider kommts dann zum Out of Memory Error!!!!

Knotenklasse

Code:

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;
      }
   }

Verbindungen

Code:

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();
      }
   }
}

ice-breaker · 17 Februar 2008

Also ich habe den Code jetzt nur überflogen, wieviel Ram verbrauchst du denn in deinem Java-Programm? Vllt müsste man der VM mitteilen, dass mehr benötigt wird, weil du durch eine Endlosschleife neue Objekte erzeugst

Edit: da er über die initialisiereKnoten-Methode nicht hinaus kommt, hast du wahrscheinlich eine Endlosschleife und erzeugst immer neue Objekte, bis eben der für Java reservierte Ram voll ist

Edit2: ich war mal so nett und habe den Fehler gesucht, er liegt in dieser Methode:

PHP:

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

	}

du hast vergessen i zu inkrementieren

Dippen · 17 Februar 2008

genau danke das war mein fehler;

jetzt hat es soweit hingehauen, jetzt habe ich aber ein weiteres Problem, und zwar weiß ich nicht genau , wie ich die Suche über mehrere Stationen gestalten soll.

Mit Rekursion ist klar, aber irgendwie stehe ich grad auf dem Schlauch.

Im Moment kann ich wenigstens überprüfen ob man von einer Station über eine Route von ihr zum Ziel kommt, und welche Route das ist.

Code:

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;
     
     Knoten [] test2 = new Knoten[4];
     test2[0] = k4;
     test2[1] = k3;
     test2[2]= k9;
     test2[3] = k8;
     
    
      
     Verbindung v1 = new Verbindung("Test1");
     v1.addStationen(test);
   
     Verbindung v2 =new Verbindung("Test2");
     v2.addStationen(test2);
     
     k1.addVerbindung(v1);
     k4.addVerbindung(v2);


   }

   public static void main(String args[])
   {
      initialisiereKnoten();
      haltestellen.get(0).gibVerbindungenaus();
haltestellen.get(0).FindeVerbindung(haltestellen.get(5)); //ein Beispiel
     
   }

Code:

	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.verbname + ":");
			System.out.println();
			   verb.gibStationenaus();
			   System.out.println();
		   }
	   }
	   
	   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;
	   }
	   
	   public boolean FindeVerbindung(Knoten ziel){
		   if(besucht){
			   return false;
		   }
		   int i = 0;
		   while(i < verbindungen.size()){
			   int a = 0;
			   while (a<verbindungen.get(i).verb.size()){
			   if (ziel.equals(verbindungen.get(i).verb.get(a))){
				   System.out.println("Benutze "+verbindungen.get(i).verbname);
				 return true;
			   }
			   a++;
			   }
			   i++;
			     
		   }
		   return false;
	   }
	   
	   
	}

Code:

import java.util.ArrayList;

public class Verbindung {
	
	
	public Verbindung(String name) {
		verbname = name;
		
	}

	String verbname;
	boolean frei = true;

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

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

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

[Java] OutofMemory Error bei Routenplaner

Dippen

Member

ice-breaker

return void

Dippen

Member