SWI-Prolog und Constraints, Bibliothek CLP (FD)

Question

Ich spiele mit Einschränkungen in (Swi) Prolog mit der Clpfd-Bibliothek.

Ich versuche zu identifizieren, wenn ein Satz von Einschränkungen den anderen einkapselt oder subsumiert, z. X < 4 kapselt X < 7 wie immer, wenn ersteres wahr ist, letzteres ist wahr. Dies kann leicht durch logische Implikation dargestellt werden. Allerdings konnte ich den # ==> Operator nicht erhalten, um mir das gewünschte Ergebnis zu geben, also habe ich auf die Verwendung von nicht (Co1 #/\ # \ Co2) zurückgegriffen, wobei Co1 und Co2 Beschränkungen sind. Das ist für einzelne Constraints gut, aber ich wollte dann Conjunctions von Constraints in Co1 und Co2 übergeben.

Jetzt ist hier die reibung. Als ich

X#<7 #/\ #\X#<4. 

versuchen bekomme ich zurück

X in 4..6, 
X+1#=_G822, 
X+1#=_G834, 
_G822 in 5..7, 
_G834 in 5..7. 

(seltsam genug, dies in einem Segmentierungsfehler in SICStus Ergebnisse tun)

Wenn ich pass in

X#<7,X#<4 

I Holen Sie sich die gewünschte

X in inf..3. 

Offensichtlich kann ich letzteres nicht übergeben (Co1 #/\ # \ Co2), aber ersteres gibt mir nicht das Ergebnis, das ich will. Kann jemand erklären, warum die beiden Ansätze zu unterschiedlichen Ergebnissen führen, und wie kann ich die beiden dazu bringen, so zu handeln?

Answer 1

Es scheint, Sie haben mit CLP (FD) zu tun. Diese Löser unterscheiden zwischen der Setup-Phase und der Markierungsphase, in der ein Constraint-Problem gelöst wird.

Ein CLP (FD) Solver reduziert ein Problem während der Einrichtungsphase nicht vollständig. Da es die Möglichkeit hat, variable Bereiche während der Markierungsphase zu reduzieren. So könnte es sein, dass während des Setups ein Problem auftritt, das von anderen Solvern auf "Nein" reduziert werden könnte, aber nicht mit einem CLP (FD) Solver. Nur während der Beschriftung wird ein "Nein" erkannt.

Wie stark die Reduzierung in der Setup-Phase vorgenommen wird, hängt stark vom jeweiligen CLP (FD) System ab. Einige CLP (FD) -Systeme machen während der Einrichtungsphase mehr Reduktion, während andere weniger tun. GNU Prolog verwendet zum Beispiel eine indexikalische Propagation, während SWI Prolog dies nicht tut.So finden wir zum Beispiel nicht Ihr Beispiel:

SWI-Prolog:

?- X #< Y, Y #< Z, Z #< X. 
Z#=<X+ -1, 
X#=<Y+ -1, 
Y#=<Z+ -1. 

GNU Prolog:

?- X #< Y, Y #< Z, Z #< X. 
(7842 ms) no 

Weitere da Sie verdinglicht Einschränkungen verwenden es hängt auch ein wenig wie klug Die Verdinglichung ist getan. Aber ich denke, im vorliegenden Fall handelt es sich nur um eine Vermehrung. Wir finden jetzt Ihr Beispiel:

SWI-Prolog:

?- X #< 4 #==> X #< 7. 
X+1#=_G1330, 
X+1#=_G1342, 
7#>=_G1330#<==>_G1354, 
_G1354 in 0..1, 
_G1377#==>_G1354, 
_G1377 in 0..1, 
4#>=_G1342#<==>_G1377. 

GNU Prolog:

?- X #< 4 #==> X #< 7. 
X = _#22(0..268435455) 

Es ist ein Kompromiss zwischen mehr Reduktion in der Aufbauphase zu tun und mehr Arbeit der Abgänge Markierungsphase. Und die ganze Sache hängt auch von dem gegebenen Beispiel ab. Aber wenn man auch neben Setup-Kennzeichnung haben, werden Sie keinen Unterschied in Bezug auf die Ergebnisse sehen:

SWI-Prolog:

?- X in 0..9, X #< 4 #==> X #< 7, label([X]). 
X = 0 ; 
X = 1 ; 
X = 2 ; 
X = 3 ; 
X = 4 ; 
X = 5 ; 
X = 6 ; 
X = 7 ; 
X = 8 ; 
X = 9. 

GNU Prolog:

?- fd_domain(X,0,9), X #< 4 #==> X #< 7, fd_labeling([X]). 
X = 0 ? ; 
X = 1 ? ; 
X = 2 ? ; 
X = 3 ? ; 
X = 4 ? ; 
X = 5 ? ; 
X = 6 ? ; 
X = 7 ? ; 
X = 8 ? ; 
X = 9 

habe ich nicht getestet mit SICStus Prolog oder B-Prolog. Aber ich denke, sie werden sich irgendwo in der Nähe von SWI-Prolog und GNU Prolog verhalten.

CLP (Q) ist keine echte Alternative, wenn Ihre Domäne wirklich FD ist, da es einige "Nein" -Reduktionen vermissen wird, die CLP (FD) nicht verpassen würde. Zum Beispiel ist die folgende unerfüllbar in CLP (FD), aber erfüllbar in CLP (Q):

X = Y + 1, Y < Z, Z < X. 

Bye

Answer 2

Die Unterteilung der allgemeinen arithmetischen Constraints über die ganzen Zahlen ist im Allgemeinen unentscheidbar, so dass alle korrekten Löser inhärente Grenzen haben, hinter denen sie ihre Antworten verzögern müssen, bis mehr bekannt ist. Wenn Sie wissen, dass Ihre Domänen endlich sind, können Sie die Domänen posten und dann versuchen, Gegenbeispiele zu finden, die die Implikation mit dem Labeling/2-Prädikat des Constraint-Solver ungültig machen würden. Beachten Sie auch, dass lineare Ungleichungen über Q entscheidbar sind und dass die SWI-Prolog-Bibliothek (clpq) für sie vollständig ist. So können Sie Ihre Einschränkungen in CLP (Q) versuchen, mit:

?- use_module(library(clpq)). 
true. 

?- { X < 4, X >= 7 }. 
false. 

und sehen, dass kein solches Gegenbeispiel in Q vorhanden ist (daher auch nicht in Z) und damit die Implikation hält.