JAVA Hausaufgabe - Routenplanung mit Backtracking


#1

Hallo zusammen! Ich hoffe, es kann mir jemand etwas Hilfestellung geben.


Aufgabe:

Ich soll ein Programm namens JourneyPlaner als Konsolenanwendung schreiben, das eine S-Bahn-Verbindung zwischen zwei beliebigen Bahnhöfen im Berliner S-Bahn-Netz finden und auf der Kommandozeile ausgeben kann und dabei das Prinzip des Backtracking anwenden. Start- und Zielbahnhof sollen auf der
Kommandozeile übergeben werden können. Verwendung soll folgender kleiner Ausschnitt des S-Bahn-Netzes mit den Bahnhöfen Hauptbahnhof, Friedrichstraße, Westkreuz, Gesundbrunnen, Südkreuz, Adlershof und den Bahnen S45 zwischen Südkreuz und Adlershof, S1 zwischen Gesundbrunnen,Friedrichstraße und Südkreuz, S5 zwischen Hauptbahnhof und Friedrichstraße, S41 bzw. S42 zwischen Südkreuz und Westkreuz und S75 zwischen Hauptbahnhof und Westkreuz. Zur Beschreibung des Streckennetzes folgende Arrays sollen folgende Arrays genutzt werden, wobei das erste Array die Bahnhöfe und das zweite die Verbindungen repräsentiert. Die Spalten bzw. Zeilen des zweiten Arrays entsprechen den Bahnhöfen in der Reihenfolge des ersten Arrays. Ein Eintrag > 0 beschreibt die jeweilige S-Bahn, die zwischen zwei Bahnhöfen
verkehrt.

String[] stations = {
  "Hauptbahnhof", "Friedrichstraße",
  "Westkreuz", "Gesundbrunnen",
  "Südkreuz", "Adlershof"};

int [][] lines = {
  {0, 5, 75, 0, 0, 0},
  {5, 0, 0, 1, 1, 0},
  {75, 0, 0, 0, 42, 0},
  {0, 1, 0, 0, 0, 0},
  {0, 1, 41, 0, 0, 45},
  {0, 0, 0, 0, 45, 0}
};
  • lines[0][2] bedeutet, dass zwischen Hauptbahnhof (Index 0) und Westkreuz (Index 2) die Linie S75 verkehrt (und umgekehrt: lines[2][0] ).
  • lines[2][4] bedeutet, dass zwischen Westkreuz (Index 2) und Südkreuz (Index 4) die Linie S42 verkehrt.
  • Umgekehrt verkehrt die Linie S41 (lines[4][2] ).

Der Aufruf des Programms und die Ausgabe sollen folgendermaßen aussehen:

java JourneyPlaner Friedrichstraße Adlershof
Friedrichstraße -> Südkreuz mit S1
Südkreuz -> Adlershof mit S45

Hinweis: Es soll ein Array verwendet werden, in dem gespeichert wird, welche Stationen bereits besucht wurden, um Zyklen zu verhindern. Außerdem soll eine verwendet Liste, in der die Information gespeichert wurden, von welcher Station ich zu welcher Station mit welcher Linie gefahren bin, und geben den Inhalt der Liste anschließend auf der Konsole ausgeben. Die Signatur der Methode könnte folgendermaßen aussehen:

boolean solve( int start, int ziel, boolean [] besucht, List<String> tour);

  • Der Parameter start bezeichnet den Bahnhof, an dem Sie sich gerade
    befinden.
  • Der Parameter ziel bezeichnet den Bahnhof, den Sie erreichen wollen
  • Der Parameter besucht enthält die Information, welche Bahnhöfe Sie
    bereits besucht haben.
  • Der Parameter tour enthält alle zurückgelegten Teilstrecken (z. B.
    Friedrichstraße -> Südkreuz mit S1)

Zusatzaufgabe B1 (5 Punkte)

Erweitern Sie das Programm JourneyPlaner so, dass immer die Strecke mit den wenigsten Zwischenhalten bzw. Bahnwechseln zwischen zwei Bahnhöfen gefunden wird. Zum Beispiel gibt es für die Strecke vom Westkreuz zum Südkreuz mindestens zwei Möglichkeiten:

Westkreuz -> Hauptbahnhof mit S75
Hauptbahnhof -> Friedrichstraße mit S5
Friedrichstraße -> Südkreuz mit S1

und

Westkreuz -> Südkreuz mit S42

