LbP Programmiertechniken
Aus ProgrammingWiki
Inhaltsverzeichnis |
Programmiertechniken mit Logik-orientierten Sprachen
Generate and test
Hierbei wird die inhärent nichtdeterministische Lösungssuche von Prolog ausgenutzt, indem fortlaufend Lösungsvorschläge erzeugt und anschliessend verifiziert werden. Als Regel formuliert, heisst das
find(S) :- generate(S), test(S).
Diese Lösungstechnik bietet sich vor allem für NP-vollständige Probleme an, da für diese kein effizientes Lösungsverfahren bekannt ist. Aufgrund der in Prolog üblicherweise eingebauten Tiefensuche und Backtracking, arbeitet auch generate nach diesem Prinzip.
Effizienzverbesserungen lassen sich erzielen, wenn man generate und test miteinander verzahnt. D.h., unmittelbar nach Bereitstellung eines Kandidaten für eine Teillösung wird geprüft, ob sich die Fortsetzung der Suche in der eingeschlagenen Richtung noch lohnt. Auf diese Weise können aussichtslose Teile des Suchbaumes ausgespart werden.
Beispiel: "Vierfarbenproblem für Deutschlandkarte" Färben einer Landkarte mit 4 Farben, so dass keine 2 benachbarten Regionen die gleiche Farbe haben. Das Viefarbenproblem wurde 1976 gelöst. member/2 soll als Systemprädikat angenommen werden.
Die berechnete Farbfolge korrespondiert mit der write-Reihenfolge der Bundesländerkürzel.
select und sublist können im Verlauf der Berechnung mit instanziierten und nichtinstanziierten Variablen aufgerufen werden. Diese Bidirektionalität lässt sie einmal in der Funktion eines Generatorprädikates und einmal in der eines Testprädikates auftreten.
Beispiel: Permutationssortieren (Übungsaufgabe) Die "generate and test"-Idee bedeutet für dieses Beispiel: Erzeugung je einer Permutation und sofortige Prüfung, ob sie eine sortierte Liste darstellt.
Das Verfahren ist natürlich sehr ineffizient, sodass schon bei kleinen Listen erhebliche Wartezeiten entstehen können.
Akkumulatortechnik
Die Idee besteht darin, ein n+1-stelliges Prädikat aus einem n-stelligen zu konstruieren, indem eine zusätzliche Variable angefügt wird. Man spricht von Akkumulatorvariable. In dieser wird das Resultat schrittweise aufgebaut. (Das Verfahren ist auch im funktionsorientierten Programmieren populär.)
myreverse/2 aus dem Abschnitt über Listen arbeitet ineffizient. Zur Erinnerung wird hier die Definition wiederholt.
Verfolgen Sie alle Berechnungsschritte - auch mit Handrechnung. Die rekursive Abarbeitung geht n Schritte in die Tiefe und hat dann noch den ebensolangen Aufstieg zu erledigen, wenn n die Länge der zu spiegelnden Liste ist. Der Zeitaufwand liegt also in O(n²).
Unter Verwendung einer Akkumulatorvariablen kann die rekursive in eine zugehörige iterative Berechnung umgewandelt werden. Für unser Beispiel zeigt myrev/3 eine Lösung. Hinweis: Um Verwechslungen vorzubeugen, verwenden wir myrev/3 anstelle myreverse/3, da Menschen - ganz im Gegensatz zu Prolog - myreverse/2 und myreverse/3 nicht so klar zu unterscheiden vermögen.
Die Umkehrliste wird nun in einer Zeit in O(n) berechnet. Analysieren Sie dies mittels Handrechnung!
Differenzlisten
Eine Liste ist eine Datenstruktur zur Repräsentation einer Folge von Elementen. Listen sind in Prolog eingebaute Basisdatentypen. Zur externen Repräsentation von Listen werden eckige Klammern [, ] verwendet.
Die Differenzlistentechnik geht von einer speziellen Darstellungsform von Listen als Differenz zweier Listen, kurz: L1\L2, aus. Elementsequenzen können alternativ auch als Differenzlisten repräsentiert werden. Beispielsweise kann die Liste [1,2,3] als [1,2,3,4,5]\[4,5] geschrieben werden, wobei klar ist, dass dies nicht die einzige Möglichkeit ist. Ebensogut wäre [1,2,3,4,5,a,b,c]\[4,5,a,b,c] möglich.
Allgemein gilt [1,2,3] = [1,2,3|Xs]\Xs, wobei man Xs als Lückenvariable im Sinne eines Platzhalters bezeichnet. [1,2,3|Xs] ist der Kopf (head) der Differenzliste und Xs ist ihr Rest (tail).
Eine beliebige Liste Ls lässt sich als Differenz aus Ls und der leeren Liste, also durch Ls\[], darstellen. Die zur leeren Liste [] gehörende Differenzliste ist Ls\Ls, wobei Ls eine beliebige Liste ist.
Zur Definition eines Prädikats reverse_dl, auf das wir weiter unten eingehen werden, wird daher für den Fall der leeren Liste geschrieben als reverse_dl([], Ls-Ls). Obwohl man Differenzlisten auch durch zwei Parameter (head, tail) darstellen könnte, stellt SWI-Prolog das (zweistellige) Prädikat - in Infixnotation zur Verfügung. Diese Darstellung erleichtert das Lesen von Differenzlisten enorm.
Durch den Gebrauch von Differenzlisten kann die Effizienz bestimmter Operationen oder Prädikate beachtlich verbessert werden. Beispielsweise wird für die Verkettung zweier Listen As und Bs unter Verwendung des im Folgenden definierten Prädikats myappend eine Zeit in O(n) benötigt, wobei n die Länge der ersten Liste (As) bezeichnet.
Fügen Sie in der Definition von myappend an geeigneten Stellen write-Anwendungen ein, um den Prozess der Abarbeitung zu protokollieren. Bedingt durch Rekursion (Abstieg/Aufstieg) sind gerade 2n Schritte notwendig, um die Verkettungsliste zu bilden.
Unter Verwendung von Diffenzlisten für As und Bs gelingt die Verkettung mit append_dl sogar in konstanter Zeit. Die Definition lautet:
.Die Unifikation sorgt dafür, dass die Resultatliste nur durch Anwendung des head-tail-Separators entsteht. Intern ist also nur eine Zeigeroperation nötig, nämlich das Richten des Endezeigers von As auf den Anfang von Bs.
Beispiel: Umkehrliste reverse_dl(As,Bs) - Bs ist die Umkehrliste von As
In diesem Beispiel bleibt die rekursive Idee der Erzeugung der Umkehrliste erhalten. Im Übrigen kann man eine Definitionszeile ergänzen, um die Gebrauch von reverse_dl von der Repräsentation der Folgen durch Differenzlisten abzukoppeln (representation independence).
Die Differenzlistendarstellung ist dann allerdings noch an der Ergebnisausgabe erkennbar:
Beispiel: "Glätten" einer Liste: flatten_dl
flat (engl.) bedeutet flach; flatten heißt dann soetwas wie "flach machen", besser "ebnen". Angewandt auf Listen heißt das: Eine beliebig verschachtelte Liste wird in eine unverschachtelte überführt, indem die atomaren Elemente der Teillisten als Elemente der "flachen" Resultatliste erscheinen.
Wir geben zunächst eine Definition, die Standard-Listen (nicht Differenzlisten) verwendet.
Wir wollen myflatten nun so zu flatten_dl umschreiben, dass die Differenzlistentechnik eingesetzt wird.
Es ist durchaus sinnvoll, ein Prädikat flatten_akku unter Benutzung der Akkumulatortechnik zu schreiben.
Beispiel: Sortieren einer Liste mit Quicksort mit quicksort
In quicksort(As,Bs) ist As eine beliebige Permutation einer Menge von Elementen und Bs ist die aufsteigend sortierte Liste aus den Elementen von As.
Die verwendeten Symbole wurden so benannt, dass sie an bestimmte Bedeutungen erinnern:
T ... Trennelement
Ls ... linke Teilliste
Rs ... rechte Teilliste
Zur Sortierung der Liste [2,4,1,8,5,3,9,2,7] beantwortet Prolog die Frage
Memoizing und adaptive Programme
Die Idee, die dieser Technik zugrunde liegt, ist die Modifikation eines Prolog-Programms während der Laufzeit. Dies bedeutet, dass Fakten oder Regeln während des Berechnungsprozesses ergänzt, entfernt oder modifiziert werden können.
Zum Anfügen neuer Klauseln am Anfang, also vor evtl. vorhandenen Klauseln mit gleichnamigem Funktor und gleicher Stelligkeit, verwendet man asserta(<klausel>). Soll dies am Ende geschehen, nimmt man assert bzw. assertz. Das Entfernen eines zweistelligen Prädikats erledigt retractall(<funktor(_,_)>).
Dem Interpreter muss allerdings mittels dynamic mitgeteilt werden, dass sich die Definition des betreffenden Prädikats zur Laufzeit ändern wird.
Beispiel: Fibonacci ohne bzw. mit Memoizing
Die Ergebnisse der folgenden Anfragen beindrucken insbesondere durch die sehr unterschiedliche Bearbeitungszeit.
Es kann durchaus einige Minuten dauern, bis das Resultat, nämlich 17711, vorliegt. Im Gegensatz dazu, kann sogar
in Sekundenbruchteilen berechnet werden.
Mit dem Modifizieren vorhandener Prädikate werden wir uns hier nicht befassen. Es kann als Kopieren, Löschen des alten Prädikats und Anfügen der modifierten Kopie realisiert werden.
Übungsaufgaben
- Schreiben Sie ein Prolog-Programm zur Sortierung einer Liste von Zufallszahlen. Es soll jeweils eine Permutation erzeugt werden, die anschliessend auf "Sortiertheit" untersucht wird (generate and test). Vergleichen Sie Ihr Resultat mit dem Programm in obigem Text.
- Schreiben Sie ein Prolog-Programm zum Primzahltest.
- Realisieren Sie die Berechnung der n-ten Fibonaccizahl mit memoizing. Memoizing bedeutet, dass einmal berechnete Werte aufbewahrt werden. Vor jeder Neuberechnung wird geprüft, ob das gesuchte Resultat schon vorliegt. Ist dies das Fall, wird es genommen.
Memoizing realisiert man mit Prolog durch dynamisches Ergänzen von Fakten in der Datenbasis. Machen Sie sich zu diesem Zweck mit asserta vertraut. Berechnen Sie die 1000-te Fibonaccizahl unter Benutzung der bekannten rekursiven Definition und memoizing.
- Schreiben Sie ein Prädikat reverse_dl/2 für die Bestimmung der Umkehrliste mit Differenzlistentechnik.
