Programmierprojekt: Ariadnefaden

 Im Projekt Ariadnefaden wird eine graphische Anwendung entwickelt mit der man Labyrinthe entwickeln kann um sich dann den besten Pfaden suchen lässt.

Das Projekt wird in mehreren Stufen entwickelt:

  • 1. Stufe: Entwicklen eines "Buttons" der eine Zelle repräsentiert
    • Grundlegende Swingkonzepte: Komponenten, Listener, Actionhandler, innere Klassen
  • 2. Stufe: Aus dem Button ein Feld von Buttons entwickeln
    • Swing Layout Manager
  • 3. Stufe: Entwickelte Labrinthe laden und speichern
    • Java Streams
  • 4. Stufe: Eine Lösung entwickeln
    • Backtracking
    • Generische Typen
  • 5. Stufe: Paralleles Backtracking
    • Java Concurrency Package

Ein Beispiel eines Labyrinths:

Ein Labyrinth

 Die Quellen können aus dem github Projekt scalingbits/dhbwjava aus dem Paket s2.backtrack heruntergeladen werden.

Stufe 1: Swing

 

Die Klasse Zelle ist ein JButton der abhängig vom Zustand einer Position eine bestimmte Farbe annimmt. In der main() Methode werden die verschiedenen Menüpunkte implementiert um den JButton zu testen. Rechts ist ein Beispiel zu sehen.

Jede Zelle hat einen Zeiger auf eine Position. In der Klasse Zeiger werden alle graphischen Aspekte implementiert. In der Klasse Position wird die Logik zum Darstellen einer Position implementiert.

Die Zellen werden in der nächsten Stufe zu einem Feld zusammengefaßt aus dem ein Labyrinth gebaut wird. Die Klasse Position hat hierzu eine x und y Koordinate da sie später in einem Feld zu Lösen des Labyrinths verwendet wird.

Implementieren Sie die Klassen im Paket s2.backtrack.

ScreenShot Phase 1

 

UML Diagramm Zelle, Position

Quellcode der Klasse Zelle

package s2.backtrack;

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.image.BufferedImage;
import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JCheckBoxMenuItem;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;

/**
*
* @author s@scalingbits.com
* @version 1.0
*/
public class Zelle extends JButton{
/**
* Die Zelle ist im Editiermodus und erlaubt Änderungen zwischen
* Wand und Leer.
* Alle Objekte teilen sich diese Eigenschaft
*/
public static boolean editierbar = false;
public static Position start;
public static Position ziel;
/**
* Die x,y Position
*/
public Position p;

public static Icon leerIcon;
public static Icon wandIcon;
public static Icon kruemelIcon;
public static Icon startIcon;
public static Icon zielIcon;
public static Icon loesungIcon;
public static int xRaster=20;
public static int yRaster=20;

/**
*
* @param pp eine Position im Feld
*/
public Zelle (Position pp) {
// Hier kodieren
}

/**
* Update des graphischen Objekts falls sich die Position verändert hat
* Es wird die Farbe und der Tooltip neu gesetzt
*/
public void update() {
// Hier kodieren
}

/**
* Erzeugt eine Ikone in der richtigen Größe und Farbe
* @param farbe Farbe der Ikone
* @return die erzeugte Ikone
*/
public static ImageIcon erzeugeIcon(Color farbe) {
BufferedImage img =
new BufferedImage(xRaster, yRaster, BufferedImage.TYPE_4BYTE_ABGR);
Graphics2D g = img.createGraphics();
g.setColor(farbe);
g.fillRect(0, 0, xRaster-1, yRaster-1);
g.dispose();
return new ImageIcon(img);
}

/**
* Erzeugt ein Fenster mit einem einzelnen Button zum Testen der Funktionen
* dieser Klasse
* @param args Eingabeparameter werden nicht gelesen
*/
public static void main(String[] args) {
// Implementieren Sie alles was zum testen des JButtons benötigt wird.

} // Ende Methode main
} // Ende Klasse Zelle

