Beispiele

Nach einer kurzen theoretischen Einführung in die Prädikatenlogik wurde schon die 1. Aufgabe mit Prolog gelöst.



Aufgabe 1:

Eingabe von "kind_von" Verhältnissen zwischen zwei Personen, und von Regeln, wer ein Elternteil, ein Onkel/eine Tante und ein Cousin oder eine Cousine ist.

Nach diesem kleinen praktischen Exkurs wurde das Konzept der Liste erklärt, welches für die folgende Einführung in Suchverfahren wie Tiefen- oder Breitensuche und iterative Deepening benötigt wurde.

[ Quelltext anzeigen ]


Aufgabe 2 (Tiefensuche):

In einem angegebenen Baum (Abb. 1) ist zu untersuchen, ob ein Knoten von einem anderen Knoten aus erreichbar ist, dh. ob es einen Weg zwischen zwei Knoten gibt. Der Baum ist angegeben durch seine Kanten als Fakten (z.B. edge(a, b)).

Die Vorgangsweise bei der Tiefensuche ist das Abgehen eines Suchpfades, bis sein Ende erreicht oder eine Lösung gefunden wird, um dann wieder beim nächst-höheren Knoten den nächsten Weg bis zu einem Blattknoten zu gehen, um dann wieder .....

Man erkennt aufgrund dieser Beschreibung, dass die Tiefensuche in einem unendlichen Suchraum unter Umständen keine Lösung liefert, auch wenn eine existiert. Ausserdem wird die erste gefundene Lösung, die nicht immer die optimale, sondern die, die im Suchbaum am weitesten links steht, ist, gefunden.

[ Quelltext anzeigen ]


Aufgabe 3 (Listenmanipulation):

Das Suchverfahren der Tiefensuche ist in Prolog einfach zu implementieren, da der Prolog-Interpreter selbst Beweisbäume nach diesem Muster aufbaut. Die anderen Suchverfahren erfordern etwas mehr "Geschicklichkeit" vom Programmierer und müssen durch eigene Konstrukte "simuliert" werden. Da im Rahmen dieses Kurses hauptsächlich Listen eingesetzt wurden, ist eine Vertrautheit mit der Listenmanipulation und Rekursion in Prolog notwendig. Dazu wurden geübt:

[ Quelltext anzeigen ]


Aufgabe 4 (iterative Deepening):

Wird der Suchbaum zu einen zyklischen gerichteten Graphen, so ist die Tiefensuche nicht mehr zielführend, weil sie unter Umständen unendlich lange dauert (Siehe Abb. 2, gibt es einen Weg von a nach c?). In diesem Fall kann die Tiefensuche durch das iterative Deepening- eine Art begrenzte Tiefensuche ersetzt werden. Dabei wird der Suchbaum bei jeden Durchlauf um eine Ebene weiter durchsucht- die Vorgangs- weise ist ansonsten die selbe wie bei der Breitensuche. Bei dem Beispiel in Abb. 2 ergibt das:

Ebene 1: a
Ebene 2: a- > b, c, d
Ebene 3: a-> (b -> (e, f), c, d -> (g, h))
Ebene 4: a-> (b -> (e, f -> (i, j)), c, d -> (g, h))
Ebene 5: a-> (b -> (e, f -> (i, j -> (k, l))), c, d -> (g, h)))

Wird dabei eine "öfter" geklammerte Schicht verlassen, werden alle Knoten in diesen Klammern wieder verworfen.

Dieses Suchverfahren hat den Vorteil, dass es zwar universell Einsetzbar ist, und, falls vorhanden, auch eine Lösung findet, aber bei zunehmender Suchtiefe muss für jeden Durchlauf der Suchraum komplett neu aufgebaut werden.

[ Quelltext anzeigen ]


Aufgabe 5 (Breitensuche):

Zum Abschluss des Themas Suchverfahren wurde die Breitensuche behandelt, die durch das iterative Deepening simuliert wurde. Dabei wird wieder eine Ebene des Suchbaumes nach der anderen durchsucht- allerdings wird der Suchbaum nicht mehr bei jeden Durchlauf neu aufgebaut, sondern die bisher zurückgelegten Wege werden gespeichert. Dieses Suchverfahren ist bei grösseren Suchräumen zwar schneller, als iterative Deepening, dafür wird mehr Speicher verbraucht, da alle Knoten auf einer Ebene zugleich gespeichert werden.

Ebene 1: a
Ebene 2: a, b, c, d
Ebene 3: a, b, e, f, c, d, g, h
Ebene 4: a, b, e, f, i, j, c, d, g, h
Ebene 5: a, b, e, f, i, j, k, l, c, d, g, h
[ Quelltext anzeigen ]