Stufe 4: Suchen einer Lösung mit Backtracking

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 Wartebebingung, 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 suche(). Die rekursive Suche findet in einer überschriebenen Methode statt, die die Teilstrecke von einem Zwischenstart zu einem Zwischenziel sucht.

Alle Methode 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.

UML

UML Diagramm

Musterlösung

Github Projekt scalingbits/dhbwjava

Hilfe! Wie packe ich das an?

  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. Nutzen Sie die Serialisierung
    1. Die Klassen Labyrinth und Position müssen die entsprechende Schnittstelle implementieren
  4. Ü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.
  5. Starten Sie die Suche in einem eigenen Thread, dann kann das GUI parallel arbeiten und Sie können die Suche beobachten
  6. 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 welches den Suchauftrag gibt. Man kann dann nach jedem Krümel ein Update machen
      2. Legen Sie sich ein neues Labyrinth an. Kopieren Sie sich das Labyrinth des GUIs!
    4. 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()
    5. Testen der Rekursion in Teilschrittem ist schwierig. Möglickeiten sind:
      1. findeOptionen() mit Testfällen testen
      2. Abbruch der Rekursion testen: Start ist gleich Ziel
    6. 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
        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, 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
          2. wir legen eine neue Liste an
          3. hängen die aktuelle Position als Lösung ein und
          4. und geben sie zurück
          5. Ende der Methode
        4. falls nicht rufen wir die Methode suche() rekursiv auf.
          1. Verwende die Option als Start
          2. Verwende das ursprüngliche Ziel
        5. Merke dir die
          1. erste Liste (Heureka!)
          2. die kürzeste Liste (Hänsel läuft nicht gerne)
        6. 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
        7. 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