Nach einer kurzen theoretischen Einführung in die Prädikatenlogik wurde schon die 1. Aufgabe mit Prolog gelöst.
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.
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.
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:
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.
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 ]