Klasse BacktrackSuche

Diese Klasse wird aus BacktrackIO spezialiert. Sie nutzt die gesamte Infrastruktur. Sie überschreibt

• loesungFinden() 
• main(String[] args): Sie müssen hier eine Instanz von BacktrackSuche anlegen und anzeigen

Klasse Ariadne

In dieser Klasse wird die Suche implementiert.

Zuschauen beim Suchen...

Implementieren Sie eine Wartebedingung, dann können Sie Ihrem Algorithmus zuschauen.

Definieren Sie eine Variable mit Millisekunden Schlafzeit

public static final int WARTEN=10; //ms Schlafen vor dem nächsten Schritt

Lassen Sie den aktuellen Thread schlafen

public static final int WARTEN=1000; // ms Schlafen vor dem nächsten Schritt
try {
       Thread.sleep(WARTEN);
    } catch (InterruptedException ex) {
         System.out.println("Probleme mit Thread aufwachen");
    }

Das GUI muss jetzt noch wissen, dass sich etwas geändert hat. Deshalb benötigt man einen Zeiger auf das GUI. Das schafft eine Abhängigkeit vom GUI und ist nicht schön (muss aber sein).

Triggern Sie ein Update indem Sie das Labyrinth des GUIs erneuern und dann alle Buttons dazu zwingen den Zustand ihrer Zelle zu checken:

bt.laby.update(laby);
bt.updateButtons();

Die rekursive Suche

Es gibt einen Einstieg in die Suche ohne Parameter mit der Methode  suche(). Die rekursive Suche findet in einer überschriebenen Methode statt, die die Teilstrecke von einem Zwischenstart zu einem Zwischenziel sucht.

Alle Methoden arbeiten auf dem gleichen Labyrinth, dadurch kann man Stellen entdecken auf denen man schon mal war.

Eine separate Methode findeOptionen() checkt alle Nachbarpositionen und gibt eine Liste von Optionen zurück.
Optionen sind freie Felder. Keine Optionen sind die Wände und Felder die schon einmal betreten wurden.

UML

Musterlösung

Github Projekt scalingbits/dhbwjava

• Klasse Position.java
• Klasse Zelle.java
• Klasse Labyrinth.java
• Klasse Backtrack.java
• Klasse BacktrackIO.java
• Klasse BacktrackSuche.java

Hilfe! Wie packe ich das an? Grundlegende Überlegungen Die Suche findet in einer eigenen Klasse statt. Man kann dann diese Klasse für das parallele Suchen verwenden Die Suche muss in einem eigenen Java-Thread laufen. Sie wird sonst das GUI blockieren und wir wollen den Fortschritt sehen. Das heißt, das GUI muss etwas während der Suche arbeiten können Mein Rechner wird zu schnell suchen. Ich muss meinen Tread nach jedem Schritt schlafen legen damit ich den Schritt sehen kann Mein Suchalgorithmus muß das GUI nachen jedem Schritt bitten den neuen Zustand anzuzeigen. Wir benötigen einen Zeiger auf das graphische Objekt um es den neuen Zustand malen zu lassen. Rekursion: Ich bestimme alle von meiner aktuellen Position erreichbaren Nachbarfelder. Ich nehme jedes Nachbarfeld als Startposition einer neuen Suche. Ich benutze immer das gleiche Ziel Habe ich das Ziel gefunden erzeuge ich eine Java-Liste, trage die Zielposition ein und gebe die Liste als Ergebnis zurück Hatte eine Suche meiner Nachbarfelder Erfolg, nehme ich die Ergebnisliste, setzte meine aktuelle Position vorne an und gebe die Liste als Ergebnis zurück

1. Erzeugen Sie eine spezialisierte Klasse BacktrackSuche aus der Klass BacktrackIO
2. Kopieren Sie sich das Hauptprogramm der Oberklasse
   1. Anpassung: Erzeugen Sie ein Objekt der aktuellen Klasse
   2. Testen: Läuft alles wie zuvor?
3. Überschreiben Sie die Methode loesungFinden()
   1. Implementieren Sie einen ActionListener der die Suche started
   2. Setzen Sie das Statusfeld. Das ist ein guter Test ob der Aktionlistener funktioniert.
