Logische Programmierung mit Prolog

Prolog
0. Grundlagen
Die Sprache Prolog wird nicht zufällig in Kapitel 2.03 zusammen mit Haskell
behandelt. Wir erinnern uns:
•
PHP, Java, Delphi und C# gehören zu den prozeduralen
Programmiersprachen.
Hier muss man einen Algorithmus angeben, der beschreibt, wie das Problem
zu lösen ist.
•
Prolog und Haskell sind logische bzw. funktionale Programmiersprachen. In
ihnen beschreibt man, was das Problem ist.
Prolog bedeutet Programmation en Logique. Zu Beginn der 70-er Jahre wurde sie
von Alain Colmerauer und Philppe Roussel entwickelt. Beide arbeiteten mit einem
Team an der Universität von Aix an der Frage, wie man sich mit Computern
(schriftlich) in französisch unterhalten kann.
Zu dieser Zeit gab es eigentlich schon eine logische Programmiersprache namens
Planner. Die offizielle Lesart, weshalb diese Sprache von Colmerauer und seinem
Team nicht benutzt und weiterentwickelt wurde ist: Planner baut auf der funktionalen
Programmiersprache Lisp auf. Und Lisp wollte die Gruppe auf keinen Fall benutzen.
Warum auch immer!
Die inoffizielle Lesart: Planner konnte kein französisch. Und in einem Land, in dem ein
Computer „ordinateur“, ein Walkman „baladeur“ genannt wird, scheint die Beziehung
zu Fremdsprachen eher problematisch zu sein. Bleibt nur die Frage, wie es der Begriff
„le weekend“ ins Dictionaire geschafft hat...;-)
Die Forscher dachten sich das so: Man erzählt dem Computer – pardon, dem
ordinateur etwas und dieser bewegt die Worte im Prozessor-Herz(t)e, um den
Menschen bestimmte Schlussfolgerungen zu liefern. Ein Beispiel:
Man gibt dem Rechner (das ist der ordinateur auf deutsch!) folgende Zeilen ein:
•
•
„Meine Frau hat am 24.12.2004 einen Jungen zur Welt gebracht.“
„Meine Frau hat am 18.04.2005 ein Mädchen zur Welt gebracht.“
Der Rechner gibt dann aus: „Du hast also zwischen dem 25.12.2004 und dem
18.04.2005 neu geheiratet!“
Gedacht war die Sprache Prolog für Expertensysteme, mathematische Logik,
automatisches Beweisen und all die anderen Anwendungen, die eine Wissensbasis
benötigen, innerhalb derer man Fragen stellen kann, die ein Mensch nur mit viel
1
Zeitaufwand beantworten kann, - wenn er sie, der großen Komplexität wegen,
überhaupt beantworten kann.
Prolog ist im Gegensatz zu allen anderen hier behandelten Sprachen eine
interaktive Sprache. Das heißt, die Programmentwicklung muss man sich eher als
Dialog vorstellen. Man gibt dem System das nötige Wissen und stellt dann eine
Frage. Möglicherweise merkt man dann, dass dem System weiteres Wissen fehlt.
Dieses gibt man dann ebenfalls ein und stellt erneut eine Frage....
In Kapitel 6 (Datenbanken) werden Sie auch lernen, dass Prolog eine relationale
Datenbank ist. Mit ihr werden Objekte und Relationen zwischen den Objekten
beschrieben.
Sie erinnern sich: Bei Haskell war die Formulierung eines Algorithmus sehr nah an
der natürlichen Sprache. Denken Sie etwa an das „Turm-Problem“. Dies ist in Prolog
in noch stärkerem Umfang gültig. Ein Beispiel:
„Das Meer ist türkis.“
In Prolog schreiben Sie:
tuerkis(meer).
grün(palmenblaetter).
weiss(sand).
graublau(himmel).
In der Sprache Prolog ist
beispielsweise meer
eine Konstante, die die
Eigenschaft (das
Prädikat) tuerkis hat.
Eine einfache Anfrage
wäre nun:
?- gruen(meer)
SWI-Prolog-Editor
Im Schulnetz ist der SWI-Prolog-Editor in der Version 4.14 installiert. Sie können sich
das Programm für zuhause aus dem Tauschverzeichnis kopieren oder hier
runterladen: http://lernen.bildung.hessen.de/informatik/swiprolog/setup.zip
Die drei Systemerweiterungen turtel, spur und zeichenterm gibt es hier
http://lakk.bildung.hessen.de/netzwerk/faecher/informatik/swiprolog/swiprolog.htm
Enpacken Sie die Dateien und legen Sie sie im Ordner library von SWI-Prolog ab.
Danach im Editor die Anweisung ?- make. eingeben.
SWI-Prolog ist mit seinem Konsolenmodus etwas für den Profi. Der SWI-PrologEditor von Gerhard Röhner hingegen eignet sich auch gut für Anfänger. Damit der
Editor so wie unten dargestellt aussieht, müssen Sie nach der Installation einige
Einstellungen vornehmen.
2
Mit diesem Schalter (Konfiguration) kommen Sie zum Konfigurationsfenster.
Hier sollten Sie vor allem das Quellverzeichnis wählen, in das Sie die
pl-Dateien ablegen werden. Sonst kann Prolog keine Compilierung des
Quelltextes vornehmen:
3
Wählen Sie zum Beispiel: H:\Prolog\Quelltexte
Im gleichen Fenster wählt man den Tab „Dokumentation“ und stellt dort den Dateipfad
zu den genannten Hilfen ein. Zunächst sind diese Felder rot unterlegt, weil bei der
Standardinstallation keine Hilfedateien abgelegt werden. Im Tauschverzeichnis
können Sie sich die nötigen Dateien holen. Falls Sie eine schnelle Internetverbindung
haben, können Sie hier auch die entsprechenden Internetadressen eintragen:
•
•
•
http://gollem.science.uva.nl/SWI-Prolog/Manual/Contents.html
http://gollem.science.uva.nl/SWI-Prolog/Manual/DocIndex.html
http://hcs.science.uva.nl/projects/xpce/UserGuide/
Um die Geschwindigkeit
zu erhöhen, werden die
bereits abgerufenen
Dateien lokal gespeichert
(gecacht). Auch in diesem
Fall sollten Sie Ihr
Homeverzeichnis H:
wählen, damit die Daten
nach dem Herunterfahren
erhalten bleiben.
Der SWI-Prolog-Editor,
der auf der letzten Seite
dargestellt ist, zeigt links ein Hilfefenster. Rechts daneben erkennt man das
eigentliche Prolog-Programm. In diesem Fall ist das Programm familie1.pl, mit dem
wir uns gleich beschäftigen werden, dargestellt.
Im unteren Feld findet die „Kommunikation“ mit Prolog statt. Hier kann man
beispielsweise seine Fragen, die die pl-Datei betreffen, stellen.
Sobald Sie sich einige Zeit mit diesem Editor beschäftigt haben, werden Sie selbst
entdecken, welche weiter Einstellungen günstig sind.
Zum Schluss nur noch ein Hinweis hierzu:
Im Test-Menu kann man den sogenannten „Trace-Modus“ einschalten. Ist er
eingeschaltet, so wird das Programm schrittweise ausgeführt. Das ist insbesondere
dann praktisch, wenn man einen Fehler aufspüren will.
Aufgabe 1
Öffnen oder installieren Sie SWI-Prolog-Editor. Nehmen Sie die oben ausgeführten
Einstellungen vor und erforschen Sie die weiteren Einstellungsmöglichkeiten.
4
1. Fakten
Damit Sie auch mit allen Fenstern arbeiten können, laden Sie das Mini-Programm
ist_mutter_von.pl (Tauschverzeichnis). Es enthält nur zwei Zeilen:
ist_mutter_von(christine,michael).
ist_muter_von(christine,maximilian).
Nun wählen Sie Start/consultieren (das Programm wird danach compiliert) und
stellen im unteren Fenster hinter ?- eine Anfrage.
Vermutlich werden Sie von den Fähigkeiten des Programms ist_mutter_von.pl nicht
besonders beeindruckt sein. Kein Wunder! Die Datenbank ist ja auch mehr als
bescheiden. Also muss eine etwas größere für weitere Forschungen erzeugt werden.
Wir nennen sie familie1.pl und sie sieht so aus:
%Funktor:
%Variable:
%Bedeutung:
%
%Funktor:
%Variable:
%Bedeutung:
%
%Funktor:
%Bedeutung:
%
ivom(X,Y) "Ist Vater oder Mutter von"
X,Y sind Menschen
ivom(X,Y) ist wahr,
wenn X Vater oder Mutter von Y ist.
w(X)
X sind Menschen
w(X) ist wahr,
wenn X eine Frau oder ein Mädchen ist
m(X)
m(X) ist wahr,
wenn X ein Mann oder ein Junge ist
ivom(christine,michael).
ivom(christine,max).
ivom(julian,max).
ivom(julian,maria).
ivom(max,paul).
ivom(max,paula).
ivom(paul,manuela).
ivom(paula,jana).
ivom(gernot,jana).
w(christine).
w(maria).
w(paula).
w(jana).
w(manuela).
m(michael).
m(max).
m(paul).
m(gernot).
m(julian).
%% Ende
Im obigen Datensatz werden Fakten beschrieben. Benötigt werden hierzu die Atome
(Konstanten), wie christine. Beziehungen zwischen den Atomen werden durch
Funktoren beschrieben. ivm/2 bedeutet beispielsweise, dass der Funktor ivm zwei
Argumente aufnimmt, w/1 nur eines.
5
Atome und Funktoren müssen mit einem kleinen Buchstaben beginnen.
(Ausnahme bei den Atomen: Statt paula kann man auch 'Paula' schreiben. )
Man erkennt unschwer, dass damit folgende Situation beschreiben wird:
Aufgabe 2
•
•
•
•
Wählen Sie im Editor Datei/neu und tragen Sie die obigen Daten ein.
Speichern Sie die Datei auf Ihrem Homeverzeichnis unter familie1.pl ab. Die
Text-Färbung nimmt der Editor, wie sie es ja schon von vielen anderen
Editoren gewohnt sind, der besseren Lesbarkeit wegen selbst vor.
Erweitern Sie jetzt die Familie nach Ihren Vorstellungen.
Was bedeutet das %-Zeichen zu Beginn an manchen Zeilen?
Weshalb sollte in den Fakten kein weiterer Funktor person/1 auftauchen, mit
der Bedeutung: p(X) ist wahr, wenn X eine Person ist?
Um Anfragen im unteren Fenster durchzuführen, muss man zuvor die Datei familie1.pl
compilieren. Das geht über Start/consultieren.
Aufgabe 3
Führen Sie mindestens folgende Anfragen durch:
1. Ist Christine „Vater oder Mutter von“ (ivom) Maria?
2. Ist Jan Vater oder Mutter von Paul?
3. Ist Paula „ein Mädchen oder eine Frau“ (w) ?
6
Vermutlich scheinen Ihnen diese Anfragen banal. Man muss ja nur selbst kurz einen
Blick auf die pl-Datei werfen,- dann hat man die Antwort!
Hier ist das sicher richtig. Hat die Datei aber mehrer Millionen Einträge, dann reicht
kein „kurzer Blick“ mehr.
Außerdem haben wir die Möglichkeiten durch Anfragen noch nicht kennengelernt.
Hierzu einige Beispiele:
Wenn Sie alle Kinder von Christine erfragen wollen, dann geht das so:
„Person“ ist eine Variable der Anfrage. Sie werden
im Gegensatz zu den Atomen (in Delphi würde
man Konstante sagen) immer groß geschrieben!
Wenn man auf Enter drückt, dann wird zunächst
nur ein Kind ausgegeben. Durch weiteres Drücken
auf Enter werden alle weiteren Kinder ausgeben.
Sind alle genannt, so erscheint in der letzten Zeile
ein „No“.
Sehr praktisch bei
mehreren Lösungen
ist die Funktion
findall.
Nur die Töchter von Christine
bekommt man durch eine
konjunktive Anfrage (links). Das
Komma bedeutet "und zugleich".
Testen Sie, ob die Reihenfolge eine
Rolle spielt!
Will man die Anfrage ist Vater oder Mutter von präzisieren, indem man etwa genauer
wissen will, ob das Prädikat ist Vater von zutrifft, so könnte man zunächst auf den
Gedanken kommen, wie weiter oben Relationen ist Vater von bzw. ist Mutter von zu
definieren.
Das wäre allerdings äußerst ungeschickt, denn diese Informationen stecken ja schon
in unserer „Datenbank“.
Beispielsweise durch die konjunktive Anfrage
links bekommen wir die Auskunft, wer Vater
von Maxi ist, - ohne ist Vater von definiert zu
haben.
7
2. Regeln
Dennoch wäre es natürlich leichter, wenn man mit einer einfachen Anfrage zum Ziel
kommen könnte. Und das geht so:
iv(V,K):ivom(V,K),
m(V).
(„Kopf“ der Regel)
(„Rumpf“ der Regel)
Man spricht hier von einer Prolog-Regel: Oben ist also die
Regel für ist Vater von aus den vorhanden Relationen
abgeleitet. Eine Regel wird mit den Zeichen :- nach dem zu
Definierenden eingeleitet.
Unter Klauseln versteht man die Gesamtheit aus Fakten und Regeln.
Aufgabe 4
•
•
•
•
•
•
•
•
•
Erstellen Sie eine Regel im/2 "ist Mutter von" nach obigem Vorbild.
Weshalb kann man die Relation ist verheiratet mit nicht aus der vorliegenden
Datenbank ableiten?
Laden Sie die erweitererte Familien-Datenbank familie3.pl (grafische
Darstellung siehe Bild unten) in den SWI-Editor.
Ergänzen Sie eine Relation sindverh/2 "sind verheiratet" nach Ihren
Vorstellungen.
Bedenken Sie aber, dass gilt: Wenn A mit B verheiratet ist, dann ist auch B mit
A verheiratet! Diese Eigenheit muss sich in der Regel wiederfinden. Hierzu ein
Tipp: Wenn die einzelnen Bedingungen einer Regel durch Strichpunkt
getrennt sind, dann bedeutet dies ein logisches oder. Sind sie durch ein
Komma getrennt, dann ist dies ein logisches und.
Erstellen Sie nun eine Regeln für isva/2 "ist Schwiegervater von".
Erstellen Sie eine Regel für igvv/2 "ist Großvater von".
Erstellen Sie eine Regel für hkk/1 "hat keine Kinder".
Wie lautet eine einfache Regel für sindgeschw/2 "sind Geschwister"? Welches
Problem gibt es bei einer Anfrage sindgeschw(X,Y). ?
Zum Schluss: Wie prüft man ischwa/2 "ist Schwager von" ?
Beachten Sie, dass es hier zwei Möglichkeiten gibt:
Im obigen Beispiel ist Jan ein Bruder von Gernot und Sebastian ein Bruder von
Paula. Aber nur in der Kombination Sebastian-Gernot ist die Beziehung
ischwa/2 symmetrisch!
8
Und so sieht Familie3 aus:
Einige werden die Regel für hkk/1 "hat keine Kinder" so aufgeschrieben haben:
hkk(X):(m(X);w(X)),
not(ivom(X,W)).
Prolog gibt dann eine Warnung aus: [W] Singelton variable. Das bedeutet, dass die
Variable W nur einmal in der Regel vorkommt und somit in keiner Beziehung zur
Variablen X steht. Die Ausgabe dieser Warnung kann man vermeiden, wenn man für
statt der Variablen W die anonyme Variable _W verwendet. Also:
hkk(X):(m(X);w(X)),
not(ivom(X,_W)).
Wie kann eine Regel für esg/1 "Eltern sind geschieden von" formuliert werden?
Ist dies eine Lösung?
esg(X):ivom(Y,X),
ivom(Z,X),
Y\==Z,
not(sindverh(Y,Z)).
Stellt man eine Anfrage ?- esg(X). so bekommt man wie bei sindgeschw/2 manche
Antworten mehrfach. Das ist zwar nicht falsch, aber lästig. Verstehen kann man die
Mehrfachnennungen erst wenn man weiß, wie Prolog arbeitet. Damit beschäftigen wir
uns im 4.Kapitel. Abstellen lässt sich das Verhalten erst, wenn man die Ergebnisse in
Listen speichert und so überprüfen kann, ob das neue Element schon vorhanden ist.
Damit Sie nicht
glauben, das Prolog
nur für die Kontrolle
von Verwandtschaftsverhältnissen zu
gebrauchen ist, hier
eine ganz andere
Anwendung:
9
Oben ist eine vereinfachte Landkarte dargestellt. Die Frage: Kann man diese Karte
mit drei Farben einfärben, so dass keine gleichen Farben nebeneinander liegen?
Wenn nein: Reichen vier Farben?
Natürlich kann man das Problem auch ohne Prolog relativ leicht lösen. Das liegt
hauptsächlich daran, dass wir bewusst einen einfachen Fall gewählt haben, um die
nötigen Eingaben nicht zu umfangreich werden zu lassen.
So kann man den Sachverhalt eingeben (bei vier Farben z.B. farbe(gelb) hinzufügen.
Das Prädikat \= bedeutet „ sind ungleich“):
%% Einfärben von Landkarten
farbe(blau).
farbe(gruen).
farbe(rot).
farbe(gelb).
einfaerbung(F1,F2,F3,F4,F5,F6,F7):farbe(F1),farbe(F2),farbe(F3),farbe(F4),farbe(F5),farbe(F6),farbe(F7),
F1\=F2,F1\=F3,F1\=F4,F1\=F5,F1\=F6,F2\=F3,F2\=F4,F3\=F6,F3\=F7,F4\=F5,
F5\=F6,F6\=F7.
Eine Anfrage mit vier Farben muss eine Lösung liefern (Vier-Farben-Satz!). Prolog
gibt alle möglichen Lösungen aus. (Wieviele? Allein 60 sind es, die für Feld 1 die
Farbe blau festlegen!!).
Auf die Anfrage ?- einfaerbung(F1,F2,F3,F4,F5,F6,F7).
bekommt man als erste Antwort die Lösung rechts.
Um weitere Lösungen zu erhalten, drückt man die Entertaste.
Einfacher geht es, wenn man bis zur letzten Anzeige die w-Taste
drückt.
Aber auch das ist zeitraubend. Deshalb verfassen wir eine neue
Regel, die Prolog dazu zwingt, immer weitere Druckbefehle zu
erzeugen. Entscheidend ist dabei der Eintrag fail, der, wie man im nächsten Kapitel
erfahren wird, dafür sorgt, dass Prolog nach immer weiteren Möglichkeiten sucht, bis
es keine mehr gibt: (nl erzeugt eine "new line"). Auch wenn es danach aussieht: Dies
ist keine Schleife im prozeduralen Sinn! Besser beschrieben wird der Vorgang durch
den umgangssprachlichen Aufruf: "Such weiter, bis nichts mehr gefunden wird!"
alleEinfaerbungen(F1,F2,F3,F4,F5,F6,F7):(
einfaerbung(F1,F2,F3,F4,F5,F6,F7),
print(F1),print(' '), print(F2),print(' '),
print(F3),print(' '), print(F4),print(' '),
print(F5),print(' '), print(F6),print(' '),
print(F7),print(' '), nl,
fail
;
true
).
10
3. Rekursion
Zurück zu unserem Stammbaum. Wie würden Sie die Prozedur ige ist Großelter von
(also ist Großvater oder Großmutter von) in Prolog implementieren? Und welche
Regel erstellen Sie für die Prozedur iuge ist Urgroßelter von ?
Eine Möglichkeit wäre:
ige(X,Y):- ivom(X,Z), ivom(Z,Y).
% ist Großelter von
iuge(X,Y):- ivom(X,Z), ige(Z,Y).
% ist Urgroßelter von
Damit wird auch die Erweiterung zu iuuge ist Ururgroßelter von recht einfach:
iuuge(X,Y):- ivom(X,Z), iuge(Z,Y).
% ist Ururgroßelter von
So könnte man beliebig fortfahren. Die Implementierung der Prozedur ivorfahr ist
Vorfahr von würde uns so nicht gelingen. Wie die Überschrift erkennen lässt, muss
das Problem „Vorfahr“ durch eine Rekursion gelöst werden:
ivorfahr(X,Y):- ivom(X,Y).
ivorfahr(X,Y):- ivom(X,Z), ivorfahr(Z,Y).
Die erste Zeile der Rekursion ist, wie auch schon in Haskell, der Induktionsausstieg.
Man braucht diese Zeile, damit es keine Dauerschleife gibt.
Im nächsten Kapitel werden wir untersuchen, wie genau Prolog zum Beispiel die
Anfrage ?- ivorfahr(margit, michael) beantwortet. Zuvor aber gehen wir die
Rekursion selbst durch. Ein möglicher Weg wäre:
ivorfahr(margit, thomas) ist wahr, denn ivom(margit, thomas) ist wahr.
Damit wird das Problem auf ivorfahr(thomas, michael) reduziert.
Das klappt wieder nicht direkt, denn ivom(thomas, michael) ist falsch.
Aber ivorfahr(thomas, christine) klappte, weil ivom(thomas, christine) wahr ist.
Damit wird das Problem auf ivorfahr(christine, michael) reduziert.
Und das ist wahr, denn es gilt ivom(christine, michael).
Die Anfrage ?- ivorfahr(margit, michael) wird also mit true beantwortet
Aufgabe 5
Zeigen Sie, dass es auch andere "Wege" gibt, die bei der obigen Anfrage zur Antwort
"true" führen.
Veranschaulichen Sie den Sachverhalt an einer Skizze.
In wie fern ist die erste Zeile der obigen Regel ein "Ausstieg" aus der Rekursion?
Was wäre passiert, wenn man es oben für Z nicht mit thomas, sondern mit martin
versucht hätte?
Wie muss Prolog vorgehen, um auch alle Möglichkeiten testen zu können?
11
Aufgabe 6
Notieren Sie alle Fakten, die zu dem
Bild der auf einem Stapel liegenden
Klötzchen gehören:
Es gibt drei Stapel x, y und z
4 liegt auf x, 3 liegt auf 4 etc.
Formulieren Sie eine (rekursive) Regel
liegtUeber(X,Y) mit der Bedeutung : X
liegt über Y.
Ein weiteres Beispiel:
In einer großen Stadt haben die
Planer die Busverbindungen so
angelegt, dass man vom Bahnhof
(1) mit nur einem Ticket zu den
Sehenswürdigkeiten (2-11)
fahren kann, falls man immer nur
die durch Pfeile markierten
Verbindungen benutzt. Ganz
nach dem Motto: Wer sparen will,
muss auch nicht alles sehen....
Ein Reisender mit PrologKenntnissen möchte die
Gegebenheiten so in Prolog
implimentieren, dass er nur noch
eingeben muss: fahre(1,5) und sein prologfähiger
Organizer gibt die Antwort Yes oder No
Zunächst muss man Prolog die Gegebenheiten
mitteilen.
buslinie(1,2).
bedeutet, dass es eine Busverbindung auf der
„Spar-Buslinie“ von 1 nach 2 gibt.
fahre(X,X).
drückt aus, dass es auch erlaubt ist, an der Stelle X
zu bleiben.
fahre(X,Y).
ist – wie erwartet- rekursiv definiert. Beachten Sie,
dass dies hier nur funktioniert, weil es keine
Rückwege gibt. Mit diesen würde die Rekursion
unweigerlich in einer Schleife landen.
Gespeichert wird alles unter sparbuslinie.pl
12
Beispiel einer Anfrage:
Aufgabe 7
Erweitern Sie die Anzahl der Sehenswürdigkeiten und fügen Sie entsprechende
Busverbindungen hinzu. Achten Sie darauf, dass keine Rückwege und damit
mögliche Schleifen entstehen. Implementieren Sie die neue Situation in Prolog.
Aufgabe 8
Prolog ist als Programmiersprache
sicher nicht erste Wahl, wenn es um
umfangreiche Rechnungen geht.
Dennoch stellt die Sprache
zahlreiche arithmetischer Operatoren
und Funktionen zur Verfügung. Um
mehr darüber zu erfahren, rufen Sie
das Hilfe-Menu auf und geben Sie
als Suchbegriff "Arithmetic" ein.
Wählen Sie den obersten Eintrag in
der Ergebnis-Liste. Die meisten
Bezeichnungen sind selbsterklärend.
Es gibt aber auch einige
Besonderheiten.
• Welche Operatoren und
Funktionen gibt es?
• Worin besteht der
Unterschied zwischen is und
=:= ?
• Welche drei numerische
Typen gibt es?
Rekursionen sind nicht einfach zu verstehen. Daher sollen weitere Beispiele
behandelt werden.
13
Beispiel Fakultät
Unter n! versteht man 1*2*3*...*(n-1)*n, also gilt beispielsweise 5! = 120.
Der GTR (Menu Math/PRB/ ! ) zeigt die Fakultät gerundet bis 69 an. Danach
bekommt man eine Fehlermeldung. Warum das so ist und weshalb Prolog dies viel
besser kann, erfährt man hier:
% fakultaet/2
% fakultaet(N,F) ist wahr, wenn N! = F
%Faktum
fakultaet(0,1).
%Regel
fakultaet(N,F):N>0,
N1 is N-1,
fakultaet(N1,F1),
F is N * F1.
Aufgabe 9
•
•
•
Erstellen Sie nach den obigen Angaben das Programm fakultaet.pl und prüfen
Sie es durch folgende Anfragen: ?- fakultaet(5,F) , ?- fakultaet(250,F) etc.
Gehen Sie die Anfrage ?- fakultaet(3,F) Schritt für Schritt durch. Wie kommt
das Ergebnis 6 zustande?
Wann ist die Rekursion beendet?
Beispiel Fibonacci-Zahlen
Kaum eine ander Folge von Zahlen hat so viel Aufmerksamkeit erfahren wie diese:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Können Sie die Folge fortsetzten?
Ursprünglich hatte Fibonacci die Folge durch das Wachstum einer
Kaninchenpopulation veranschaulicht. Es gelten genau drei Regeln:
1. Nach jedem Monat wirft ein Paar ein weiteres Paar Kaninchen.
2. Erst ab dem zweiten Lebensmonat bekommt ein neugeborenes Paar
Nachwuchs.
3. Alle Tiere befinden sich in einem abgeschlossenen Raum und leben unendlich
lange.
Aufgabe 10
Versuchen Sie die oben begonnene Zahlenfolge mit den drei Regeln in Einklang zu
bringen. Wie lauten die folgenden Bestandzahlen von Kaninchen-Paaren?
Versuchen Sie eine rekursive Regel mit Abbruchbedingung (Induktionsanfang) zu
formulieren.
14
Informieren Sie sich hier zum Thema Fibonacci-Zahlen:
http://www.matheprisma.uni-wuppertal.de/Module/Rekurs/index.htm
http://www.youtube.com/watch?v=bE2EiI-UfsE
Eine erste Lösung könnte so aussehen:
% fibonacci1
% fibo/2
% fibo(N,F) ist wahr, wenn F die N-te Fibonacci-Zahl ist
% Fakten
fibo(0, 1).
fibo(1, 1).
%Regel
fibo(N, F) :N > 1,
N1 is N - 1, N2 is N - 2,
fibo(N1, F1), fibo(N2, F2),
F is F1 + F2.
Viel Freude haben wir an dieser Lösung nicht, denn schon bei der Anfrage
?- fibo(40,F). bekommt man einen Stack-Überlauf, ein Zeichen dafür, das wir den
Rechner überfordert haben.
Aufgabe 11
•
•
•
•
Erstellen Sie nach den obigen Angaben das Programm fibonacci.pl und prüfen
Sie es durch folgende Anfragen: ?- fibo(5,F) , ?- fibo(30,F) etc.
Gehen Sie die Anfrage ?- fibo(3,F) Schritt für Schritt durch. Wie kommt das
Ergebnis 3 zustande?
Wann ist die Rekursion beendet? Weshalb ist die Anfrage ?-fibo(40,F). mit so
viel Rechnung verbunden?
Weshalb hatten wir in fakultaet dieses Problem nicht?
Immerhin erlaubt uns dieses Beispiel, deutlich zu erkennen, dass nicht alle rekursiv
aussehenden Aufgaben auch rekursiv gelöst werden sollten. Die 40.-te FibonacciZahl mit einer Schleife auszurechnen, erledigt der Rechner in einem Bruchteil einer
100-tel Sekunde!
Beispiel Turm von Hanoi
Die Spielregel ist einfach:
Lege die Scheiben einzeln so um, dass sie
am Ende wieder genau wie jetzt auf einem
anderen Stab daliegen. Dabei darf nie eine
größere Scheibe auf einer kleineren liegen.
15
Hier können Sie es einmal selbst versuchen:
http://www.matheprisma.uni-wuppertal.de/Module/Rekurs/index.htm
Aufgabe 12
•
•
Zeigen Sie dass man mit 7 Schritten
einen Dreier-Turm nach der obigen
Regel umsetzten kann.
Weshalb sind nun noch genau 8 Schritte
nötig, die Aufgabe zu lösen? (Das Bild
rechts ist dabei sehr hilfreich!).
Wer die obige Aufgabe gelöst hat, erkennt, dass man das Problem mit vier Scheiben
auf das Problem mit drei Scheiben zurückführen kann. Verallgemeinert heißt dies,
wenn man das Problem für n Scheiben gelöst hat, ist es auch für n+1 Scheiben
gelöst. Nehmen wir an, man benötigt x Züge für n Scheiben. Dann benötigt man
offensichtlich 2x +1 Züge für n+1 Scheiben.
Wenn man die Stäbe von 1 bis 3 durchnummeriert, und ein Turm von n+1 Scheiben
von Turm 1 auf Turm 3 gebracht werden soll, so muss man lediglich einen Turm von n
Scheiben auf Turm 1 auf Turm 2 transportieren. Dann die letzte Scheibe auf Turm 3
setzten und nun die n Scheiben auf Turm 2 nach Turm 3 transportieren. Das ist aber
ganz eindeutig eine Rekursions-Anweisung: Löse das Problem für 5 Scheiben, indem
du das Problem für 4 Scheiben löst. Löse das Problem für 4 Scheiben, indem du das
Problem für 3 Scheiben löst.... Am Ende muss man nur das Problem für eine Scheibe
lösen - und das ist nun wirklich kein Problem!
Aufgabe 13
Überprüfen Sie den folgende Quellcode dahingehend, ob er dem oben beschriebenen
rekursiven Algorithmus gerecht wird. Kontrollieren Sie dabei vor allem die Regel
verschiebe(N,Start,C,Ziel):% Türme von Hanoi
% hanoi/1 : hanoi(N) gibt die minimale Zugzahl für einen Turm mit N Scheiben
aus.
% verschiebe/4 : verschiebe(N, links, mitte, rechts)
hanoi(AnzahlScheiben):verschiebe(AnzahlScheiben, links, mitte, rechts).
verschiebe(0,_,_,_).
%Abbruchbedingung: keine Scheibe zu verschieben
verschiebe(N,Start,C,Ziel):M is N-1,
verschiebe(M,Start,Ziel,C),
eineScheibe(Start,Ziel),
verschiebe(M,C,Start,Ziel).
eineScheibe(Von,Nach):print('Bewege Scheibe von '), print(Von), print(' nach '), print(Nach),
nl.
16
4. Wie Prolog arbeitet
Die Situation ist in einem Punkt völlig klar: Das Prolog-"Programm" besteht aus
Klauseln (Fakten und Regeln) und der Anwender stellt eine Frage, die Prolog mit Hilfe
der Klauseln beantworten soll. Man kann sich daher die Klauseln als eine
Wissensbasis vorstellen. Hinzu kommt, dass Prolog in der Lage sein soll, logische
Schlussfolgerungen aus den Klauseln zu ziehen. Das klingt zunächst ziemlich
abenteuerlich, denn die Logik betrachten wir doch als eine allein dem Menschen zur
Verfügung stehende Fähigkeit. Ein großer Irrtum! Logik basiert auf Axiomen und
Regeln, die man ohne Ausnahme in einen Algorithmus packen kann.
Man kann zeigen, dass beim Bearbeiten einer Anfrage drei verschiedene Methoden,
Resolution, Unifikation und Backtracking, notwendig sind, um eine korrekte
Antwort zu bekommen. In diesem Kapitel werden wir mit verschiedenen Techniken
Prolog beim Beantworten einer Anfrage "über die Schulter schauen", und dabei
lernen, was man unter den drei Begriffen versteht.
ProVisor
Das Programm Provisor ist ein DOS-Programm zur Visualisierung einer PrologAnfrage, das aber unter Windows XP problemlos (im DOS-Modus) funktioniert.
Beachte: Dateinamen dürfen in
DOS nur maximal 8 Zeichen
haben. (Spätere Versionen von
Windows benötigen eine "DOSBox". In jedem Fall muss aber der
Pfad in der Datei PROVISOR.PTH
angepasst werden.) In den Ordner
BSP legen wir die Prolog-Datei
familie1.pl. (Siehe Seite 5). Dann
wird PROVISOR.EXE durch
Doppelklick gestartet. Wenn alles
gut geht, öffnet sich ein etwas
spartanisches DOS-Fenster. Durch
Drücken der Taste F4 kann man
alle im Beispiel-Ordner
vorhandenen pl-Dateien
konsultieren.
Wir geben oben familie1.pl ein.
Im unteren Fenster erfolgt die Anfrage ?- ivv(max,Y). Dann erscheint ein erstes Bild:
Anfrage-Knoten
Funktor: ivv
Variablen-Leiste
Hier können Variable instanziert werden. (Schraffiert sind die
Felder, weil sie noch nicht vom Interpreter "besucht" wurden.
17
Resolution:
Der Funktor ivv wird in Teilziele aufgelöst.
Die beiden durchgezogenen Strecken bedeuten
"und zugleich".
X_1 und Y_1 sind die (auch für die Teilziele
benötigten) Variablen.
Unifikation:
Es wird unter den Fakten ein passendes
Gegenstück gesucht.
Gestrichelte Strecken bedeuten "oder".
18
Nicht-passende und überprüfte Fakten bekommen einen "Deckel" verpasst. Das
passende Faktum ivom(max,paul) bewirkt, dass die Variable Y nun mit paul belegt
wird:
Nun muss noch überprüft werden, ob m(max) gilt:
Gefundene Lösungen werden gestrichen:
19
Backtracking: Nach der gefundenen Lösung wird zum letzten Knoten
zurückgesprungen und nach noch offenen Möglichkeiten gesucht. Nächste Fundstelle
für die Belegung von Y ist paula
Kontrolle, ob m(max) erfüllt werden kann:
20
Es nützt leider nichts, dass dies schon beim letzten Mal beim Treffer paul überprüft
wurde. Gibt es einen neuen Treffer, werden bei jedem Mal alle Teile der Regel
überprüft.
Nach erneutem Backtracking wird erkannt, dass es keine weiteren Lösungen mehr
gibt:
Aufgabe 14
•
•
•
Führen Sie mit FAMILIE1PLl in Provisor die Anfrage ?- im(dagmar,Y). durch.
Überprüfen Sie, wann Resolution, wann Unifikation und wann Backtracking
durchgeführt wird.
Verwenden Sie FAMILIE6PLl und stellen im Provisor die Anfrage
?- sindgeschw(michael,Y). Erstellen Sie zur besseren Übersicht einen
passenden Und-Oder-Baum. (Tipp: Unter Visualisierung/ Übersichtsbaum kann
man den Baum ohne Beschriftung anzeigen lassen!)
Konsultieren Sie unser erstes Faktuläts-Programm, hier FAKULT.PL genannt,
und stellen Sie die Anfrage ?- faktultaet(3,F). Beobachten Sie den Ablauf im
Einzelschritt-Modus und lassen Sie sich nach dem ersten Treffer den
Übersichtsbaum anzeigen.
trace-Modus
Die visuelle Provisor-Methode eignet sich natürlich nur für nicht zu umfangreiche
Fakten. Bereits bei 100 Fakten ist die Übersicht dahin.
Aber auch in einer logischen Programmiersprache muss es eine Art "Debug-Modus"
geben. Und in der Tat kann man jede Anfrage im sogenannten trace-Modus
durchführen. Den erreicht man entweder über Test / Trace ein aus oder über das
Brillen-Ikon.
21
Die Funktionsweise des trace-Modus kann durch folgende Zeichnung (Boxenmodell)
am Beispiel "ist Mutter von" veranschaulicht werden:
Man kann die Anfrage "ist Mutter von" ( im/2 und im2/2 in familie6.pl) auf zwei
verschiedene Arten stellen:
im(M,K):ivom(M,K),
w(M).
% In diesem Fall wird zuerst überprüft, ob M Vater oder
% Mutter von K ist. Danach überprüft man, ob M weiblich
im2(M,K):w(M),
ivom(M,K).
% Hier ist die Reihenfolge der Anfragen gegenüber oben
% vertauscht. Was ist in der Regel schneller?
Für uns macht es keinen Unterschied, ob wir nach der ersten oder zweiten Methode
vorgehen. Es wird ja der gleiche Sachverhalt beschrieben.
erkennt man, dass die beiden Wege durchaus verschieden lang dauern können- und
damit also in Prolog anders abgearbeitet werden:
(Die Unify-Zeile erhält man nur, wenn man zuvor die Anfrage ?- visible(+all). stellt.)
22
Aufgabe 15
Versuchen Sie anhand der obigen trace-Protokolle herauszubekommen, wie Prolog
arbeitet. Verwenden Sie hierzu auch das oben dargestellte Boxenmodell.
Weshalb wäre bei einer sehr großen Datenbasis das untere Verfahren langsamer?
Sobald die Anfragen etwas komplexer werden, kann man sehr gut das sogenannte
Backtracking (Zurücksetzen) beobachten.
Als Beispiel dient uns zunächst die Anfrage: "Ist Paul ein Schwager von Gernot?"
Prolog wird die erste Möglichkeit testen: "Ist Paul ein Bruder von Z und sind Z und
Gernot verheiratet?" (sindgeschw(X,Z),m(X),sindverh(Z,Y));
Dabei muss sindgeschw(paul,Z) solange mit den vorhandenen Daten verglichen
werden, bis sich eine Möglichkeit für Z ergibt (Das Verfahren zur Unifizierung nennt
man matching).
Paula erfüllt diese Bedingung. Paul ist männlich m(X),- die nächste Bedinung ist also
ebenfalls erfüllt. Allerdings muss Paula mit Gernot verheiratet sein sindverh(Z,Y).
Dies ist der Fall und Prolog kann ein Yes ausgeben:
Erheblich mehr Mühe machen wir dem Programm, wenn wir umkehrt anfragen:
"Ist Gernot ein Schwager von Paul?"
Die erste Möglichkeit greift hier nicht und so muss Prolog nach vielen Irrungen und
Wirrungen mit der zweiten Möglichkeit von vorn anfangen.
Ganze 167 Zeilen hat das Protokoll dieses mal! Probieren Sie es aus!
Sofort taucht die interessante Frage auf: Könnte man die zweite Möglichkeit nicht
einfacher überprüfen: Also statt sindgeschw(Z,Y),sindverh(X,Z),m(X) besser:
sindgeschw(X,Z),m(X),sindverh(Z,Y) wie im ersten Fall, aber mit der
Zusatzbedingung: m(Y) ? Klar, denn wenn X ein Schwager von Y ist, dann gilt doch
die Umkehrung nur, wenn Y männlich ist,- oder? Ihre Antwort?
23
Der trace-Modus wurde sicher nicht implementiert, damit der Benutzer die „Mühen“
beobachten kann, die Prolog hat, um eine Anfrage zu beantworten. Der eigentliche
Sinn ist natürlich die Fehlersuche zu unterstützen!
ivorfahr(X,Y):ivorfahr(X,Y):-
ivom(X,Y).
ivom(X,Z), ivorfahr(Z,Y).
Um die Rekursion etwas besser zu verstehen, kann man die Anfrage
ivorfahr(heike, heimo). im trace-Modus durchlaufen lassen (sieh Screenshot
rechts).
Prolog stellt hier zunächst fest,
dass Heike keine Mutter oder
Vater von Heimo ist. Da dies
nicht der Fall ist, ergibt die
Prüfung ein Fail.
Danach wird nach der zweiten
Zeile geprüft, ob Heike Vater
oder Mutter von irgend
jemandem ist.
Die Suche führt zu Richard.
Das ist allerdings eine
Sackgasse (weshalb?). Um das
zu erkennen, benötigt das
Programm 13 Zeilen.
Schließlich findet es den Weg
über Simon...
Prüfen Sie so, ob Margit ein
Vorfahr von Justin ist.
Schon bei dieser kleinen
Faktenmenge ist es sehr
schwierig einen Überblick, vor
allem bei Rekursionen, zu
behalten. Wünschenswert
wäre, dass der besseren
Lesbarkeit wegen, die Zeilen, je
nach Tiefe der Resolution
eingerückt sind. Genau dies
leistet der Funktor spur/1
24
Spuren
Die gleiche Anfrage wie oben (auf dem gleichen Datenmaterial) sieht deutlich
übersichtlicher aus:
Benötigt wird hierzu die Datei spur.pl , die man hier runterladen kann:
http://lakk.bildung.hessen.de/netzwerk/faecher/informatik/swiprolog/swiprolog.html
Abgelegt wird sie im library-Verzeichnis. Danach gibt man zum Einbinden im
Anfrageabschnitt des Editor noch make. ein. Danach ist dem Interpreter spur/1
bekannt.
Aufgabe 16
•
•
Beobachten Sie die Abarbeitung der Anfrage ?- spur(liegtUeber(X,x)).
(aufgabe6Stapel.pl)
Vergleichen Sie mit der Ausgabe bei der gleichen Anfrage, - aber im traceModus.
Graphischer Debugg-Modus
Wenn man im Menu Test einen Haken bei GUI-Tracer setzt, dann öffnet sich im traceModus ein Fenster, das noch etwas mehr Überblick erlaubt:
25
Im Teilfenster Call Stack wird der aktuelle Aufruf angezeigt. Das Hauptziel steht oben
und neue Teilziele werden unten eingefügt. Rechts (hier mit Pfeil) sind Teilziele zu
erkennen, für die es noch andere Lösungen geben kann. Klickt man auf die Ziele oder
Teilziele, so wird im unteren Fenster der zugehörige Quellcode angezeigt.
Im Teilfenster Bindings wird die aktuelle Belegung der Variablen dargestellt.
Nun haben Sie vier Möglichkeiten kennengelernt, Prolog "auf die Finger zu schauen".
Auch wenn besonders die letzten drei Möglichkeiten das Debuggen eines Programms
unterstützen, - Ziel dieses Kapitels war das Beweis-Prinzip von Prolog mittels
Resolution, Unifikation und Backtracking nachzuvollziehen.
Das folgende mit Prolog zu lösende Rätsel dient dann auch dazu, ProVisor, trace,
spur und GUI-trace erneut in Aktion zu beobachten.
Zahlen-Rätsel
Jeder Buchstabe vertritt eine andere Ziffer. Finden Sie alle
Lösungen. Kleiner Tipp: "//" ist die Ganzzahl-Division. Beispiel:
41 // 9 ergibt 4. Hingegen für 41 mod 9 erhält man 5
Die Lösung erhält man, wenn man die Fakten stur genau so
hinschreibt, wie sie dastehen.
Zunächst werden die vorkommenden ziffern-Variablen
formuliert:
ziffer(L),ziffer(G),ziffer(A),ziffer(N),ziffer(F),
Und nun muss festgehalten werden, dass alle verschieden sein müssen:
L\=G,A\=L,A\=G,N\=L,N\=G,N\=A,F\=L,F\=G,F\=A,F\=G,
26
Eine Addition beginnt man mit den letzten Ziffern. Und das sind die Fakten dieser
linken Spalte:
S1 is L+L,G =:= S1 mod 10,Ue1 is S1//10,
Hier steht, dass es zwei Ziffern L und G gibt, die verschieden sein müssen. Dann wird
die Summe L + L gebildet. G ist dann die Summe mod 10, also einfach die Einerziffer.
Der Übertrag Ue1 ist die Summe // 10, also die Zehnerziffer.
Beachte: "is" ist der Auswertungsoperator, "=.=" bedeutet hingegen numerische
Gleichheit.
Und nun die zweite Spalte (von links).
S2 is A+A+Ue1,N =:= S2 mod 10,Ue2 is S2//10,
Man muss hier nur beachten, dass die Summe auch den Übertrag von oben enthält.
Die dritte Spalte (hier ist der Übertag gleich F):
S3 is A+A+Ue2,A =:= S3 mod 10,F =:= S3//10.
Zwei Dinge fehlen noch:
• Es gibt die Ziffern 0, 1, 2, ..... 9
• Die Regel für loesung(A,F,G,L,N) muss durch die drei obigen Zeilen definiert
werden.
Das erledigen wir so:
ziffer(0).
ziffer(1).
ziffer(2).
ziffer(3).
ziffer(4).
ziffer(5).
ziffer(6).
ziffer(7).
ziffer(8).
ziffer(9).
loesung(A,F,G,L,N):-
Hinter den Regelkopf müssen dann nur noch die drei Zeilen von oben eingetragen
werden. Welche Lösungen gibt es? Wie sieht die Anfrage im trace- oder spur-Modus
aus?
Aufgabe 16
•
•
•
Lösen Sie mit Prolog dieses Zahlenrätsel:
Finden Sie eine Lösung, bei der M = 1 ist.
Wenn Sie wie im obigen Beispiel vorgegangen
sind, dann braucht Prolog sehr viel Zeit für die
Lösung. Vergleichen Sie Ihre Lösung mit der
Lösung buchstabenraetselMONEYschnell.pl im Tauschverzeichnis. Weshalb
ist diese Lösung, die ja nur Umstellungen in der Regel vornimmt, so viel
schneller? Verwenden Sie hierzu den spur-Modus.
27
Aufgabe 17
Den größten gemeinsamen Teiler zweier natürlicher Zahlen a und b (ggT(a,b)) kann
man nach folgendem Algorithmus bestimmen:
ggT(a,b) = a ; falls a = b
ggT(a,b) = ggT(a-b,b); falls a > b
ggT(a,b) = ggT(a, b-a); falls a < b
Beispiel: ggT(49,56) = ggT(49, 7) = ggT(41,7) = ...= ggT(7,7) = 7
Schreiben Sie eine rekursive Regel in Prolog, mit der man den ggT zweier beliebiger
natürlichen Zahlen berechnen kann.
Beispielanfrage: ggT(163251,175001400,E):(E steht für Ergebnis)
Beobachten Sie die Lösung von ggT(163251, 175001400,E) im spur-Modus.
28
5. Listen
Wie oben schon erwähnt, gibt es keine Schleifen in Prolog. In diesem Kapitel wird
gezeigt, dass Listen in einer logischen Programmiersprache die Schleifen einer
prozeduralen Sprache ersetzen.
Schauen wir uns das Programm spar_buslinien nochmal an. Etwas enttäuschend ist
die Tatsache, dass man nur mitgeteilt bekommt, ob der geplante Weg möglich ist oder
nicht. Viel besser wäre doch, wenn man eine oder mehrere Listen von möglichen
Wegen bekäme.
Unter Listen werden hier Datenstrukturen mit variabler Länge verstanden. Es gibt sie
sowohl in prozeduralen (z.B. C#) aber auch in funktionalen Programmiersprachen
(z.B. Haskell). In Prolog allerdings sind sie von grundlegender Bedeutung. Etwas
vereinfacht ausgedrückt: Ohne Listen keine logische Programmiersprache.
(Allerdings entspricht den Prolog-Listen eher Haskell-Tupel, denn Listen durften in
Haskell ja keine verschiedenenartigen Daten-Typen enthalten. )
Die Schreibweise für Listen ist Standard:
[margit, miriam, julian] oder
[rot, blau, gruen, weiss, schwarz] sind Listen. Allerdings ist auch dies:
[rot, blau, gruen, weiss, schwarz,1,2,[ margit, miriam, julian] ] .
Die Elemente der Liste dürfen also nicht nur verschieden sein, - sie dürfen als
Elemente selbst Listen enthalten. Es ist auch die „leere Liste“ [ ] zugelassen.
Um auf einzelne Listenelemente zugreifen zu können, benötigt man einen
„Separator“. Häufig ist dies der Doppelpunkt oder der Strichpunkt - hier in Prolog ist
es der senkrechte Strich:
[rot, blau | [gruen, weiss, schwarz] ]
Hier ein Beispiel für eine Anfrage:
Solche Separatoren sind für die Bearbeitung von Listen unverzichtbar. Es gibt jedoch
noch weiter Möglichkeiten, durch vorgefertigte Operationen eine Bearbeitung zu
vereinfachen:
member(X,Liste). bedeutet: „Das Element X ist in der Liste vorhanden“. Beispiel:
length(Liste,N). bedeutet: „Die Anzahl der Elemente der Liste ist N.“ Beispiel:
29
append(Liste1,Liste2,L). bedeutet: „L ist die Liste, die durch anhängen der Liste2 an
Liste1 entsteht.“ Beispiel:
Hier sehen Sie, dass Prolog gegebenenfalls drei Punkte für „usw“ schreibt!
Hier wird die append-Operation zusammen mit dem Separator benutzt:
Mitunter ist die Verwendung einer anonymen Variablen (z.B.: [ _| a] ) von Vorteil:
Eine anonyme Variable ist eine Variable, deren Wert nicht benötigt wird.
Entsprechend „anonym“ ist dann auch das Ergebnis der Anfrage!!!
Aufgabe 18
•
•
•
•
•
Hängen Sie mit append ein einzelnes Element an eine Liste hinten an.
Stellen Sie einige Anfragen mit den Listenoperatoren length und member.
Was ergibt die Anfrage:?- member(Zahl,[1,2,3,4,5]).
Wie kann man alle Elemente einer Liste einzeln ausgeben lassen?
gibAus([1,2,5,6]). soll 1 2 5 6 liefern. (Tipp: Separator und Rekursion
benutzen).
Schreiben Sie eine Prozedur element_n, die prüft, ob das n-te Element einer
Liste gleich einem gegebenen Element ist (Zählung beginnt bei 0).
Ein Beispiel:
?-element_n([a,b,c,d,e],2,c) sollte Yes ergeben.
?-element_n([a,b,c,d,e],1,X) sollte X=b ergeben.
Der letzte Teil der Aufgabe war nicht einfach! Eine mögliche Lösung sieht so aus:
element_n(Liste,N,X):append(LinkeSeite,[X|_],Liste),
length(LinkeSeite,N).
Angenommen, man gibt ein
?- element_n([a,b,c,d,e],3,X).
30
Was passiert dann nach dem obigen Programmcode eigentlich, bis es zur Lösung
X=d kommt? Man kann es sich bildlich so vorstellen:
[a,b,c,d,e] ist die „Liste“. Sie muss als Ergebnis bei der Operation append
herauskommen. Weil die Liste „LinkeSeite“ die Länge 3 hat, kann sie nur so
aussehen: [a,b,c]. Zusammengefasst:
[a,b,c,X, Restliste] = [a,b,c,d,e]. Durch direkten Vergleich („matching“) kommt man
jetzt zum Ergebnis: X = d
Vielleicht etwas einfacher, aber noch eine Spur trickreicher, ist die Operation
enthalten(X,L).
Zum Beispiel soll die Anfrage enthalten(s,[a,b,t,s,y]). „Yes“ ergeben, da s in der
anschließenden Liste enthalten ist.
Und so könnte man enthalten(X,L). implementieren:
enthalten(E,[E| _ ]).
enthalten(E,[ _ |L]):- enthalten(E,L).
Um zu verstehen, wie Prolog hier vorgeht, lohnt es sich, eine Anfrage im spur-Modus
zu stellen:
Das heißt: Sollte das erste Element der Liste das gesuchte Element E sein, dann wird
Yes ausgeben. (Ausstieg aus der Rekursion).
Ansonsten wird nach und nach jedes Kopfelement der Liste weggelassen und geprüft,
ob jetzt das erste Element der neuen Liste das gesuchte E ist.
Zwei Zeilen Programmcode! Einfach genial, oder?!!
Wir benötigen für die Ausgabe von Listen bei unseren „Busfahrten“ noch zwei weitere
Listenoperationen.
Aufgabe 19
Die Operation anhaengen_an soll eine ein-elementige Liste [X] an eine gegebene
Liste L2 hinten anhängen. Formulieren Sie die Operation mit Hilfe des appendBefehls.
Die Operation an_denAnfang soll ein Element X an den Kopf einer gegebenen Liste
L stellen.
Testen Sie die neuen Operationen an einigen Beispielen!
(Lösung auf der nächsten Seite erst anschauen, wenn keine eigene Lösung gefunden
wurde.)
31
Eine Lösung für anhaengen_an :
anhaengen_an([X],L2,L):-append(L2,[X],L).
Eine Lösung für an_denAnfang :
an_denAnfang(X,L,[X|L]).
Kommen wir zurück zu unserem Spar-Buslinien-Problem. Leider konnten wir ja immer
nur erfahren, ob ein eingebener Weg möglich ist oder nicht. Das wollen wir nun
ändern. Das Programm spar_buslinien_alle soll uns sämtliche möglichen Wege als
Liste ausgeben. So wird es klappen:
an_denAnfang(X,L,[X|L]).
allewege(X,X,[X]).
allewege(X,Y,L):- buslinie(X,Z),
allewege(Z,Y,NL),
an_denAnfang(X,NL,L).
Es ist auch hier ausgesprochen hilfreich, Prolog im spur-Modus bei der Lösung eines
sehr einfachen Falls zuzusehen:
Die Rekursion wird solange durchgeführt, bis der Ausstieg der Rekursion
allewege(2,2,[2]). erreicht wird. Dann wird bekannt, was _G322 ist, nämlich [1,2].
Sehr schön sieht man auch, wie 1 in die Liste [2] vorn eingefügt wird.
Drückt man nach Angabe der ersten Lösung die Enter-Taste, so sucht Prolog nach
weiteren Lösungen. Hier ein kleiner Ausschnitt:
Beispiel für Backtracking:
da busline(7,9) nicht zu Ziel
führt wird die Alternative
busline(7,10) getestet.
32
Dass nun bei allewege(2,2,...) weitergesucht wird, haben wir ebenfalls dem
Backtracking zu verdanken. Rein theoretisch könnte es ja den (unsinnigen) Weg 1-23-2 geben.
Hier geht es dann nicht weiter und somit ist der Versuch mit buslinie(1,2) beendet und
durch erneutes Backtracking werden nun noch die Versuche:
und
(vergeblich) durchprobiert. Erst danach gibt es keine weitere Möglichkeiten mehr und
Prolog gibt No aus.
Damit allewege(X,X,L) nach dem ersten Erreichen des Ziels nicht weiter verfolgt wird,
sollte man die obige Regel leicht abändern:
allewege(X,Y,L):- X\=Y,
buslinie(X,Z),
allewege(Z,Y,NL),
an_denAnfang(X,NL,L).
Vergleichen Sie diese Lösung im spur-Modus mit der vorherigen.
Sollten Sie allerdings auf die Idee kommen, allewege(1,11,L) im spur-Modus
beobachten zu wollen, dann werden Sie einige Zeit beschäftigt sein ;-))
Wieviele Spar-Buswege gibt es von Station 1 bis 11? Das erfahren Sie, wenn Sie
nach jeder angegebenen Lösung durch die Enter-Taste ein Backtracking erzwingen.
Es sollten 16 Lösungen sein! Welche Lösung fährt die meisten Busstationen an?
Wieviele sind es?
Die „Spar-Bus-Variante“ hat programmtechnisch den Vorteil, dass keine EndlosSchleifen entstehen können. Das ist eine sehr starke Einschränkung, die wir beim
nächsten Problem loswerden wollen:
In der oben erwähnten großen Stadt gibt es ein weiteres Sondern-Ticket. Es ist für
Leute gedacht, die sich möglichst wenig Sehenwürdigkeiten entgehen lassen wollen.
Die Bedingungen:
• Man darf die Buslinien in alle Richtungen benutzen.
• Allerdings darf man nicht zweimal die gleiche Busstation anfahren.
• Man darf mit dem Ticket nur die schwarze oder die blaue Linie benutzen.
So sieht der Busplan jetzt aus:
33
Damit man nicht alle Buslinien in die Gegenrichtung neu aufführen muss, kann man
eine Regel verwenden (siehe auch weiter oben):
bus(X,Y):- buslinie(X,Y);
buslinie(Y,X).
Die blauen Linien müssen natürlich (in einer Richtung) noch nachgetragen werden:
buslinie(12,13). etc
Es ist Ihnen sicher klar, dass die Menge der Lösungen selbst bei diesem kleinen Plan
rapide zunimmt.
Der Einfachheit halber schreiben wir zunächst nur ein Programm, dass uns mit Yes
oder No angibt, ob ein bestimmter Weg möglich ist.
Dies scheint auf den ersten Blick ziemlich sinnlos, denn dank der Farbgebung sind wir
mindestens genau so schnell wie der Computer. Allerdings wollen wir mit dem
Programm nur einfacher zu unserer eigentlichen Aufgabe kommen: Alle Listen von
Station a nach Station b ausgeben zu lassen.
Wir greifen dabei auf die Ihnen schon bekannten Operationen anhaengen_an und
enthalten zurück. Lesen Sie nötigenfalls die Erklärungen weiter oben nochmals
durch. (buslinie.pl)
anhaengen_an([X],L2,L):- append(L2,[X],L).
enthalten(E,[E|_]).
enthalten(E,[_|L]):- enthalten(E,L).
wege(X,X,_).
wege(X,Y,L):- bus(X,Z),
not(enthalten(Z,L)),
anhaengen_an([Z],L,NL),
wege(Z,Y,NL).
(Lesen Sie, falls nötig, die Funktionsweise und Bedeutung für anhaengen_an/3 und
enthalten/2 nochmals durch.)
34
Wie Sie erkennen wird eine Liste L mitgeführt. Zu Beginn besteht die L nur aus der
ersten Busstation, also L = [x].
Wenn eine Zwischenstation Z angefahren wird, die noch nicht in der Liste L enthalten
ist, dann wird sie in L hinten hinzugefügt.
Schauen wir Prolog bei einer einfachen Anfrage im spur-Modus „über die Schulter“:
Beobachten Sie, wie die Weganfrage rekursiv bearbeitet wird.
Dies geht so lange bis der Interpreter an die Zeile wege(7,7,[5,6,7]), den
Rekursionsausstieg kommt.
Da bis hierher alles widerspruchsfrei ablief, bekommt man ein Yes als Antwort.
Man erkennt ebenfalls, dass die Liste der Busstationen, die von Station 5 nach Station
7 führen, bereits vorhanden ist. Man muss sie nur noch auslesen lassen...
Daher muss der Ausstieg der Reduktion einfach mit einem Schreibbefehl verknüpft
sein.
Das neue Programm buslinie_eine.pl unterscheidet sich daher nur wenig vom
obigen Programm:
wegeliste(X,X,L):-write(L).
wegeliste(X,Y,L):- bus(X,Z),
not(enthalten(Z,L)),
anhaengen_an([Z],L,NL),
wegeliste(Z,Y,NL).
(Die Programmzeilen anhaengen_an und enthalten sind unverändert und wurden
daher hier nicht aufgeführt!)
Aufgabe 8
•
Testen Sie das Programm mit der Anfrage wegeliste(2,10,[2]).
35
•
Beobachten Sie mit dem trace-Modus eine sehr einfache Anfrage.
Leider bekommt man höchstens eine Lösung, denn Prolog geht nach der Ausgabe
der gefundenen Liste L alle Rekursionsschritte rückwärts und stellt schlussendlich
zufrieden fest, dass die Anfrage mit Yes beantwortet werden kann.
Das muss nicht sein! Mit einem simplen Trick liefert Prolog auch alle Lösungen auf
einmal (Programm buslinieListeAlle.pl):
wegeliste(X,X,L):- write(L),nl.
wegeliste(X,Y,L):- bus(X,Z),
not(enthalten(Z,L)),
anhaengen_an([Z],L,NL),
wegeliste(Z,Y,NL),
fail.
Das Prädikat fail führt dazu, dass Prolog am Ende einer Rekursion scheitert.
So erzwingt man ohne Betätigung der Enter-Taste ein Backtracking.
Neu ist das Prädikat nl. Es bedeutet einfach: „new line“.
Eine Anfrage sieht dann zum Beispiel so aus: wegeliste(1,11,[1]).
Mit dem obigen Busplan zählt Prolog bei dieser Anfrage 28 Möglichkeiten auf.
Sollten Ihnen dies alles recht rätselhaft vorkommen, so lesen Sie gleich jetzt auf
Seite 212 den Versuch einer Klarstellung......
Aufgabe 9
•
Vergrößern Sie die Anzahl der Busstationen und lassen Sie sich dann durch
eine Anfrage wegeliste(a,b,[a]) alle möglichen Wege ausgeben.
36
•
Fügen Sie einige Einbahnstraßen hinzu. (Wie ist das realisierbar?) Stellen Sie
erneut eine Anfrage!
In der Mathematik heißen Konstrukte, wie im Bild oben, Graph. Die Punkte (hier
Bushaltestellen) sind Knoten, die Linien dazwischen heißen (gerichtete) Kanten.
Der Zweig der Mathematik, der sich mit Graphen beschäftigt, heißt Graphentheorie.
Die vielleicht bekanntesten Anwendungen dieser Theorie sind der Vierfarbensatz
und das Königsberger Brückenproblem. Der Vierfarbensatz gesagt, dass man zur
Einfärbung einer Landkarte nur vier Farben benötigt, das Königsberger
Brückenproblem untersucht, ob es einen Rundweg gibt, bei dem man alle Brücken in
Königsberg (heute Kaliningrad) nur genau einmal verwendet, aber alle Brücken
benutzt hat. Es ist dabei gleichgültig, wo man den Weg beginnt und wo man ihn
beendet.
Hier kann man es ausprobieren:
http://www.matheprisma.uni-wuppertal.de/Module/Koenigsb/
Das nebenstehende Bild (Wikipedia)
zeigt die Situation zur Zeit Leonhard
Eulers (1736), der das Problem mit Hilfe
der Graphentheorie gelöst hat.
Sie können es auch lösen, - mit Prolog,
ohne etwas von Graphentheorie
verstehen zu müssen.
Zunächst verwandeln wir die
geografische Situation in einen Graphen
wie bei den Bushaltestellen oben.
37
Im Gegensatz zum Busproblem darf hier jeder Knoten bliebig oft vorkommen. Dafür
darf und muss jede Verbindung (Brücke) genau einmal benutzt werden.
Das bedeutet, dass wir dieses Mal die Zahlen für die Brücken in einer Liste mitführen
müssen.
Da es hier genau 7 Brücken sind, muss Prolog bei jeder benutzen Verbindung eine
abstreichen.
Wer die Busprobleme verstanden hat, wird zweifelsohne auch hier eine Lösung
finden:
%% Königsberger Brückenproblem
ueber(1,s,i).
ueber(2,s,i).
ueber(3,n,i).
ueber(4,n,i).
ueber(5,n,o).
ueber(6,i,o).
ueber(7,s,o).
bruecke(B,X,Y):- ueber(B,X,Y);
ueber(B,Y,X).
anhaengen_an([X],L2,L):-append(L2,[X],L).
enthalten(E,[E|_]).
enthalten(E,[_|L]):- enthalten(E,L).
weg(_,_,L,0):-
write(L),nl.
weg(X,Y,L,N):- bruecke(B,X,Z),
not(enthalten(B,L)),
anhaengen_an([B],L,NL),
M is N-1,
weg(Z,Y,NL,M).
weg_von(Start):- weg(Start,_,[],7), fail. %% Um Backtracking zu erzwingen
Vergleichen Sie mit dem Programm buslinie_alle_schnell und Sie werden feststellen,
dass nur wenig geändert werden muss.
Aus buslinie wurde ueber. Bei ueber muss ein weiterer Parameter mitgenommen
werden, weil es mehrere Verbindungen zwischen zwei benachbarten Knoten geben
kann. bruecke entspricht bus und sorgt dafür, dass die Verbindung in beide
Richtungen zugelassen wird.
Bei der Rekursion fällt nur die neue Zeile M is N-1 auf. Diese wird, wie oben schon
erwähnt, gebraucht, um auch alle 7 Brücken zu benutzen, indem von N=7 auf 0
runtergezählt wird (Ausstieg der Rekursion).
38
Stellen Sie zunächst eine Anfrage, deren Antwort Sie kennen. Beispielsweise: Wie
kommt man von Gebiet s nach Gebiet o, wenn man genau 3 Brücken benutzen darf:
Aber das interessiert uns ja nicht. Wir wollen wissen, ob man einen Rundweg finden
kann, bei dem jede Brücke genau einmal benutzt wird. Man müsste also viele
Anfragen der Form ?- weg(Start,Ziel,[ ], 7). stellen. Da das Ziel gleichgültig ist,
verwenden wir bequemer die letzte Zeile mit der Regel : weg_von(Start).
So kann man die Anfrage, ob es einen Weg vom Südufer aus gibt, so formulieren:
weg_von(s).
Und? Gibt es eine Lösung?
Aufgabe 10
Es gibt allerdings noch andere Fälle, von denen
die zwei typischen Vertreter hier dargestellt sind:
Im ersten Bild handelt es sich um die Stadt
Meiningen mit dem Fluss Werra, im zweiten Bild
ist es Passau (im Jahre 2050, denn die rot
eingetragenen Brücken gibt es noch nicht....).
Hier fließen die Flüsse Ilz vom Norden und Inn
vom Süden in die Donau.
Ändern Sie das Königsberger-Brücken-ProblemProgramm ab und untersuchen Sie, ob man in
Meiningen oder Passau das tun kann, was in
Königsberg offensichtlich nicht möglich war.
Achten Sie besonders darauf, ob es darauf
ankommt, wo man startet!
Falls es eine Möglichkeit gibt, - ist dies dann die
Einzige?
(oben:
Meiningen)
(rechts: Passau)
Kommen wir zurück
zu unseren Buslinien.
Prolog sagt uns
bisher, welche
Möglichkeiten es gibt, um von A nach B zu kommen. Das mag ja ganz hilfreich sein, perfekt ist es jedenfalls noch nicht. Gibt man bei einem Navigationsgerät oder bei
einem Routenplaner Start und Ziel ein, so listet einem das Programm ja auch nicht
39
alle Möglichkeiten auf, wie das Ziel zu erreichen ist! Vielmehr informiert man das
Programm zuvor, welche Vorgaben bei der Planung zu beachten sind: Schnellste
Strecke, kürzeste Strecke, Stecke ohne Autobahnen, Strecke mit den meisten
Sehenswürdigkeiten …..
Damit wird aus dem Graph ein „gewichteter Graph“. Zum Beispiel kann das „Gewicht“
die Streckenlänge zwischen den Knoten sein:
Beachten Sie, dass Graphen in der Regel (wie oben) nicht maßstabsgetreu sind. Man
hat daher keine „Landkarte“ vor sich und entsprechend schwer fällte es einem, selbst
in einem so extrem einfachen Beispiel, die kürzeste Strecke zwischen Knoten 1 und
Knoten 9 zu finden. Finden Sie die kürzeste Strecke?
Zu Beginn wollen wir uns damit zufrieden geben, dass Prolog einfach nur die
Streckenlänge zu allen gefundenen Strecken mit angibt. Und das geht so:
%% Streckenlaengen
linie(1,2,55).
linie(1,3,12).
linie(1,4,70).
linie(2,5,38).
linie(2,6,72).
linie(3,6,82).
linie(3,4,94).
linie(4,6,69).
linie(5,6,58).
linie(6,7,83).
linie(6,8,65).
linie(7,9,51).
linie(7,10,45).
linie(8,9,26).
linie(9,11,47).
linie(9,10,22).
linie(10,11,51).
strecke(X,Y,Z):- linie(X,Y,Z);
linie(Y,X,Z).
40
anhaengen_an([X],L2,L):-append(L2,[X],L).
enthalten(E,[E|_]).
enthalten(E,[_|L]):- enthalten(E,L).
%%Beispielanfrage: laenge_weg_von_bis(1,11).
wegeliste(X,X,L,N):-write(N), write(L),nl.
wegeliste(X,Y,L,N):- strecke(X,V,Z),
not(enthalten(V,L)),
ahaengen_an([V],L,NL),
M is N + Z,
wegeliste(V,Y,NL,M ),
fail.
laenge_weg_von_bis(X,Y):- wegeliste(X,Y,[X],0).
Aus buslinie(X,Y) wird jetzt linie(X,Y,N). Wie zu erwarten ist in N die Entfernung
gespeichert.
is ist ein built-in Prädikat. Der rechte Term wird berechnet und an die linke Variable
(M) gebunden. Falls die linke Seite keine Variable ist, dann wird ein Vergleich
durchgeführt.
Weshalb schreibt man nicht M = N+ Z , wie man es in Delphi (mit Doppelpunkt)
machen würde? Ganz einfach: Bei der obigen Schreibweise testet Prolog lediglich,
ob der Term links mit dem Term rechts „matcht“ oder nicht.
Wie wäre es mit M =:= N + Z ? Geht auch nicht, da hier beide Seiten instanzierte
Variable sein müssen. M wird aber erst erzeugt.
Die letzte Zeile ist wie im letzten Beispiel aus reiner Bequemlichkeit entstanden. Die
beiden letzten Parameter von wegeliste sind redundant. Denn natürlich soll der erste
Eintrag in der Liste L der Startort sein. Und außerdem ist beim Start die
Streckenlänge N noch Null.
Damit wir der Wirklichkeit eines Routenplaners wenigstens ein wenig gerechter
werden, soll der Graph vergrößert werden: (keine Einbahnstraßen)
41
Aufgabe 11
Vervollständigen Sie die Liste der „Linien“ anhand des obigen gewichteten Graphen.
Erstellen Sie dann den vollständigen Quelltext zu laenge_weg_von_bis.
Wie lang ist die kürzeste und wie lang ist die längste Strecke zwischen den Orten 1
und 12? Wieviele Wege gibt es von 1 nach 12 ?
(Zur Erinnerung: Ein Knoten darf höchstens einmal angefahren werden!)
Da es einige tausend Wege von 1 nach 12 gibt, ist kaum anzunehmen, dass Sie
darunter den kürzesten Weg ausfindig machen konnten.
Es muss also, wie in den Programmen für Routenplanung auch, eine Grenze S
festgelegt werden, ab der eine weitere Verfolgung des Weges abgebrochen wird.
(Man kann auf die Eingabe einer Obergrenze auch verzichten, wenn man das
Zwischenergebnis mit der letzten Streckenlänge vergleicht. Sobald dies größer als der
letzte Wert ist, wird abgebrochen. Ist aber die aktuelle Streckenlänge kürzer, als das
letzte Ergebnis, so wird die kürzere Strecke als neuer Referenzwert übernommen.
Dieses Verfahren der immer neuen Speicherbelegung für das Minimum wird im
Anschluss behandelt.)
Bei geschickter Wahl der Obergrenze S wird die Menge der Möglichkeiten deutlich
geringer. Und so kann man es realisieren:
42
wegeliste(N,X,X,L,S):- append([N],L,NL),print(NL),nl.
wegeliste(N,X,Y,L,S):- strecke(X,V,Z),
not(member(V,L)),
anhaengen_an([V],L,NL),
M is N + Z, M<S,
wegeliste(M,V,Y,NL,S),
fail.
weg_von_bis_kleiner(X,Y,S):- wegeliste(0,X,Y,[X],S).
Durch die Bedingung N < S werden nur die Strecken verfolgt und anschließend
ausgegeben, deren Länge kleiner als die vorgegeben Größe S ist.
Beachten Sie, dass member(V,L) die prolog-eigene Anfrage für unserer Anfrage
enthalten(V,L) ist. Wir hoffen dabei auf einen kleinen Geschwindigkeitsvorteil!!
Anfrage aus Aufgabe 11:
?- weg_von_bis_kleiner(1,12,250).
[219, 1, 2, 5, 13, 12]
[217, 1, 2, 14, 13, 12]
[249, 1, 3, 6, 8, 9, 12]
[245, 1, 15, 2, 5, 13, 12]
[243, 1, 15, 2, 14, 13, 12]
No
Das sieht doch jetzt bedeutend übersichtlicher aus!
Dennoch, - so richtig befriedigend ist auch diese Lösung nicht. Man muss die
Obergrenze S schon sehr genau erraten, damit die Zahl der Lösungen einigermaßen
gering bleiben.
Aufgabe 12
Erstellen Sie den Programmcode weg_von_bis_min, der auch bei noch größerer
Punktemenge schnell und übersichtlich den kürzesten Weg berechnet.
Testen Sie das Programm durch einige Anfragen.
43
Die hierfür nötige Datenbank für Prolog können Sie aus dem Tauschverzeichnis
laden.
Die obige Aufgabe ist alles andere als einfach. Daher werden weiter unten einige
Ideen dazu vorgestellt.
Zunächst einige grundsätzliche Bemerkungen zum Thema „Suchen in Graphen“.
Solange man die Punkte (Knoten) nicht mit Koordinaten versieht und die
Verbindungen auch nicht „gewichtet“, wie bei uns durch die „Entfernung“ zwischen
den Punkten, ist jeder Weg von A nach B gleich zu werten. Können Sie sich in etwa
vorstellen, wieviele verschiedene Wege es etwa im obigen Bild von Knoten 1 nach
Knoten 51 gibt?
Obwohl innerhalb eines Weges kein Knoten zwei mal vorkommen darf, ist die Zahl
der Wege unvorstellbar groß.
Prolog meldet in der Situation (20 Knoten) S.210 genau 1364 Wege. Eine Warnung
vorweg: Wenn Sie jetzt Prolog die Anzahl der Wege mit 80 Knoten (Bild oben)
ausrechnen lassen wollen, dann schauen Sie besser erst morgen nach dem Ergebnis!
Auf diesem „niederen Struktur-Niveau“ muss jede Suche erschöpfend sein. Es darf
kein Weg ausgelassen werden! Dass dies eine sehr theoretische Fragestellung ist,
44
wird Ihnen klar sein: Die Knoten der Graphen in einem Navigationsgerät verfügen
über Koordinaten und damit automatisch auch über „Gewichtungen“ der
Verbindungen. Sonst wäre eine Anfrage bezüglich einer „kürzesten Verbindung“
zwischen A und B schlicht sinnlos.
Es gibt hier zwei Arten nach allen Wegen zwischen A und B zu suchen. Alle beiden
werden auch „Blindsuchen“ genannt, weil sie einfach alles „blind“ durchspielen
müssen, anstatt „sehenderweise“ manche Wege als unsinnig ad acta legen zu dürfen.
Was wir bisher gemacht haben, als wir in den obigen Anfragen alle Wege von A nach
B gesucht haben, war eine Tiefensuche oder DFS (depth first search). Der
Interpreter selbst von Prolog arbeitet mit der DFS. Deshalb ist Prolog bei dieser Art
der Suche allen anderen Programmiersprachen überlegen.
Weshalb der Ausdruck „Tiefensuche“?
In der Tat ist die Bezeichnung sinnvoll gewählt, denn Prolog geht bei der Suche eines
Weges zwischen A und B zunächst ganz in die „Tiefe“, - bis es nicht mehr weiter geht!
Und dann beginnt das Backtracking.
In nebenstehendem einfachen
Graphen wird der Algorithmus
deutlicher: Es ist ein Weg von
Knoten 6 nach Knoten 5 zu
finden. Zunächst geht es bis
Knoten 2. Wählt Prolog jetzt
als nächstes Knoten 1, so
werden mit mehrfachem
Backtracking die blauen
Linien durchlaufen.
Schließlich landet man wieder
bei Knoten 2 und dieses mal
wird der richtige Weg zu
Knoten 5 gewählt.
Wie würde Prolog jetzt die
anderen möglichen Wege
durch DFS finden? Welche
Nachteile bzw. welche Vorteile hat diese Methode?
Rufen wir uns nochmal ins
Gedächtnis: Es müssen in jedem
Fall alle Wege getestet werden. Kein
Alogrithmus kann uns dies ersparen.
Möglich ist aber, dass durch ein
geschickteres Vorgehen, der
Prozessor weniger Zeit für die
gleiche Arbeit benötigt. Stellen Sie
sich einen PC mit einem riesigen
RAM vor. Dann ist die Breitensuche
oder BFS (breadth first search) ein
interessantes Konzept. Hier die
gefundenen Wege als Ganzes auf
den Speicher gelegt und nach und
45
nach durch längere Wege ersetzt. Ein Bild soll dies veranschaulichen:
Gleiche Aufgabe wie oben: Es soll ein Weg zwischen Knoten 6 und Knoten 5
gefunden werden.
Prolog stellt nun anhand der Datenbank fest, welche Wege von Knoten 6 wegführen
und notiert sich dann die Wege [6,2], [6,8] und [6,9].
Es entsteht also eine Liste von Wegen:[ [6,2], [6,8] und [6,9] ].
Diese Liste wird nach folgender Regel ausgebaut: Nehme der Reihe nach jeden Weg
und versuche ihn auszubauen. Dann entsteht aus [6,2] :
[6,2,5], [6,2,1] und [6,9,8]. Die drei werden jetzt in der Liste gespeichert und dafür
wird [6,2] gestrichen.
Wenn alle zwei-Knoten-Wege ersetzt sind, sieht die neue Liste so aus:
[ [6,2,5], [6,2,1], [6,9,8], [6,9,7] ].
Man kann sich leicht vorstellen, dass bei vielen Knoten die Liste sehr schnell sehr
groß werden kann! Ist der Prozessor in der Lage, parallel viele Wege gleichzeitig zu
prüfen, so ist dieses Verfahren natürlich deutlich schneller! Ein Weg von 6 nach 5 ist
hier bereits beim zweiten Anlauf gefunden, - oben waren es neun Schritte!
Dennoch: Da ja alle Wege gefunden werden müssen, ist der Geschwindigkeitsvorteil
aber nur bei Parallelverarbeitung vorhanden.
Hier nun der Quellcode für eine Tiefensuche. Wenn Sie die Anfrage auf eine Knotenmenge größer 20 anwenden, dann wird Ihnen der Stack Probleme machen. Aber
testen Sie selbst:
strecke(X,Y,Z):- linie(X,Y,Z);
linie(Y,X,Z).
% Wege in Nachfolgewege expandieren
expandiere([E|R], Wege) :findall(X,strecke(E,X,_), Nachfolger),
e([E|R], Nachfolger, [], Wege).
% Hilfsprädikat für expandiere
e(_, [], X, X).
e(Weg, [E|R], Bisher, Ergebnis) :not(memberchk(E,Weg)),
e(Weg, R, [[E|Weg]|Bisher], Ergebnis).
e(Weg, [E|R], Bisher, Ergebnis) :memberchk(E,Weg),
e(Weg, R, Bisher, Ergebnis).
% Tiefensuche
% ts(Superliste, Ziel, Ergebnisweg)
ts([[Ziel|R]|_RestWege], Ziel, [Ziel|R]):- Loesung = [Ziel|R],print(Loesung),nl.
ts([Weg1 | RestWege], Ziel, Weg) :expandiere(Weg1, NachfolgeWege),
append(NachfolgeWege,RestWege, NeueSuperliste),
ts(NeueSuperliste, Ziel, Weg).
46
% bequemer Aufruf
tiefensuche(Start, Ziel, Weg) :- ts([[Start]], Ziel, Gew),fail.
Schnell ist der Code ohne Zweifel, - aber leider nicht verwendbar für größere
Knotenmengen!
Ganz anders sieht die Sache aus, wenn die Kanten (Verbindungen) „gewichtet“ sind.
Die „Gewichte“ sind bei uns oben die Entfernungen in Kilometern zwischen den
Knoten. Jetzt kann durch bestimmte Nebenbedingungen (zum Beispiel darf der Weg
nicht länger sein als 100 km) die Rechenarbeit reduziert werden. Eine solche Suche
nennt man eine heuristische Suche.
Aufgabe 13
Überlegen Sie sich kurz, welche unserer Prolog-Anfragen heuristisch waren und
welche nicht!
Wenn man alle Wege von A nach B sucht, die eine gewisse Länge nicht
überschreiten, ist dann die Breiten- oder die Tiefensuche günstiger?
Wie könnte man bei einer heuristischen Tiefensuche das Überlaufen des Stacks
verhindern?
Zurück zu Aufgabe 12. Es wurde eine Prolog-Lösung gesucht, die auch bei einer
größeren Anzahl von Knoten, relativ schnell den kürzesten Weg bestimmt.
Der folgende Code stammt von Mario Schreiner. Er fand heraus, dass man auch in
Prolog globale Variablen verwenden kann.
initGlobals:- nb_setval('KuerzesterWeg',0), nb_setval('KuerzesterWegPunkte',[]).
Das nutzt er für eine heuristische Tiefensuche aus, indem er die Länge des ersten
erfolgreichen Weges von A nach B in die globale Variable schreibt und fortan alle
längeren Wege nicht weiter verfolgt. Gleichzeitig wird aber ein kürzerer und
erfolgreicher Weg die globale Variable erneut verändern, so dass zum Schluss der
kürzeste Weg übrig bleibt:
Der komplette sehr gut kommentierte Code kann im Tauschverzeichnis geladen
werden. ( kuerzesterWeg80Mario.pl )
Die Optimierung ist noch nicht perfekt, denn eine Anfrage wie
kuerzesterWeg(1,25,Weg).
dauert deutlich mehr als 10 Minuten.
Eine andere Idee stammt von Thomas Fröhle. Die entscheidenden Zeilen sind diese:
kurz(X,Y):setof(N,weg(X,Y,N,[X],[0]),Liste),
47
% setof sucht alle möglichen Lösungen für die Strecke X Y und speichert die Lösung
%(N) in einer Liste. Diese ist gleich schon so sortiert, das die kürzeste Strecke vorne
%steht
Sein gesamter, ebenfalls sehr gut kommentierter Code, kann im Tauschverzeichnis
geladen werden.
Mit der Geschwindigkeit war Thomas nicht zufrieden und entwickelte daher ein ganz
anderes Konzept, das davon ausgeht, dass die Knoten Koordinaten haben. Davon
später mehr.
Inspiriert von den Ideen von Mario und Thomas kann man auf einen sehr schnellen
Code kommen:
initGlobals:- nb_setval('Minimum',1000).
strecke(X,Y,Z):- linie(X,Y,Z);
linie(Y,X,Z).
istkleiner(X,Y,Z):- (X>=Y ,Z is Y) ; (Y>X , Z is X).
anhaengen_an([X],L2,L):- append(L2,[X],L).
%%Beispielanfrage: minweg(2,53).
wegeliste(N,X,X,L):- append([N],L,NL),print(NL),nl,
nb_setval('Minimum',N).
wegeliste(N,X,Y,L):- nb_getval('Minimum',Minimum),
strecke(X,V,Z),
not(member(V,L)),
anhaengen_an([V],L,NL),
M is N + Z,
M<Minimum,
wegeliste(M,V,Y,NL),
fail.
minweg(X,Y):- initGlobals, nb_getval('Minimum',Minimum),
wegeliste(0,X,Y,[X]).
Damit werden wirklich nur die benötigten Zweige berechnet. Damit man beobachten
kann, wie die Streckenlänge immer kleiner wird, werden alle kürzerwerdenden Wege
ausgegeben.
29 ?- minweg(2,25).
[970, 2, 5, 6, 7, 9, 11, 12, 13, 14, 38, 24, 26, 27, 29, 31, 32, 33, 25]
[964, 2, 5, 6, 7, 9, 11, 12, 13, 14, 38, 24, 26, 27, 29, 32, 33, 25]
[905, 2, 5, 6, 7, 9, 11, 12, 13, 14, 38, 24, 26, 27, 29, 28, 33, 25]
[884, 2, 5, 6, 7, 9, 11, 12, 13, 14, 38, 24, 26, 28, 33, 34, 22, 25]
[810, 2, 5, 6, 7, 9, 11, 12, 13, 14, 38, 24, 26, 28, 33, 25]
[750, 2, 5, 6, 7, 9, 11, 12, 13, 14, 38, 24, 26, 22, 25]
[698, 2, 5, 6, 7, 9, 11, 12, 13, 14, 38, 24, 26, 25]
48
[670, 2, 5, 6, 7, 9, 11, 12, 13, 14, 38, 27, 29, 28, 33, 25]
[629, 2, 5, 6, 7, 9, 11, 12, 13, 14, 38, 27, 26, 25]
[627, 2, 5, 6, 7, 9, 11, 12, 13, 39, 27, 29, 28, 33, 25]
[586, 2, 5, 6, 7, 9, 11, 12, 13, 39, 27, 26, 25]
[574, 2, 5, 6, 7, 9, 11, 12, 40, 30, 31, 32, 33, 25]
[560, 2, 5, 6, 7, 9, 11, 12, 40, 30, 27, 26, 25]
[527, 2, 5, 6, 7, 9, 11, 12, 40, 30, 29, 28, 33, 25]
[521, 2, 5, 6, 7, 9, 12, 40, 30, 29, 28, 33, 25]
[517, 2, 5, 6, 8, 9, 11, 12, 40, 30, 27, 26, 25]
[484, 2, 5, 6, 8, 9, 11, 12, 40, 30, 29, 28, 33, 25]
[478, 2, 5, 6, 8, 9, 12, 40, 30, 29, 28, 33, 25]
[469, 2, 5, 6, 8, 13, 14, 38, 27, 26, 25]
[467, 2, 5, 6, 8, 13, 39, 27, 29, 28, 33, 25]
[426, 2, 5, 6, 8, 13, 39, 27, 26, 25]
[408, 2, 5, 13, 14, 38, 24, 26, 25]
[380, 2, 5, 13, 14, 38, 27, 29, 28, 33, 25]
[339, 2, 5, 13, 14, 38, 27, 26, 25]
[337, 2, 5, 13, 39, 27, 29, 28, 33, 25]
[296, 2, 5, 13, 39, 27, 26, 25]
[242, 2, 15, 36, 21, 22, 25]
[215, 2, 15, 36, 24, 26, 25]
[211, 2, 37, 24, 26, 25]
Rechenzeit bei 80 Knoten: Weniger als eine Sekunde!
Ob das Verfahren bei mehreren tausend Knoten noch sinnvoll funktioniert, darf
bezweifelt werden. Hier kommen nun Koordinaten ins Spiel.
Man muss sich zunächst klar machen, dass damit die Information in der Datenbank
zunimmt. Denn jetzt ist es möglich, von „Richtung“ zu sprechen. Damit fallen viele
Knoten weg, die in der „falschen Richtung“ liegen.
Durch die Reduktion einer sehr großen Knotenmenge auf eine kleine, wird die
Rechenzeit drastisch verkürzt. Allerdings kann man nicht immer sicher sein, auch
wirklich den kürzesten Weg gefunden zu haben! Man muss sich daher bei einer sehr
großen Knotenmenge mit einer Näherungslösung zufrieden geben.
Hier nun der Kommentar von Thomas Fröhles zu seinem Quellcode
(Greedy_ThomasFroehle.pl). Der Greedy-Algorthmus ist eine optimierte Tiefensuche.
Weitere Informationen dazu: http://de.wikipedia.org/wiki/Greedy-Algorithmus
Daten:
punkt (ID, X-Wert, Y-Wert)
Punkte in Koordinatenform
linie (PunktA, PunktB)
Verbindungen zwischen Punkten
Unterprogramme:
wurzel (X, Y, MaxAbw)
Berechnet Y, die Quadratwurzel von X mit der Abweichung MaxAbw
49
abstand2p (P, Q, Abstand)
Berechnet den Abstand zwischen P und Q
strecke(PunktA,PunktB,Strecke)
Checkt, ob eine Verbindung zwischen PunktA und PunktB existiert und berechnet mit
abstand2p den Abstand zwischen den Punkten
Greedyprogramme:
strecke_luftlinie (Anfang, Ende, Punkte, H)
Weist Punkte einen H- Wert zu:
1. Suche alle Punkte, die eine Verbindung zu Anfang haben.
2. H- Wert ist die Summe aus der Strecke von Anfang zu Punkte und der Luftlinie
von Punkte zu Ende
suche (Start, Ziel, Punkt)
Sucht den Punkt der den geringsten H- Wert hat.
Wegfindungsprogramme:
weg (X, Y, N, L, R, L2)
X:Startpunkt
Y:Endpunkt
N:Bisher zurückgelegter Weg
L:Bisher zurück gelegte Wegliste
R:Maximaler Weg
L2:Lösung (N,L)
Zuerst wird überprüft ob Ziel erreicht wurde (X= : =Y). Wenn Ziel erreicht wurde speicher den
Weg als kürzesten in der Globalen Variablen und speicher N und L in L2
Wenn Ziel noch nicht erreicht wurde:
1. Überprüfe, ob der bisher zurückgelegte Weg größer als der maximale Weg ist.
2. Wenn Ja: Weg abbrechen
3. Wenn Nein: Strecken, die von X ausgehen auslesen, Punkt V wird als nächstes
überprüft
4. Falls V noch nicht in L enthalten ist: V in L speichern
5. Falls noch kein Weg gefunden wurde ist die Globale Variable Null -> Rekursion
vom Punkt Vaus
6. Falls schon ein Weg gefunden wurde wird die bisherige Weglänge mit der
Luftlinie von V bis Y addiert und mit der Globalen Variable Kurz verglichen ->
wenn größer: abbrechen
7. Wenn kleiner -> Rekursion.
faktor (X, Y, R)
X:Startpunkt
Y:Endpunkt
R:Faktor
Globale Variablen erstellen bzw. Null setzen.
50
Die maximale Weglänge ist der Faktor mal Luftlinie zwischen Start und Endpunkt.
Finde alle Lösungen des Weg-Programms, mit den Variablen X, Y und Max, die
Lösungen, werden in der Liste Loesung gespeichert.
Falls diese Liste leer ist, wird der Faktor um 0,1 erhöht und Faktor neugestartet,
sonst wird die Lösung ausgegeben, die Globalen Variablen kurz und liste sind jetzt
mit dem kürzesten Weg gefüllt -> Diese werden dann aufgerufen.
kurz (X, Y)
Programm, das vom Benutzer ausgeführt wird, ruft faktor mit dem Anfangswert 1,5
auf.
Die Greedy-Suche basiert auf dem gleichnamigen Algorithmus. Die Idee dahinter ist,
dass der nächste Punkt der „vielversprechendste“ ist. Der Greedy Algorithmus ist erst
ab einer großen Anzahl an Punkten und Verbindungen schneller (siehe
Wenig_Punkte.pl und Viele_Punkte.pl). Bei wenigen Punkten ist die normale Suche
schneller.
weg_greedy (X, Y, N, L, R, L2)
Basiert auf dem weg- Programm.
Die einzigeÄnderung:
Es wird nicht willkürlich eine Strecke gesucht von X aus, sondern per suche(X, Y, V)
ausgeführt (siehe oben)
faktor_greedy (X, Y, R) und greedy (X, Y)
Sind die gleichen Programme wie bei der normalen Suche
ANMERKUNG:
Die Werte 1,5 als Standardfaktor und 0,1 als Erhöhungsschritt sind natürlich
individuell einstellbar, muss man ausprobieren, je nachdem wie viele Verbindungen
existieren.
% Autor: Thomas Fröhle
% Datum: 08.05.2008
wurzel(X,Res,MaxAbw) :wurzelberechnung(X,Res,_,MaxAbw), !.
wurzelberechnung(X,Res,TRes,MaxAbw) :var(TRes), TRes1 is X / 2,
wurzelberechnung(X,Res,TRes1,MaxAbw).
wurzelberechnung(X,Res,TRes,MaxAbw) :Quadrat is TRes * TRes,
LowBound is X - MaxAbw, HighBound is X + MaxAbw,
LowBound =< Quadrat, Quadrat =< HighBound,
Res = TRes, !.
wurzelberechnung(X,Res,TRes,MaxAbw) :Abw is (X - TRes * TRes) / (2 * TRes),
TResNeu is TRes + Abw,
wurzelberechnung(X,Res,TResNeu,MaxAbw).
51
abstand2p(P,Q,Abstand):punkt(P,X1,Y1),
punkt(Q,X2,Y2),
Z is ((X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1)),
wurzel(Z,Abstand,1).
strecke(PunktA,PunktB,Strecke):(linie(PunktA,PunktB);
linie(PunktB,PunktA)),
abstand2p(PunktA,PunktB,Strecke).
strecke_luftlinie(Anfang,Ende,Punkte,H):strecke(Anfang,Punkte,Strecke),
abstand2p(Punkte,Ende,Luftlinie),
H is Strecke + Luftlinie.
suche(Start,Ziel,Punkt):setof(Z,strecke_luftlinie(Start,Ziel,Z,_),Liste),
append([Punkt|_],_,Liste).
weg_greedy(X,Y,N,L,R,L2):- (X=:=Y,nb_setval('Kurz',N),
nb_setval('Liste',L),append([N],L,L2))
;
(N>R -> fail;
(
suche(X,Y,V),
abstand2p(X,V,Strecke),
not(member(V,L)),
append(L,[V],NL),
Zwischensumme is N + Strecke,
nb_getval('Kurz',Kurz),
(Kurz>0 ->
((abstand2p(V,Y,Luft),
Z_Luft is Luft + Zwischensumme,
Z_Luft > Kurz)->fail;
weg_greedy(V,Y,Zwischensumme,NL,R,L2))
;
weg_greedy(V,Y,Zwischensumme,NL,R,L2)
)))
.
faktor_greedy(X,Y,R):nb_setval('Kurz',0),
nb_setval('Liste',[]),
abstand2p(X,Y,Luft),
Max is Luft*R,
findall(L,weg_greedy(X,Y,0,[X],Max,L),Loesung),
length(Loesung,N),
(N =:= 0) -> (R_neu is R + 0.1,faktor_greedy(X,Y,R_neu))
;
52
(nb_getval('Kurz',Laenge),
nb_getval('Liste',Weg),
write('Kuerzester Weg:'),nl,
write(Weg),nl,
write('Laenge Des Weges:'),nl,
write(Laenge)
).
greedy(X,Y):- faktor_greedy(X,Y,1.5).
Zum Testen hat Thomas 2500 Punkte und fast 30000 Verbindungen erzeugt.
(Quellcode: Viele_Punkte.pl).
Die Wegsuche greedy(1,2455). dauert auf einem schnellen Rechner zirka 2 Minuten.
Das ist ein hervorragendes Ergebnis! Allerdings ist der
Greedy-Algorithmus ein Näherungs-Algorithmus. Mit anderen
Worten: Das Ergebnis ist möglicherweise nicht das kürzeste
Ergebnis!
53
6. Anhang: Hilfestellung zu Prolog
Es ist sehr wahrscheinlich, dass Sie anfangs mit Prolog einige Schwierigkeiten haben
werden. Das liegt zum Einen daran, dass in allen bisherigen Programmiersprachen
Speicherzuweisungen und anschließene Operationen, den Speicherinhalt betreffend,
durchgeführt wurden.
Eine Zeile wie: X:= 5; besagt, dass die Integerzahl 5 in den Speicher namens X
geschrieben wurde. An späterer Stelle kann man auf diesen Wert erneut zugreifen.
Solche Speicherzuweisungen gibt es in Prolog nicht! Wenn man beispielsweise
X is 5. schreibt, so bedeutet dies nur, dass in dieser Zeile die Variable X mit 5
verknüpft ist. Vor oder nach der Anfrage, die X is 5 enthält, ist die Verknüpfung
unbekannt.
Prolog „rechnet“ auch nicht, wie wir es etwa von C# gewohnt sind. In Anfragen wird
nur versucht, die Anfrage mit dem Datenbestand abzugleichen (= matchen).
Dabei greift Prolog im Wesentlichen nur auf Rekursionen zurück. Schleifen gibt es in
Prolog nicht.
Auch „Ausgaben“ sind hier immer als Vergleich mit dem Datenbestand zu verstehen.
Dazu ein Beispiel: In der Funktion anhaengen_an wird mit Hilfe der appendFunktion ein einzelnes Listenelement an Liste L2 hinten anghängt. Das Ergebnis ist
L.
Schauen Sie sich die folgenden Anfragen genau an!
anhaengen_an([X],L2,L):- append(L2,[X],L).
Hier gibt es keine Variablen, also kann nur Yes oder No ausgeben werden.
In den drei obigen Fällen gibt es jeweils eine Variable. Sie wird, falls möglich,
gematcht und ausgegeben. Da keine weitere Lösung existiert, wird schließlich ein No
ausgegeben.
54
Dieser Fall ist typisch für die Arbeitsweise von Prolog: Es gibt zwei Variable und
Prolog versucht mit Hilfe von „Platzhaltern“ (wie _G405) alle Möglichkeiten
auszugeben. Dass dies hier zu keinem Ende führen kann, ist verständlich. Die
Anfrage wurde daher angehalten.
Nun stellen Sie sich aber vor, dass im Programmcode an anderer Stelle auf den
Datenbestand zugegriffen wird. Und dort gibt es für LG = [_G406,_G411,_G415,a]
eine Entsprechung, wie [a,b,b,a]. Dann „matcht“ Prolog die Platzhalter und gibt ein
kurzes aber prägnantes Yes aus!
Sehen wir uns jetzt Zeile für Zeile den Programmcode zu buslinie.pl an:
%%Datenbestand:
buslinie(1,2).
buslinie(1,3).
buslinie(1,4).
buslinie(2,5).
buslinie(2,6).
buslinie(3,6).
buslinie(4,6).
buslinie(5,6).
%% und so weiter
bus(X,Y):- buslinie(X,Y);
buslinie(Y,X).
%% beide Richtungen erlaubt
anhaengen_an([X],L2,L):append(L2,[X],L).
enthalten(E,[E|_]).
enthalten(E,[_|L]):- enthalten(E,L).
wege(X,X,_).
wege(X,Y,L):- bus(X,Z),
55
not(enthalten(Z,L)),
anhaengen_an([Z],L,NL),
wege(Z,Y,NL).
Hier nun die Anfrage wege(1,6,[1]). im trace-Modus, - Zeile für Zeile kommentiert:
[trace] 21 ?- wege(1,6,[1]).
Call: (7) wege(1, 6, [1]) ? creep
Call: (8) bus(1, _L170) ? creep
Call: (9) buslinie(1, _L170) ? creep
Exit: (9) buslinie(1, 2) ? creep
Exit: (8) bus(1, 2) ? creep
^ Call: (8) not(enthalten(2, [1])) ? creep
Call: (9) enthalten(2, [1]) ? creep
Call: (10) enthalten(2, []) ? creep
Fail: (10) enthalten(2, []) ? creep
Fail: (9) enthalten(2, [1]) ? creep
^ Exit: (8) not(enthalten(2, [1])) ? creep
Call: (8) anhaengen_an([2], [1],
_L171) ? creep
Call: (9) lists:append([1], [2], _L171) ?
creep
Exit: (9) lists:append([1], [2], [1, 2]) ?
creep
Exit: (8) anhaengen_an([2], [1], [1, 2])
? creep
Call: (8) wege(2, 6, [1, 2]) ? creep
Call: (9) bus(2, _L231) ? creep
Call: (10) buslinie(2, _L231) ? creep
Exit: (10) buslinie(2, 5) ? creep
Exit: (9) bus(2, 5) ? creep
^ Call: (9) not(enthalten(5, [1, 2])) ?
creep
Call: (10) enthalten(5, [1, 2]) ? creep
Call: (11) enthalten(5, [2]) ? creep
Call: (12) enthalten(5, []) ? creep
Fail: (12) enthalten(5, []) ? creep
Fail: (11) enthalten(5, [2]) ? creep
Fail: (10) enthalten(5, [1, 2]) ? creep
^ Exit: (9) not(enthalten(5, [1, 2])) ?
creep
Call: (9) anhaengen_an([5], [1, 2],
_L232) ? creep
Call: (10) lists:append([1, 2], [5],
_L232) ? creep
Exit: (10) lists:append([1, 2], [5], [1, 2,
5]) ? creep
Gibt es einen Weg von 1 nach 6 ?
(Startpunkt 1 steht schon in der Liste)
1 ungleich 6, daher kein Abruch.
Gesucht in der Datenbank:
buslinie(1,_L170)
Versuch: _L170 = 2
Z = 2 klappt
Ergebnis: 2 ist nicht in L = [1] enthalten.
Also wird 2 hinten angefügt.
Somit L2 = [1,2]
2 ungleich 6, daher kein Abruch sondern
rekursiver Aufruf von wege mit L = L2
Gesucht in der Datenbank:
buslinie(1,_L231)
Versuch _L231 = 5
Z = 5 klappt
Ergebnis: 5 ist nicht in L = [1,2]
enthalten.
56
Exit: (9) anhaengen_an([5], [1, 2], [1,
2, 5]) ? creep
Call: (9) wege(5, 6, [1, 2, 5]) ? creep
Call: (10) bus(5, _L292) ? creep
Call: (11) buslinie(5, _L292) ? creep
Exit: (11) buslinie(5, 6) ? creep
Exit: (10) bus(5, 6) ? creep
^ Call: (10) not(enthalten(6, [1, 2, 5])) ?
creep
Call: (11) enthalten(6, [1, 2, 5]) ?
creep
Call: (12) enthalten(6, [2, 5]) ? creep
Call: (13) enthalten(6, [5]) ? creep
Call: (14) enthalten(6, []) ? creep
Fail: (14) enthalten(6, []) ? creep
Fail: (13) enthalten(6, [5]) ? creep
Fail: (12) enthalten(6, [2, 5]) ? creep
Fail: (11) enthalten(6, [1, 2, 5]) ? creep
^ Exit: (10) not(enthalten(6, [1, 2, 5])) ?
creep
Call: (10) anhaengen_an([6], [1, 2, 5],
_L293) ? creep
Call: (11) lists:append([1, 2, 5], [6],
_L293) ? creep
Exit: (11) lists:append([1, 2, 5], [6], [1,
2, 5, 6]) ? creep
Exit: (10) anhaengen_an([6], [1, 2, 5],
[1, 2, 5, 6]) ? creep
Call: (10) wege(6, 6, [1, 2, 5, 6]) ?
creep
Exit: (10) wege(6, 6, [1, 2, 5, 6]) ?
creep
Exit: (9) wege(5, 6, [1, 2, 5]) ? creep
Exit: (8) wege(2, 6, [1, 2]) ? creep
Exit: (7) wege(1, 6, [1]) ? creep
Yes
Also wird 5 hinten angefügt.
Somit L2 = [1,2,5]
5 ungleich 6, daher kein Abruch sondern
rekursiver Aufruf von wege mit L = L2
Gesucht in der Datenbank:
buslinie(1,_L292)
Versuch _L292 = 6
Z = 6 klappt
Ergebnis: 6 ist nicht in L = [1,2,5]
enthalten.
Also wird 6 hinten angefügt.
Somit L2 = [1,2,5,6]
6 = 6 also Ausstieg aus der Rekursion
und L = L2 = [1,2,5,6]
Rekursion jetzt wieder schrittweise
rückwärts….
mit dem Ergebnis, dass die Anfrage mit
Ja beantwortet werden kann!!
Nun hoffentlich ist Ihnen Prolog etwas weniger undurchsichtig....
57