Informatikmaterialien  von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges | | Inhalt | Vorherige Seite | Nächste Seite |

	Richard-Wossidlo-Gymnasium Ribnitz-Damgarten Fachbereich Informatik

Cut !

Die Lösungssuche in  PROLOG arbeitet u. a. mit dem des Backtrackings. Dieses Verfahren kann in einzelnen Fällen jedoch zu überflüssigen Suchen nach weiteren Lösungen führen und damit zu ineffektiven Programmen. PROLOG stellt das Prädikat CUT (geschrieben als !) zur Verfügung, mit dem das Backtracking verhindert werden kann. Man unterscheidet zwischen grünen und roten Cuts.

Beispiel – Grüner Cut

Das folgenden Programm liefert als Z das Maximums zweier Zahlen X und Y. An das System wird die Anfrage ?- maximum(5,3,3). gestellt.

maximum(X,Y,Z) :- X>=Y, Z=X. 
maximum(X,Y,Z) :- X<Y, Z=Y.

Die Analyse des Programms im UND-ODER-Beweisbaum zeigt, dass nach Setzen eines Backtrackingpunktes der rechte Teilbaum abgearbeitet wird. Der erste Test X >= Y ist zwar erfolgreich, der zweite jedoch nicht. Damit steht aber zwangsläufig fest, dass die Behauptung 3 sei das Maximum vom 5 und 3 falsch ist. Dennoch muss das System zum Backtrackingpunkt zurückkehren, um die zweite Alternative zu prüfen. Diese Prüfung ändert nichts am gefundenen Ergebnis, sie ist unnötig. Das zugehörige TRACE-Protokoll zeigt die unnötige Suche anschaulich:

Protokoll	Erläuterung
CALL: maximum(5,3,3)	Aufruf des Programms
COMP: maximum(X_1,Y_1,Z_1) :- X_1 >= Y_1 , Z_1 = X_1	erste Regel gefunden, Variablenumbenennung
INST: X_1 <--5	Instanzierung X_1 = 5
INST: Y_1 <--3	Instanzierung Y_1 = 3
INST: Z_1 <--3	Instanzierung Z_1 = 3
EXIT: maximum(5,3,3)	Instanzierungen erfolgreich
CALL: 5 >= 3	Aufruf/Prüfung ob 5 >= 3
EXIT: 5 >= 3	Prüfung erfolgreich
CALL: 3 = 5	Aufruf/Prüfung ob 3 = 5
FAIL: 3 = 5	Prüfung nicht erfolgreich
REDO: maximum(5,3,3)	Backtracking – Neuaufruf für zweite Regel
COMP: maximum(X_1,Y_1,Z_1) :- X_1 < Y_1 , Z_1 = Y_1	zweite Regel, Variablenumbenennung
INST: X_1 <--5 INST: Y_1 <--3 INST: Z_1 <--3 EXIT: maximum(5,3,3)	Instanzierungen erfolgreich
CALL: 5 < 3	Aufruf/Prüfung ob 5 < 3
FAIL: 5 < 3	Prüfung nicht erfolgreich
No	Ergebnis No

Aus diesem Grund kann man die Lösungssuche mit Hilfe des Cuts (Symbol !) abbrechen lassen. Die obige Anfrage führt zum gleichen Ergebnis. Das Programm lässt sich wie folgt ändern:

maximum(X,Y,Z) :- X>=Y, !, Z=X. 
maximum(X,Y,Z) :- X<Y, Z=Y.

Beim Übergang über der Cut, der stets wahr ist, werden alle bisher gesetzten Backtracking-Punkte gelöscht. Damit wird die zweite Regel nicht geprüft. Sehr anschaulich wird die Wirkung im TRACE-Protokoll:

Protokoll

Erläuterung

CALL: maximum(5,3,3)	Aufruf des Programms
COMP: maximum(X_1,Y_1,Z_1) :- X_1 >= Y_1 , ! , Z_1 = X_1	erste Regel gefunden, Variablenumbenennung
INST: X_1 <--5	Instanzierung X_1 = 5
INST: Y_1 <--3	Instanzierung Y_1 = 3
INST: Z_1 <--3	Instanzierung Z_1 = 3
EXIT: maximum(5,3,3)	Instanzierungen erfolgreich
CALL: 5 >= 3	Aufruf/Prüfung ob 5 >= 3
EXIT: 5 >= 3	Prüfung erfolgreich
CALL: !	Aufruf Cut – Löschen aller Backtrackingpunkte
EXIT: !	Cut ist stets erfolgreich
CALL: 3 = 5	Aufruf/Prüfung ob 3 = 5
FAIL: 3 = 5	Prüfung nicht erfolgreich
No	Ergebnis No

Definition

Das Prädikat Cut (Symbol !) wird verwendet, um unnötiges Backtracking zu verhindern. Der Cut ist stets erfolgreich. Wirkungen:  Beim "Überschreiten" eines Cuts werden alle bisher gesetzten Backtrackingpunkte gelöscht. Die lokale Wirkung bezieht sich auf die Klausel, in dem der Cut vorkommt. Die globale Wirkung des Cuts bezieht sich auf das Prädikat, in dem er vorkommt.  Arten: Ein grüner Cut schneidet Zweige des Suchbaumes ab, die keine Lösungen enthalten. Ein roter Cut schneidet Zweige des Suchbaumes ab, die Lösungen enthalten. Diesen Cut sollte man vermeiden.

Beispiel – Roter Cut (nach Röhner, 1995)

Das Listen-Prädikat member war wie folgt festgelegt:

member(X,L) :- L=[X|_].
member(X,L) :- L=[_,Y], member(X,Y).

Ist die Liste L definiert mit L=[a,b,c,a,d,e,a], so führt die Anfrage ?- member(a,L) zu drei Lösungen. Durch benutzen eines Cuts lässt sich dies verhindern.

member(X,L) :- L=[X|_],!.
member(X,L) :- L=[_,Y], member(X,Y).

Nun wird, sobald eine Lösung gefunden wurde, die Lösungssuche abgebrochen. Stellt man die Anfrage ?- member(X,L), so erwartet man entweder 7 (da ja sieben Elemente in der Liste sind), oder 5 (da ja fünf verschiedene Elemente in der Liste sind). In Wirklichkeit findet Prolog nur die Antwort X = a. Den Rest schneidet der Cut ab. Er ist deshalb ein roter Cut.

zur Startseite

© Tino Hempel 1997 - 2018

Im Web vertreten seit 1994. Eine Internet-Seite aus dem Angebot von Tino Hempel. Für alle Seiten gilt der  Haftungsausschluss/Disclaimer.