Projekt Schiebepuzzle mit dem A*-Algorithmus lösen

Projektinformationen
Aufwand (Ph)	12
Teamgröße	1-2
Schwierigkeitsgrad	schwierig
Ansprechpartner	Herr Bakera
Projekttag

Auftrag

Beim Spiel „8-Puzzle“ geht es darum, von einer beliebig durcheinander gebrachten Position der Zahlen durch Verschieben einzelner Zahlen in das jeweils leere Feld die folgende Zielposition zu erreichen:

1 2 3
8   4
7 6 5

Der A*-Algorithmus kann verwendet werden, um diese Aufgabe für beliebige Ausgangsstellungen zu lösen. Im Folgenden geht es darum, diesen algorithmischen Lösungsweg nachzuvollziehen und mit Suchverfahren ohne Heuristik zu vergleichen.

Aufgabe 1

Finde mittels einer Tiefensuche den Lösungsweg zur oben beschriebenen Zielposition aus folgender Ausgangsstellung:

2 8 3
1 6 4
7   5

Vervollständige dazu den Suchbaum auf dem nächsten Blatt von links nach rechts bis der Zielknoten erreicht ist. Schreibe neben jeden Knoten die Reihenfolge, in welcher diese besucht werden (z.B. mit roter Farbe)

Aufgabe 2

Denke dir eine Heuristik aus (d.h. definiere die Funktion h(N)), um dieses Problem mit dem A*-Algorithmus zu lösen. Diese Heuristik soll ein Maß dafür sein, wie nahe am Ziel der jeweilige Knoten ist.

Aufgabe 3

Zeichne in den Suchbaum aus Aufgabe 1) ein, wie der A*-Algorithmus mit deiner Funktion h(N) von Aufgabe 2) den Baum absuchen würde. Beginne beim Startknoten und berechne für alle Nachfolgeknoten f(n) = g(n) + h(n). Dabei ist g(n) die Anzahl bereits zurückgelegten Kanten. Verfolge immer denjenigen Nachfolgeknoten weiter, der den kleinsten Wert von f(n) hat. Schreibe neben jeden betrachteten Knoten den Wert der Funktion f(N) (z.B. so: (1) mit grün) und die Reihenfolge in welcher die Knoten besucht werden (z.B. <4> mit blau).

• Ist der Algorithmus schneller als ohne Heuristik?
• Wie viele Knoten müssen besucht werden?
• Vergleiche diese Zahl mit denjenigen der Breiten- bzw. Tiefensuche.

Projektgruppen

Bitte tragt euch für das Projekt auf der Seite Projekte von Herrn Bakera ein.

Meilensteine

1. Ich habe ein Klassendiagramm erstellt, das Klassen meiner Problemlösung enthält.
2. Ich habe eine Anwendung geschrieben, das einen Lösungsweg für eine Ausgangsstellung für das 8-Puzzle ausgibt.
3. Ich habe mein Programm mit einem ausführlichen Test getestet.
4. Der Quelltext ist in einer Dokumentation erläutert.
5. Die Dokumentation enthält eine beispielhafte Ausführung eines Programms.

Links

• Intelligenz - Unterlagen als Skript, Folien und Erläuterungen.