Von den beiden Möglichkeiten soll nur die zweite auf der Konsole ausgegeben werden, da diese im Gegensatz zur ersten keinen Bahnwechsel erfordert. Hinweis: Versuchen Sie alle Möglichkeiten aus, auch wenn Sie bereits einen Weg gefunden haben und nehmen Sie dann die Möglichkeit mit den wenigsten Stationen. Wichtig: Sie dürfen die vorgegebenen Arrays nicht ändern!


Einige Sachen habe ich schon fertig. Nur ich verstehe die Aufgabe der Zyklenvermeidung nicht.
Es wäre super, wenn sich jemand melden würde. Vielen Dank.


#2

Ein bißchen Code zu posten (d.h. den aktuellen Stand) könnte helfen, klarer zu machen, woran es hakt. Insbesodere, ob das Problem der Zyklen in der aktuellen Lösung auftritt. Das grundsätzliche Problem der Zyklen ist ja, dass im ungünstigsten Fall die “Ausgabe” sowas wäre wie

Westkreuz -> Südkreuz mit S42
Südkreuz -> Westkreuz mit S42
Westkreuz -> Südkreuz mit S42
Südkreuz -> Westkreuz mit S42
...

Bei welchen Fällen das auftreten könnte, musst du dir überlegen, und diese Fälle dann gezielt testen. Die Ausgabe würde auch ggf. nicht direkt erscheinen. Stattdessen würde das Program sich “aufhängen”.


#3
public class Tlt{

    public static void main(String[] args){

    }

    boolean  solve(int start, int ziel, boolean besucht[][], List<String>tour){
        besucht = new boolean[6][6];
        tour = new LinkedList<String>();

        String[] stations = {"Hauptbahnhof","Friedrichstraße","Westkreuz","Gesundbrunnen","Südkreuz","Adlershof"};
        int[][] lines = {
            {0 , 5, 75, 0, 0 , 0}, 
            {5 , 0, 0 , 1, 1 , 0}, 
            {75, 0, 0 , 0, 42, 0},
            {0 , 1, 0 , 0, 0 , 0},
            {0 , 1, 41, 0, 0 , 45}, 
            {0 , 0, 0 , 0, 45, 0}
        };
        if(lines[start][ziel] != 0){
            String s0 =stations[start]  + " -> " + stations[ziel] + " mit S" + lines[start][ziel];
            tour.add(s0);
            besucht[start][ziel] = true;
            return true;
        }
        else if(lines[start+1][ziel] != 0 && start !=5){
            String s1 = stations[start]  + " -> " + stations[start+1] + " mit S" + lines[start][start+1];
            tour.add(s1);
            solve(start+1, ziel,besucht, tour);
            return true;
        }
        else if(lines[start-1][ziel] != 0 && start != 0 ){
            String s2 = stations[start]  + " -> " + stations[start-1] + " mit S" + lines[start][start-1];
            tour.add(s2);
            solve(start-1, ziel, besucht, tour);
            return true;
        }
        return false;
    }
}

Das habe ich bereits…


#4

Hm. Also… hast du schonmal versucht, da irgendwas laufen zu lassen? Also, so, dass auch auf der Konsole was ausgegeben wird? Die Struktur und Implementierung macht ja nicht sooo viel Sinn. Mit backtracking hat das auch nicht so viel zu tun.

Zumindest die Basis ist hier mal…

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class JourneyPlaner {

    public static void main(String[] args){
        JourneyPlaner journeyPlaner = new JourneyPlaner();
        List<String> tour = journeyPlaner.solve("Friedrichstraße", "Adlershof");
        for (String s : tour)
        {
            System.out.println(s);
        }
        System.out.println("Done");
    }

    String[] stations = {
        "Hauptbahnhof", "Friedrichstraße",
        "Westkreuz", "Gesundbrunnen",
        "Südkreuz", "Adlershof"};
    
    int[][] lines = {
        {0 , 5, 75, 0, 0 , 0}, 
        {5 , 0, 0 , 1, 1 , 0}, 
        {75, 0, 0 , 0, 42, 0},
        {0 , 1, 0 , 0, 0 , 0},
        {0 , 1, 41, 0, 0 , 45}, 
        {0 , 0, 0 , 0, 45, 0}
    };
    
    private List<String> solve(String startName, String zielName)
    {
        int start = Arrays.asList(stations).indexOf(startName);
        int ziel = Arrays.asList(stations).indexOf(zielName);
        List<String> tour = new ArrayList<String>();
        boolean besucht[] = new boolean[stations.length];
        besucht[start] = true;
        solve(start, ziel, besucht, tour);
        return tour;
    }
    
    boolean solve(int start, int ziel, boolean besucht[], List<String> tour)
    {
       ...
    }
}

