Nächste Seite: Aufgabe 27 Vorige Seite: Aufgabe 25

Aufgabe 26

Gegeben ist ein 3x3 großes Feld von beweglichen Feldelementen, wobei jedes Feldelement genau eine der Ziffern oder das Leerzeichen aufnimmt und alle 9 vorgegebenen Zeichen benutzt werden müssen. Als Zug bezeichnet man die horizontale oder vertikale Verschiebung eines Feldelementes auf das benachbarte Feldelement, daß das Leerzeichen enthält. Ziel ist das Finden einer Zugfolge, die einen beliebigen, vorgegebenen Anfangszustand in einen Zielzustand überführt. Der Zielzustand ist in der folgenden Abbildung dargestellt.

1 2 3

8 4

7 6 5

Gib für dieses Feld eine geeignete Repräsentation sowohl in OPS5-artiger Notation wie in der Prädikatenlogik an. Wieviele mögliche Konfigurationen gibt es?

Modelliere die verschiedenen Zugmöglichkeiten mit Hilfe von Produktionsregeln sowohl in OPS5-artiger Notation wie in der Prädikatenlogik. Gib weiterhin eine Regel an, die feuert, wenn der Endzustand erreicht ist.

Gib eine Zugfolge an, die aus der folgenden Konfiguration die obige Zielkonfiguration erzeugt:

8 1 3

2 4

7 6 5

Ein Oder-Baum beinhaltet zu einer Startkonfiguration alle möglichen Züge. Dabei werden alle direkten Nachfolgekonfigurationen wiederum rekursiv erweitert (mittels Anwendung von Produktionsregeln). Ermittle anhand dieser Vorgehensweise den Oder-Baum für die obige Startkonfiguration.

Wie die vorigen Teilaufgaben zeigen, definieren Produktionssysteme implizit einen Suchraum, der durch Regelfeuerungen explizit gemacht wird. Beschreibe (mittels Pseudocode) ein Kontrollsystem für diese Suche. Verwende hierzu eine geeignete Datenstruktur für die Konfliktmengen und gib entsprechende Operationen dafür an, mit denen eine Tiefensuche(depth-first) und eine Breitensuche (breadth-first) realisiert werden kann.

Wie verhalten sich beide Strategien bzgl. der Terminierung im allgemeinen? Sind Vorkehrungen erforderlich (Begründung)? Wird die optimale Zugfolge gefunden?

In einer Konfiguration existieren mehrere alternative Zugmöglichkeiten. Versuche in dem Beispiel eine Größe zu finden, mit deren Hilfe eine Aussage über die `Güte' des betrachteten Zuges möglich ist.