Prof. Dr. R. Laue                                                                                                                                  WS0405
                                Künstliche Intelligenz
                                Übungsblatt 6
                                Abgabe: 1.12.04  nach der Vorlesung

URL:         /axel/ai_ws0405_blatt6.html

Klausurtermin: 8.2.2005

Aufgabe 6

Gegeben ist folgendes 8 Puzzle Problem: Wir haben eine 3x3 Matrix mit 8 Feldern (Einträge 1,2,3,...,8) und einem Leerfeld,  dabei kann in einem Zug das Leerfeld mit einem linken/rechten/oberen/unteren Nachbarn  den Platz  tauschen. Ein erlaubter Zug ist z.B von
1
 2
 5
3
 7
6
 4
 8

nach
1
 2
 5
3
 7
 8
6
 4
Die Aufgabe ist nun folgende: Finden Sie eine Zugfolge von der Ausgangskonfiguration
2
 8
 3
1
 6
 4
7
5
zur Zielkonfiguration
1
 2
 3
8
  
 4
7
 6
 5
mit folgender Strategie:
Depth First Search (DFS) in der Reihenfolge links/oben/rechts/unten tauschen des Leerfeldes mit einer maximalen Tiefe 5. (d.h. maximal 5 Kanten im Suchbaum von der Wurzel zu einem Knoten) (2 Punkte)
Breath First Search (BFS) (2 Punkte)
Bidirectional, dabei wird in mehreren Stufen abwechselnd BFS von Start und Zielknoten gemacht (2 Punkte)

Vergleichen Sie die Anzahl der besuchten Knoten. Wann sind die einzelnen Suchstrategien einsetzbar? (2 Punkte)

Es genügt ein Suchgraph (evtl DINA3), mit unterschiedlichen Farben der erzeugten Kanten.