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

URL:         /axel/ai_ws0405_blatt7.html

Klausurtermin: 8.2.2005

Aufgabe 7 (4 Punkte)

Die 8 Puzzle Aufgabe ist nun folgende: Finden Sie eine Zugfolge von der Ausgangskonfiguration A=
2
 8
 1
4
  6
 3
7
  
 5
zur Zielkonfiguration
1
 2
 3
8
  
 4
7
 6
 5
mit folgender Strategie:



Wir verwenden folgende heuristische Bewertungsfunktion:

Wert = g(n)+P(n)+3S(n)


Dabei ist g(n) die Suchtiefe.
P(n) ist die Summe über die Distanzen der Einträge von der Zielposition, dabei wird für das  Leerfeld nicht gerechnet.  In der Ausgangsposition ist P(A)=9 wie im folgenden Diagramm eingetragen
1
 2
 2
2
 1
 1
0
0
S(n) wird zyklisch über den Rand erstellt. Hat ein Eintrag nicht den richtigen (d.h. so wie im Ziel) Nachfolger so trägt dieser 2 zu S(n) bei. Ist der Eintrag in der Mitte falsch, trägt dieser 1 bei. Wieder wird der Wert für das Leerfeld nicht ermittelt. S(A)=13 wie folgt:
2
 0
 2
2
 1
 2
2
2


Hinweis: Es sollten 11 Ebenen sein (d.h. das Ziel wird mit Wert 11 gefunden. Die Anzahl der erzeugten Knoten sollte 19 sein. Bei Knoten mit gleicher Bewertung verwenden wir DFS Reihenfolge. Die Knoten werden wieder in LORU Reihenfolge generiert.