Wie die eigentliche solve-Methode implementiert werden muss, … da kannst du ja mal überlegen.


#5

(eingeschränktes) Dito.

Doch.

Ja (etwas),

Hauptbahnhof -> Friedrichstraße:
"optimal":
Hauptbahnhof -> Friedrichstraße
"nicht optimal":
Hauptbahnhof -> Westkreuz
Westkreuz -> Südkreuz
Südkreuz -> Friedrichstraße

Hauptbahnhof -> Westkreuz:
"optimal":
Hauptbahnhof -> Westkreuz
"nicht optimal":
Hauptbahnhof -> Friedrichstraße
Friedrichstraße -> Südkreuz
Südkreuz -> Westkreuz

Hauptbahnhof -> Gesundbrunnen:
"optimal":
Hauptbahnhof -> Friedrichstraße
Friedrichstraße -> Gesundbrunnen
"nicht optimal":
Hauptbahnhof -> Westkreuz
Westkreuz -> Südkreuz
Südkreuz -> Friedrichstraße
Friedrichstraße -> Gesundbrunnen

Hauptbahnhof -> Südkreuz:
"optimal":
Hauptbahnhof -> Friedrichstraße
Friedrichstraße -> Südkreuz
"optimal":
Hauptbahnhof -> Westkreuz
Westkreuz -> Südkreuz

Hauptbahnhof -> Adlershof:
"optimal":
Hauptbahnhof -> Friedrichstraße
Friedrichstraße -> Südkreuz
Südkreuz -> Adlershof
"optimal":
Hauptbahnhof -> Westkreuz
Westkreuz -> Südkreuz
Südkreuz -> Adlershof

Friedrichstraße -> Westkreuz:
"optimal":
Friedrichstraße -> Hauptbahnhof
Hauptbahnhof -> Westkreuz
"optimal":
Friedrichstraße -> Südkreuz
Südkreuz -> Westkreuz

Friedrichstraße -> Gesundbrunnen:
"optimal":
Friedrichstraße -> Gesundbrunnen

Friedrichstraße -> Südkreuz:
"optimal":
Friedrichstraße -> Südkreuz
"nicht optimal":
Friedrichstraße -> Hauptbahnhof
Hauptbahnhof -> Westkreuz
Westkreuz -> Südkreuz

Friedrichstraße -> Adlershof:
"optimal":
Friedrichstraße -> Südkreuz
Südkreuz -> Adlershof
"nicht optimal":
Friedrichstraße -> Hauptbahnhof
Hauptbahnhof -> Westkreuz
Westkreuz -> Südkreuz
Südkreuz -> Adlershof

Westkreuz -> Gesundbrunnen:
"optimal":
Westkreuz -> Hauptbahnhof
Hauptbahnhof -> Friedrichstraße
Friedrichstraße -> Gesundbrunnen
"optimal":
Westkreuz -> Südkreuz
Südkreuz -> Friedrichstraße
Friedrichstraße -> Gesundbrunnen

Westkreuz -> Südkreuz:
"optimal":
Westkreuz -> Südkreuz
"nicht optimal":
Westkreuz -> Hauptbahnhof
Hauptbahnhof -> Friedrichstraße
Friedrichstraße -> Südkreuz

Westkreuz -> Adlershof:
"optimal":
Westkreuz -> Südkreuz
Südkreuz -> Adlershof
"nicht optimal":
Westkreuz -> Hauptbahnhof
Hauptbahnhof -> Friedrichstraße
Friedrichstraße -> Südkreuz
Südkreuz -> Adlershof

Gesundbrunnen -> Südkreuz:
"optimal":
Gesundbrunnen -> Friedrichstraße
Friedrichstraße -> Südkreuz
"nicht optimal":
Gesundbrunnen -> Friedrichstraße
Friedrichstraße -> Hauptbahnhof
Hauptbahnhof -> Westkreuz
Westkreuz -> Südkreuz

Gesundbrunnen -> Adlershof:
"optimal":
Gesundbrunnen -> Friedrichstraße
Friedrichstraße -> Südkreuz
Südkreuz -> Adlershof
"nicht optimal":
Gesundbrunnen -> Friedrichstraße
Friedrichstraße -> Hauptbahnhof
Hauptbahnhof -> Westkreuz
Westkreuz -> Südkreuz
Südkreuz -> Adlershof

