एसडब्ल्यूआई-प्रोलॉग और बाधाएं, लाइब्रेरी सीएलपी (एफडी)

Question

मैं clpfd लाइब्रेरी का उपयोग कर (swi) prolog में बाधाओं के साथ खेल रहा हूं।

मैं पहचानने की कोशिश कर रहा हूं कि बाधाओं का एक सेट दूसरे को समाहित करता है या उदाहरण देता है, उदा। एक्स < 4 एक्स < 7 encapsulates जब भी पूर्व सच है, बाद वाला सच है। यह तार्किक निहितार्थ का उपयोग करके आसानी से प्रतिनिधित्व किया जा सकता है। हालांकि, मुझे परिणाम प्राप्त करने के लिए # ==> ऑपरेटर नहीं मिल सका, इसलिए मैंने (Co1 #/\ # \ Co2) का उपयोग करने का सहारा लिया जहां Co1 और Co2 बाधाएं हैं। यह व्यक्तिगत बाधाओं के लिए ठीक है, लेकिन मैं तब Co1 और Co2 में बाधाओं के संयोजन को पारित करना चाहता था।

अब यहां रगड़ है। जब मैं

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

कोशिश मैं वापस (विचित्र रूप से पर्याप्त, एक विभाजन गलती में Sicstus परिणामों में यह कर) प्राप्त

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

जब मैं में

X#<7,X#<4 

मैं पारित वांछित

प्राप्त करें

जाहिर है, मैं बाद में पास नहीं कर सकता (Co1 #/\ # \ Co2), लेकिन पूर्व मुझे वह परिणाम नहीं देता है जो मैं चाहता हूं। क्या कोई यह समझा सकता है कि दोनों दृष्टिकोण अलग-अलग नतीजे क्यों देते हैं, और मैं पूर्व को कैसे बाद में कार्य करने के लिए प्राप्त कर सकता हूं?

Answer 1

ऐसा लगता है कि आप सीएलपी (एफडी) से निपट रहे हैं। ये सॉल्वर सेटअप चरण और एक बाधा समस्या को हल करने के लेबलिंग चरण को अलग करते हैं।

एक सीएलपी (एफडी) सॉल्वर सेटअप चरण के दौरान पूरी तरह से समस्या को कम नहीं करता है। चूंकि लेबलिंग चरण के दौरान परिवर्तनीय श्रेणियों को कम करने का मौका है। इस प्रकार यह हो सकता है कि सेटअप के दौरान एक समस्या उत्पन्न की जाती है जिसे अन्य हलकों द्वारा "नहीं" तक कम किया जा सकता है, लेकिन यह सीएलपी (एफडी) सॉल्वर के साथ नहीं होगा। केवल "नहीं" लेबलिंग के दौरान पता लगाया जाएगा।

सेटअप चरण के दौरान कितनी कमी की जाती है, दी गई सीएलपी (एफडी) प्रणाली पर अत्यधिक निर्भर करता है। कुछ सीएलपी (एफडी) सिस्टम सेटअप चरण के दौरान अधिक कमी करते हैं, जबकि अन्य कम करते हैं। उदाहरण के लिए जीएनयू प्रोलॉग कुछ इंडेक्सिकल प्रचार का उपयोग करता है, जबकि एसडब्ल्यूआई प्रोलॉग नहीं करता है।इसलिए हम उदाहरण के लिए मिल जाए, नहीं अपने उदाहरण:

SWI-Prolog:

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

जीएनयू Prolog:

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

इसके अलावा जब से तुम reified की कमी का उपयोग कर रहे यह भी एक छोटा सा कैसे चतुर निर्भर करता है संशोधन किया जाता है। लेकिन मुझे लगता है कि वर्तमान मामले में केवल प्रचार का मामला है।

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. 

जीएनयू Prolog: हम आपके उदाहरण के लिए अब लगता है

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

सेटअप चरण में अधिक कमी कर रहे हैं और के लिए और अधिक काम छोड़ने के बीच एक समंजन नहीं है लेबलिंग चरण। और पूरा मामला भी दिए गए उदाहरण पर निर्भर करता है।

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. 

जीएनयू 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 

मैं परीक्षण नहीं किया था लेकिन जब आप भी सेटअप के बगल में लेबलिंग है, तो आप परिणाम के मामले में कोई अंतर नहीं देखेंगे एसआईसीस्टस प्रोलॉग या बी-प्रोलॉग के साथ। लेकिन मुझे लगता है कि वे एसडब्ल्यूआई-प्रोलॉग और जीएनयू प्रोलॉग के आस-पास में कहीं भी व्यवहार करेंगे।

सीएलपी (क्यू) कोई वास्तविक विकल्प नहीं है यदि आपका डोमेन वास्तव में एफडी है, क्योंकि इससे कुछ "नहीं" कमी आएगी, जो सीएलपी (एफडी) याद नहीं करेंगे।

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

अलविदा

Answer 2

पूर्णांक पर सामान्य अंकगणितीय बाधाओं की सब्सक्रिप्शन सामान्य रूप से अपरिहार्य है, इसलिए सभी सही हलकों में अंतर्निहित सीमाएं होती हैं, जिनसे उन्हें अधिक जवाब ज्ञात होने तक उनके उत्तरों में देरी होनी पड़ती है। यदि आप अपने डोमेन को परिमित होने के बारे में जानते हैं, तो आप डोमेन पोस्ट कर सकते हैं और फिर गिनती सॉल्वर के लेबलिंग/2 भविष्यवाणी का उपयोग करके, इत्यादि को अमान्य बना देंगे। इस बात पर भी विचार करें कि क्यू पर रैखिक असमानताओं को निर्णायक माना जाता है, और एसडब्ल्यूआई-प्रोलॉग पुस्तकालय (सीएलपीक्यू) उनके लिए पूरा हो गया है। आप इस प्रकार के साथ सीएलपी (क्यू) में अपने बाधाओं की कोशिश कर सकते हैं:

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

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

और देखते हैं कि ऐसी कोई counterexample क्यू में (जेड में नहीं इसलिए भी) मौजूद है, और इस तरह निहितार्थ रखती है।