4. Starten Sie die Suche in einem eigenen Thread, dann kann das GUI parallel arbeiten und Sie können die Suche beobachten
5. Implementieren Sie die Klasse Ariadne
   1. Sie können Sie auch Gretel nennen, Ariadne streut in meinem Beispiel Krümel...
   2. Variablen
      1. int zum Warten in Millisekunden, Ariadne düst sonst wie von der Hummel gestochen durch das Labyrinth und Sie können nicht sehen wie der Weg gefunden wird.
      2. Ein Zeiger auf ein Labyrinth: Die Klasse arbeitet rekursiv auf einem eigenen Labyrinth
      3. Ein Rückzeiger auf Backtrack: Hiermit können Sie das GUI nach jedem gestreuten Krümel um ein Update bitten. Dann können Sie Ariadne beim Krümelstreuen zuschauen. Das ist nicht elegant, weil damit Ariadne von dem GUI abhängt. Das ganze am besten protected, diese Klasse wird nochmals spezialisiert werden
   3. Einen Konstruktor
      1. Parameter: Das GUI (Javaklasse Backtrack) welches den Suchauftrag gibt. Man kann dann nach jedem Krümel ein Update machen und zuschauen
      2. Legen Sie sich ein neues Labyrinth an. Kopieren Sie sich das Labyrinth des GUIs!
   4. Hilfsmethode: findeOptionen() implementieren
      1. Geben Sie ein Set mit allen Optionen zurück.
      2. Testen Sie alle Punkte um den gegebenen Startpunkt. Vorsicht; Ihr Feld ist endlich, es kann Feldüberläufe geben.
      3. Tipp: Benutzen Sie die Methode Position.neuerWeg(), sie wird wahr wenn das entsprechende Feld keine Wand oder kein Krümel ist.
   5. Eine Methode suche()
      1. Diese Methode wird vom GUI aufgerufen
      2. Rückgabe: Eine Liste von Position mit dem Pfad zur Lösung
      3. Diese Methode nutzt den hardcodierten Start und Ziel des Labyrinths zum Aufruf der rekursiven Methode suche()
   6. Testen der Rekursion in Teilschrittem ist schwierig. Möglichkeiten sind:
      1. findeOptionen() mit Testfällen testen
      2. Abbruch der Rekursion testen: Start ist gleich Ziel
   7. Design der Rekursion...
      1. Diese Methode bekommt einen individuellen Start und ein individuelles Ziel. Diese Methode soll Teilaufgaben lösen!
      2. Streue erstmal einen Krümel. Gretel meint das ist immer eine gute Sache...
         1. Das ist die echte Arbeit zum Verkleinern unseres Problems bei der Rekursion
      3. Tue gutes und sprich darüber...
         1. Kopiere das Suchlabyrinth um in das GUI-Labyrinth (es hat jetzt einen neuen Krümel=
         2. Rufe in Backtrack die Methode updateButtons() auf 
         3. So kann man sehen was gerade passiert
      4. Diese Methode ruft eine Methode findeOptionen() auf
         1. Diese Methode liefert eine Liste von Optionen
         2. Optionen sind freie Felder: keine Wand, kein Krümel
            1. Liegt da ein Krümel, so waren wir schon mal da und haben den Weg gefunden (super) oder auch nicht (da müssen wir nicht weitersuchen)
         3. Ergebnis ist eine Menge von Positionen
      5. Die Rekursion:
         1. Arbeite alle Optionen ab
         2. Erstmal Pause...
            1. Lasse den Thread etwas schlafen, damit man das Herumirren im Labyrinth verfolgen kann.
         3. Hänsel möchte wissen ob wir schon da sind?
            1. Wenn der Start das Ziel ist haben wir die Lösung gefunden
               1. wir legen eine neue Liste an
            2. falls nicht rufen wir die Methode suche() rekursiv auf.
               1. Verwende die Option als Start
               2. Verwende das ursprüngliche Ziel
            3. Wir hängen die aktuelle Position als Lösung ein und
               1. und geben sie zurück
               2. Ende der Methode
         4. Merke dir die
            1. erste Liste (Heureka!)
            2. die kürzeste Liste (Hänsel läuft nicht gerne)
         5. Nach dem Abarbeiten aller Optionen:
            1. Nimm Lösungsliste (der Weg)
            2. Hänge vorne die Option and um den Lösungsweg zu verlängern
         6. Gib die Liste mit der gewünschten Lösung zurück
            1. Gibt es keine Lösung ist die Liste leer
            2. Die Länge der Liste ist die Länge des Pfades