Südkreuz -> Adlershof:
"optimal":
Südkreuz -> Adlershof
  • Jede Station kann von jeder erreicht werden, es gibt keine nicht erreichbaren Station, ist das so?
  • Es kann mehrere optimale Verbindungen geben.
  • afai® brauchst für die manchmal suboptimale Verbindung und die immer optimale Verbindung zwei unterschiedliche “Prinzip des Backtracking”-Methoden.
  • Bei weiterem Code oder Versuchen können wir dir dann “besser” helfen.

#6

@Marco13 : Ach-ja, das bezog sich *nicht* auf die Aufgabenstellung…

Das sollte etwas helfen, mehr geht nicht:

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * @author
 */
public class JourneyPlaner {

    String[] stations = {
        "Hauptbahnhof", "Friedrichstraße",
        "Westkreuz", "Gesundbrunnen",
        "Südkreuz", "Adlershof"};

    int[][] lines = {
        {0, 5, 75, 0, 0, 0},
        {5, 0, 0, 1, 1, 0},
        {75, 0, 0, 0, 42, 0},
        {0, 1, 0, 0, 0, 0},
        {0, 1, 41, 0, 0, 45},
        {0, 0, 0, 0, 45, 0}
    };

    /**
     * Du möchtest alle tours habn?
     */
    List<List<String>> tours = new LinkedList<>();

    boolean solve(int start, int ziel, boolean[] besucht, List<String> tour) {
        if (start == ziel) {
            // Schreibe hier die Abbruchbedingung der Rekursion
            // evtl. füge noch was hinzu
            return true;
        }
        besucht[start] = true;
        // for (int i = 0; i < stations.length; i++) {
            // Schreibe hier den eigentlichen Rekursionsschritt
            // ...
        // }
        besucht[start] = false;
        return false;
    }

    boolean solve2(String startName, String zielName) {
        boolean[] besucht = new boolean[stations.length];
        LinkedList<String> tour = new LinkedList<>();
        // tours.clear();
        boolean b = solve(Arrays.asList(stations).indexOf(startName), Arrays.asList(stations).indexOf(zielName), besucht, tour);
        // Gebe hier aus, falls etwas ausgeben werden muss
        // ...
    }

    public static void main(String[] args) {
        // Prüfe hier die Argumente
        // Erstelle journeyPlaner
        // Rufe journeyPlaner mit Argumenten auf
        // ...
        JourneyPlaner journeyPlaner = new JourneyPlaner();
        journeyPlaner.solve2(args[0], args[1]);
        // journeyPlaner.solve2("Westkreuz", "Südkreuz");
        // ...
    }
}

#7

Da Performance bei solchen Hausaufgaben meißt keine (große) Rolle spielt sind die 5 Punkte doch leicht verdient, wenn man den Algorithmus erst einmal hat:

  • nicht bei der ersten Lösung aufhören, sondern alle suchen und in einer Liste speichern.
  • Nachdem alle Lösungen gefunden sind diese einfach nach Anzahl der Stationen sortieren und die dann erste nehmen.

bye
TT


#9

Hi @Cenoion,

Da hier Backtracking verwendet werden soll, müsste das vorgehen wie folgt sein:

Du hast eine sortierte Menge, die immer als erstes Objekt den Startbahnhof hat:

  1. {Hauptbahnhof}

Dann fügst du eine der Stationen, die vom Hauptbahnhof erreichbar ist ein.

  1. {Hauptbahnhof, Friedrichstraße}

Prüfst, ob dass der Endpunkt ist, wenn nein, dann fügst du den nächsten Bahnhof ein, der von Friedrichstraße erreichbar ist ein, der aber noch nicht besucht worden ist.

  1. {Hauptbahnhof, Friedrichstraße, Gesundbrunnen}

Wenn nicht der gesuchte Bahnhof, dann weiter… Wenn du 5 Einträge in der Liste hast, aber der gesuchte Bahnhof nicht dabei ist, dann entfernst du den letzten Bahnhof und fährst quasi einen anderen an, der nicht in der Liste besuchter Bahnhöfe ist.

Das ist dann quasi der “Schritt zurück” (aka. Backtracking).

Du versuchst etwas, und wenn das nicht klappt, dann gehst du einen anderen weg.

Ich finde das textuell zu beschreiben ein wenig aufwändig. Schreib mich an, wenn du Unterstützung via Teamspeak benötigst :wink:

Schöne Grüße

Martin