Mit dieser Webanwendung können Sie eine grafische Darstellung einer Reihe verschiedener Graphen-Suchalgorithmen betrachten, während Sie eine Auswahl von 8 Rätselproblemen lösen.
Einstieg
Auf der linken Seite dieser Anwendung sehen Sie das Kontrollfeld. Über die Systemsteuerung können Sie die folgenden Aspekte der Anwendung konfigurieren:
- Anfangszustand und Zielzustand
- Welcher Suchalgorithmus verwendet werden soll
- Welche heuristische Funktion verwendet werden soll, wenn ein informierter Suchalgorithmus verwendet wird
- und ob der Einzelschritt- oder der Burst-Modus verwendet werden soll
Jede dieser Optionen wird im Folgenden genauer beschrieben.
Anfangs- und Zielzustand
Um den Anfangs- oder Zielzustand einzustellen, können Sie entweder auf die Schaltfläche „Zustand bearbeiten“ oder auf die grafische Darstellung des Zustands klicken.
Sie sollten ein Popup-Fenster wie das folgende sehen:
Um eine Kachel zu ändern, klicken Sie einfach auf die Kachel, die Sie ersetzen möchten, und geben Sie dann den neuen Wert über die Tastatur ein. Dadurch wird die Kachel mit der Kachel getauscht, die vorher diesen Wert hatte.
Suchalgorithmus
N-Puzzle unterstützt fünf verschiedene graphbasierte Suchalgorithmen. Die ersten drei sind uninformierte Suchalgorithmen:
- Breadth-first Search
- Depth-first Search
- Iterative Deepening Search
Die anderen beiden sind informierte Suchalgorithmen:
- A*-Suche
- Greedy-Suche
Wenn Sie einen informierten Suchalgorithmus wählen, müssen Sie auch eine heuristische Funktion auswählen.
Heuristische Funktion
N-Puzzle unterstützt drei verschiedene heuristische Funktionen:
- Euklidischer Abstand
- Manhattan-Abstand (Stadt-Block-Abstand)
- Kacheln an falscher Stelle
Einzelschritt- oder Burst-Modus
N-Puzzle kann in zwei Modi verwendet werden. Die Standardeinstellung ist der Einzelschrittmodus, der es ermöglicht, eine Suche Schritt für Schritt „zurückzuspulen“. Dies ist nützlich, um ein besseres Verständnis dafür zu bekommen, wie ein Suchalgorithmus funktioniert.
Der andere Modus ist der Burst-Modus. Einmal gestartet, setzt der Burst-Modus die Suche fort, bis der Zielzustand gefunden ist. Eine Suche im Burst-Modus kann angehalten, aber nicht „zurückgespult“ werden.
Der Suchbaum
Zustandsdarstellung
Während eine Suche aktiv ist, können Sie eine visuelle Darstellung des Suchbaums sehen. Jeder Knoten in diesem Suchbaum stellt eine Anordnung von Steinen (oder einen Zustand) dar und wird als Kästchen gezeichnet, das in 4 Abschnitte unterteilt ist.
Das folgende Diagramm zeigt einen Knoten aus einer Greedy-Suche:
Der größte Abschnitt ist der Puzzlezustand. Darunter befinden sich zwei kleinere Abschnitte.
Unter dem Puzzlezustand befinden sich zwei Abschnitte. Der linke Abschnitt ist die Tiefe des Knotens. Der rechte Bereich ist die heuristische Bewertung. Der heuristische Wert wird nur bei informierten Suchalgorithmen verwendet. Wenn Sie also die Breadth-first-, Depth-first- oder Iterative Deepening-Suche verwenden, entfällt der heuristische Wert.
Im letzten Abschnitt wird die Reihenfolge aufgezeichnet, in der die Knoten erweitert wurden. Zum Beispiel ist der Wurzelknoten immer ‚#1‘ und der nächste Knoten, der expandiert wird, wird als ‚#2‘ markiert.
Knotenfarben
Um den Suchbaum ‚lesbarer‘ zu machen, ist der Rand jedes Knotens je nach seinem aktuellen Zustand farblich gekennzeichnet.
Das folgende Diagramm zeigt den A*-Algorithmus (mit der Euklidischen Distanzheuristik), angewandt auf ein Problem, das in nur zwei Zügen gelöst werden kann:
Die Farben können wie folgt interpretiert werden:
| Farbe | Bedeutung |
|---|---|
| Blau | Wenn ein Knoten in der Offenen Liste ist, wird er blau hervorgehoben. |
| Rot | Nach jeder Iteration eines Suchalgorithmus wird der Knoten, der als nächstes expandiert wird, rot hervorgehoben. Dies gilt auch, wenn der Zielknoten gefunden wurde. |
| Grau | Wenn ein Zustand erforscht wurde, wird er ausgegraut. In Schritt 2) des obigen Diagramms wurde beispielsweise der Ausgangszustand grau eingefärbt, um anzuzeigen, dass er erkundet wurde. In Schritt 3) wird ein Knoten, der den Ausgangszustand repräsentiert, wiederentdeckt, aber nicht erweitert, da der Ausgangszustand über den Wurzelknoten erweitert wurde. |
| Grün | Wenn der Zielzustand gefunden wurde, wird er grün hervorgehoben. |
| Gold | Wenn ein Knoten, der den Zielzustand repräsentiert, gefunden wurde, werden alle Knoten auf dem Weg zurück zum Wurzelknoten in Gold hervorgehoben. |
| Lila | Bei der iterativen Vertiefungssuche werden unerforschte Knoten, die die maximale Tiefe überschreiten, nicht zur offenen Liste hinzugefügt. Diese Knoten werden lila eingefärbt. |
Offene und geschlossene Listen
Während die Suchalgorithmen laufen, werden zwei Listen geführt. Die erste ist die Offene Liste – sie wird verwendet, um Knoten zu verfolgen, die entdeckt, aber noch nicht erforscht wurden.
Die zweite ist die Geschlossene Liste – sie wird verwendet, um Knoten zu verfolgen, die erforscht wurden, oder Knoten, die nicht erforscht werden, weil sie Zustände repräsentieren, die bereits durch andere Knoten erforscht wurden.
Wenn eine Suche aktiv ist, wird die Anzahl der Knoten in den Listen „Offen“ und „Geschlossen“ in der oberen linken Ecke angezeigt:
