Universität Dortmund
Lehrstuhl Informatik VIII
Stefan Haustein
Wintersemester 2000		 2000-10-25

Übungsblatt 2 zur Vorlesung Künstliche Intelligenz

Abgabe bis Do., 2.11.2000, Briefkasten LS VIII im Eingangsbereich GB IV

Aufgabe 2.1 (4 Punkte):

Austauschstudent Guy Geeky hat sein ganzes Geld für Computerspiele ausgegeben und schickt folgenden Hilfebrief an seine Eltern: 

                           S E N D 
                         + M O R E 
                         =========
                         M O N E Y

Und natürlich wissen seine Eltern, daß jeder Buchstabe für eine andere Ziffer im Bereich [0..9] steht und die Zahlen nicht mit führenden Nullen beginnen.

  1. Wieviel Geld will Guy haben? Schreiben Sie ein Prolog-Programm, welches dieses herausfindet. Implementieren Sie dazu ein Prädikat plus(A,B,Uebertrag,Summe) das zwei Zahlen A und B im Bereich [0..9] addiert (2 P).
  2. Ist die Lösung eindeutig oder gibt es mehrere Lösungen?
  3. Kowalski sagt: Programming = Logic + Control. Erläutern Sie kurz, was in Ihrem Programm mehr Logic und was mehr Control ist.

Aufgabe 2.2: (5 Punkte)

Das sogenannte 8-Puzzle ist ein quadratisches Spielbrett mit 3 x 3 Feldern, auf denen acht durchnumerierte Steine untergebracht sind. Jeder dieser Steine kann, falls er an das leere Feld grenzt, dorthin verschoben werden. Ausgehend von einer beliebigen Startkonfiguration s der Steine auf dem Brett soll durch eine Folge von Verschiebungen eine Zielkonfiguration z erreicht werden. 
                        ---------          ---------
                       | 2  8  3 |        | 1  2  3 |
                       |         |        |         |
                   s = | 1  6  4 |    z = | 8     4 |
                       |         |        |         |
                       | 7  5    |        | 7  6  5 |
                        ---------          ---------
In der Startkonfiguration s können beispielsweise nur die Steine 4 und 5 verschoben werden, weil nur diese beiden neben dem freien Feld liegen.

  1. Implementieren Sie - ausgehend von der A*-Implementierung aus der Vorlesung - das obige Problem geeignet als Suchproblem (3 Punkte).
  2. Bauen Sie die folgenden heuristischen Schätzfunktionen ein (2 Punkte).
    1. h=0.
    2. h= Anzahl der Teile auf der falschen Position (z. B. für s ist h=6, für z ist h=0).
    3. Eine eigene (bessere ?) Heuristik. Wieviele Knoten werden jeweils expandiert ?   Wie lang ist die kürzeste Lösung?

Aufgabe 2.3: (2 Punkte)

Wandeln Sie den Algorithmus so ab, daß er jeweils mit den drei oben beschriebenen Heuristiken eine Bergsteigestrategie verfolgt. Vergleichen Sie die Ergebnisse mit denen aus Aufgabe 2.2.