Musterlösung

Github Projekt scalingbits/dhbwjava

Hilfe! Wie packe ich das an?

Hier ein paar Tips wie man dieses Problem in kleineren Schritten lösen kann...

Wichtig: Immer ein lauffähiges Programm behalten!

  1. Erzeugen Sie die Klasse Zelle als Spezialierung von JButton. Sie wird sich erstmal wie ein normaler JButton verhalten...
  2. Schreiben Sie ein Hauptprogramm:
    1. Legen Sie ein JFrame an
    2. Erzeugen Sie ein Objekt vom Typ Zelle. Geben Sie dem Button einen Namen
    3. Fügen Sie den Button zum JFrame hinzu
    4. Fügen Sie notwendigen Code zum JFrame hinzu (Größe, Schliesen beim Verlassen etc.)
    5. Testen Sie alles. Ein Fenster mit einem JButton erscheint
  3. Fügen Sie ein Menü mit einer Leiste hinzu
    1. Aktionen benötigen Sie keine
    2. Testen Sie alles
  4. Konstruktor für Zelle:
    1. Setzen Sie den Namen des JButtons im Konstruktor des JButtons (-> super )
    2. Erzeugen Sie einen Konstruktor ohne Parameter
    3. Passen Sie den Aufruf im Hauptprogramm an.
    4. Testen Sie alles
  5. Umbauen von einem JButton mit Text zu einem JButton mit Farbe
    1. Legen Sie die Konstanten für die Größe der Ikone an (x,y und statisch, sie gilt für alle Buttons)
    2. Legen Sie einen Zeiger auf eine Ikone Ihrer Wahl an (z.Bsp. Start = rot). Sie ist statisch und final
    3. Kopieren Sie sich die Methode zum Erzeugen von Ikonen in die Klasse
    4. Erweitern Sie den Konstruktor
      1. Erzeugen Sie eine rote Ikone wenn nötig (Factory-pattern! Suchen Sie auf dem Webserver nach Factory wenn notwendig )
      2. Löschen Sie den super Aufruf mit Namen
      3. Setzen Sie die Ikone (Das findet man mit Google "java API 8 JButton)
    5. Testen Sie Ihren roten Button
  6. Bunte Buttons Infrastruktur:
    1. Wiederholen Sie alles was Sie für rote Ikonen gemacht haben für die anderen Farben ...
    2. Testen: Codieren Sie eine andere Farbe für Ihren Button
  7. Vorbereiten des Farbewechseln beim Klicken
    1. Schreiben Sie einen Actionlister für einen Buttonklick
    2. Am besten im Konstruktor. Jeder Button soll automatisch einen besitzen.
    3. Schreiben Sie beim Buttonclick etwas auf die Konsole
    4. Testen des Buttonclicks!
    5. Löschen Sie die Konsolenausgabe nicht vergessen
  8. Implementieren Sie Klasse Position
    1. Minimalanforderungen:
      1. x,y Attribut und Farbe (entweder enum oder Konstante für jede Farbe)
      2. Konstruktor
    2. Der Rest der Klasse ist mechanisch. Sie machen das jetzt oder wenn Sie es später benötigen...
  9. Ändern des Konstruktors der Klasse Zelle
    1. Akzeptieren Sie eine Position
    2. Merken Sie sich die Position...
    3. Passen Sie das Hauptprogramm an
      1. Erzeugen Sie zuerst eine Position
      2. und dann einen JButton mit Ihr
    4. Testen Sie alles (keine optische Verbesserung)
  10. Implementieren Sie einen "Tooltip"
    1. Im Konstruktor von Zelle
    2. Lesen Sie die x,y Koordinate und den Zustand aus
      1. am besten jetzt eine Methode toString() in Position implementieren
    3. Testen Sie Ihre Anwendung mit dem Tooltip
  11. Farbwechsel des Buttons
    1. Verbessern Sie den ActionListener Ihres JButton ( er ist irgenwo im Konstruktor...)
    2. Lesen Sie den Zustand ihrer "Position" aus und wechseln Sie ihn (setIcon() )
    3. Testen Sie Ihren JButton
  12. Implementieren Sie die Tests der anderen Farben und den Editierschutz
    1. Sie benötigen ActionListener die auf die anderen Farben wechseln...
    2. Se benötigen einen ActionListener der die Editierbarkeit checkt und die statische Variable wechselt
      1. Blocken Sie die Editierbarkeit im ActionListener der die Farbe von leer auf Wand wechselt...
    3. Testen Sie alles!

Stufe 2: Swing mit Layout Manager

In der zweiten Phase werden viele Zellen mit JButtons zu einem Feld zusammengefaßt.

Layout

Nutzen Sie einen Layoutmanager mit dem Sie Oben das Feld darstellen können und unten die Statusinformationen. Was bietet sich hier an?

Welcher Layoutmanager bietet sich für das Feld an?

Unten sollen Sie zwei Komponenten implementieren, einen Text und einen variablen Text. Welcher Layoutmanager bietet sich hier an?

Komponenten

Welche Komponenten benötigen Sie?

Pull-down Menü

Implementieren Sie das Pull-down Menü.

Das Feld soll editierbar sein oder schreibgeschützt. Welche Komponente bietet sich hier an?

Implementieren Sie eine Textausgabe für Weg finden, Oeffnen, Speichern. Diese Funktionen werden in späteren Phasen implementiert.

Implementieren Sie Editieren, Loeschen, Beenden.

Labyrinth ohne Menü

GUI mit ausgeklapptem Menü

Labyrinth mit Menue

 

Klasse Backtrack

Zur Klasse Backtrack gibt es einige Entwurfsüberlegungen. Die Klasse soll in den nächsten Stufen in der Lage sein das Laden und Speichern von Dateien zu unterstützen. Sie soll es auch erlauben, dass die Suchalgorithmen eingebunden werden.

Dies kann man erreichen in dem man alle Aktionen des Pull-Down Menüs als eigene Methoden implementiert. Die Methoden für spätere Phasen machen nur ein Update im Textfeld. So kann man sehen, dass sie aufgerufen werden. In den späteren Phasen wird dann die Klasse Backtrack spezialisiert und die entsprechenden Methoden überschrieben.

Dadurch kann man auf den Code der vorhergehenden Klasse zurückgreifen und muss den Code nicht replizieren.

Hierzu muss man das GUI in einer Instanz von Backtrack implementieren. Das GUI der vorhergehenden Phase wurde als statische Methode in Zelle implementiert. Dies ist hier nicht geschickt.

Um das Editieren zur ermöglichlichen muß der Benutzer einen aus mehren Zuständen auswählen. Dies kann man mit der Klasse javax.swing.JCheckBoxMenuItem erreichen.

Klasse Labyrinth

Die Klasse Labyrinth dient zum Darstellen und Speichern des Labyrinths. Sie enthält keine Aspekte der Benutzeroberfläche. Das Labyrinth wird von Backtrack benutzt um die entsprechenden graphischen Elemente korrekt anzuzeigen.

Das GUI immer etwas sinnvolles anzeigen soll, wird ein Labyrinth nach dem Laden immer in das Labyrinth umkopiert welches zur Anzeige benutzt wird. Jeder JButton (Zelle) hat einen Zeiger auf eine Position. Würde man den neuen Zustand nicht in ein Objekt der Klasse Position umkopieren müsste man alle Zeiger der Zellenobjekte auf die neuen Objekte des Labyrinths ändern.

Die Klasse Labyrinth hat deshalb zwei Konstruktoren

  • einen Copy-Konstruktor
  • einen Konstruktor mit den Dimensionen und der Start und Ziel-Position
    • Hier ist es wichtig die Koordinaten der Start- und Ziel Objekte zu nutzen und die dazu passenden Objekte im Feld zu identifizieren.

Die Methode update() kopiert ein existierendes Labyrinth in ein anderes um.

getPos() ist eine Bequemlichkeitsmethode die in den späteren Phasen beim Suchen helfen wird.

UML

uml Diagramm

Die Klasse Labyrinth wird alle Information enthalten die gespeichert werden:

  • Labyrinth
  • Position 

Die Klasse Labyrinth enthält Zeiger auf den Start und das Ziel des Labyrinths. Diese beiden Objekte müssen Teile des Feldes sein welches angezeigt wird!

Die Klassen die zum GUI gehören sind:

  • Backtrack
  • Zelle

.

 

Musterlösung

Github Projekt scalingbits/dhbwjava

Hilfe! Wie packe ich das an?

Hier ein paar Tips wie man dieses Problem in kleineren Schritten lösen kann...

Wichtig: Immer ein lauffähiges Programm behalten!

  1. Implementieren Sie die Klasse Labyrinth
    1. Erzeugen Sie im Konstruktor ein zweidimensionales Feld von Position
    2. Der graphische Teil der Anwendung soll auf eigenen Datenstrukturen arbeiten. Deshalb benötigen Sie
      1. Eine Updatemethode: Der Zustand einer Vorlage wird in in ein Labyrinth kopiert
      2. Einen Copy-Konstruktur
      3. Die Klasse Position sollte eine ähnliche Infrastruktur haben
    3. Start und Ziel: Können theoretisch aus Objekten bestehen, die nicht zum aktuellen Labyrinth gehören (Gefahr von Inkonsistenzen!)
      1. Lesen Sie das Start- und Ziel-objekt im Konstruktor nur
        1. Ziegen Sie mit Ihren internen Zeigern auf die äquivalenten Objekte im Labyrinth.
        2. Setzen Sie deren Zustand.
          1. Equals- und Update-Methoden in Position sind hier sehr nützlich
    4. Setzen Sie beim Anlegen des Feldes alle Positionen auf eine leere Position (ausgenommen Start und Ziel)
    5. Testen ist schwierig: Mut zur Lücke...
  2. Design Ihres GUIs (Klasse Backtrack)
    1. Bauen Sie Ihr GUI im Konstruktor der Klasse
    2. Legen Sie ein JFrame an
      1. Beenden Sie die Anwendung beim Schliessen des Fenster
    3. Nutzen Sie ein Borderlayout als Hauptstruktur
      1. Im Süden implementieren Sie ein JPanel mit z.Bsp. ein Flowlayout
        1. Ein JLabel links
        2. Ein JTextField rechts
          1. Nur lesbar
          2. Merken Sie sich den Zeiger auf das Textfeld als Attribut in Ihrer Hauptklasse.
            1. ActionListener in inneren Klassen müssen hier den Zustand dokumentieren
      2. Im Zentrum wird ein neues JPanel mit Gridlayout angelegt
        1. Die Dimension muss zum Labyrinth passen
        2. Legen Sie ein Labyrinth an.
        3. Legen Sie zu jedem Feld im Labyrinth eine Zelle an und stecken Sie die Zellen in das JPanel mit Gridlayout
        4. Speichern Sie sich einen Zeiger auf das Anzeigelabyrinth in einem Attribut der äusseren Klasse
  3. Implementieren Sie das Hauptprogramm
    1. Legen Sie ein Objekt Ihrer Klasse an
    2. Implementieren und benutzen Sie eine Methode anzeigen()
      1. Die Methode "packt" das JFrame und zeigt es an
      2. Man muss später Spezialisierungen der Klasse mit dem spezifisichen Konstruktor in zukünftigen main() Methoden erzeugen. Dies Methode kann man dann wiederverwenden...
    3. Testen Sie alles!
  4. Implementieren Sie das Menü mit allen Einträgen. Diese Klasse wir noch spezialisiert. Esa erspart später Schreibarbeit
    1. Schreiben Sie hierfür eine eigene Methode
    2. Rufen Sie die Methode aus dem Hauptprgramm auf
  5. Behandlung der Aktionen (siehe Screenshot)
    1. Viele Behandlungen werden erst später benötigt. Implementieren nur eine Kontrollausgabe auf der Konsole
    2. Vorgehen:
      1. Die Klasse Backtrack wird in späteren Phasen spezialisiert
      2. Schreiben Sie für jede Aktion eine Methode die einen Zeiger auf die graphische Komponente entgegen nimmt.
      3. Diese Methoden werden später überschrieben!
      4. In der Methode wird ein ActionListener angelegt und registriert
    3. Jetzt zu implementierende Behandlungen
      1. Beenden der Anwendung
      2. Schützen der Anwendung vor Editierversuchen
      3. Löschen des Labyrinths
    4. Testen, testen, testen
  6. Feiern: Sie haben die nächste Stufe geschafft.

Stufe 3: Laden und Speichern von Labyrinthen

Klasse BacktrackIO

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

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

Da man hier mit Verzeichnissen arbeiten muss, sollte man die folgenden GUI Klassen verwenden:

Man kann Sie wie folgt einsetzen um den Zugriff auf eine Datei zu bekommen:

File selectedFile;
JFileChooser jfc
= new JFileChooser(FileSystemView.getFileSystemView().getHomeDirectory());
int returnValue = jfc.showSaveDialog(null);
if (returnValue == JFileChooser.APPROVE_OPTION) {
selectedFile = jfc.getSelectedFile();
System.out.println(selectedFile.getAbsolutePath()); // Ab hier mit der Datei arbeiten... }
Beispiel JFileChooser
Damit erhalten Sie, abhängig von Ihrer Plattform, einen Auswahldialog im Home-Verzeichniss Ihres Benutzers. Beispiel JFileChooser

 



UML

UML Diagramm

Musterlösung

Github Projekt scalingbits/dhbwjava

Hilfe! Wie packe ich das an?

  1. Erzeugen Sie eine spezialisierte Klasse 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 zum Speichern
    1. Nutzen Sie Klasse JFileChooser zum Selektieren der Datei
    2. Holen Sie sich von der Klasse JFileChooser das Ergebnis (Eine Instanz der Klasse File)
    3. Schreiben Sie Labyrinth, Start und Ziel als Datei
      1. Verketten Sie FileOutputStream mit ObjectOutputStream
      2. Schreiben Sie Ihre GUI Datenstruktur des Layrinths in die Datei
    4. Behandeln Sie alle Ausnahmen wie benötigt...
    5. Testen: Wurde die Datei geschrieben?
  5. Vorbereiten zum Laden
    1. Schreiben Sie eine Methode die alle JButtons updated. Nach dem Laden müssen neue Zustände angezeigt werden
  6. Überschreiben Sie die Methode zum Laden
    1. Nutzen Sie den JFileChooser zur Identifikation der Datei
    2. Laden Sie die Datei. Sie haben nun einen Zeiger auf ein neues Labyrinth
    3. Machen Sie Ihr Labyrinth editierbar
    4. Nutzen Sie die Methode update() und Ihr GUI Labyrinth mit dem eingelesen Labyrinth zu überschreiben
    5. Machen Sie ein Update auf allen Zellen
    6. Testen

 

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

 

Stufe 5: Suchen einer Lösung mit einem parallelisiertem Backtrack Algorithmus

Klasse BacktrackSucheParallel

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

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

Klasse Ariadne4Parallel

Sie müssen hier einen Konstruktor implementieren, da die Oberklasse einen besitzt.

Das parallele Suche wird in der überschriebenen Methode suchen(von, nach) implementiert.

UML

UML Diagramm

Musterlösung

Github Projekt scalingbits/dhbwjava