2012-09-03 13 views
12

मैंने quite interesting question पर जो जवाब दिया था, उसका उत्तर लिखा, लेकिन दुर्भाग्य से प्रश्न पोस्ट करने से पहले इसके लेखक द्वारा प्रश्न हटा दिया गया था। मैं प्रश्न का सारांश दोबारा पोस्ट कर रहा हूं और यहां मेरा जवाब अगर किसी और के लिए उपयोग किया जा सकता है।क्या सभी समाधान खोजने के लिए एसएटी सॉल्वर का उपयोग किया जा सकता है?

मान लीजिए मैं एक सैट solver कि, संयोजक सामान्य रूप में एक बूलियन सूत्र दिया, रिटर्न या तो एक समाधान (एक चर काम है कि सूत्र को संतुष्ट करता है) या जानकारी है कि समस्या unsatisfiable है।

क्या मैं सभी समाधान खोजने के लिए इस सॉल्वर का उपयोग कर सकता हूं?

+0

व्यक्ति जो कृपया downvoted व्याख्या कर सकते हैं क्यों? इस ब्लॉग एंट्री को पढ़ने के बाद (http://blog.stackoverflow.com/2011/07/its-ok-to-ask-and-answer-your-own-questions/), मैंने सोचा कि मैंने यहां क्या किया था "न केवल ठीक है, "लेकिन" स्पष्ट रूप से प्रोत्साहित किया। " – Vectornaut

+1

यह बिल्कुल ठीक है। अच्छा जवाब, बीटीडब्ल्यू। –

उत्तर

8

एसएटी समस्या का सभी समाधान खोजने के लिए वर्णित एसएटी सॉल्वर का उपयोग करने का निश्चित रूप से एक तरीका है, हालांकि यह सबसे प्रभावी तरीका नहीं हो सकता है।

बस अपनी मूल समस्या का हल ढूंढने के लिए सॉल्वर का उपयोग करें, एक ऐसा खंड जोड़ें जो आपके द्वारा अभी मिले समाधान को रद्द करने के अलावा कुछ भी नहीं करता है, नई समस्या का हल ढूंढने के लिए सॉल्वर का उपयोग करें, और आगे। तब तक जारी रहें जब तक आपको कोई समस्या न हो जो असंतुष्ट है।


उदाहरण के लिए, आप (X or Y) and (X or Z) को संतुष्ट रखना चाहते हैं।

  • X सच है, Y और Z मनमाना साथ चार: वहाँ पाँच समाधान कर रहे हैं।

  • X झूठी, Y और Z सत्य के साथ एक।

तो आप अपने solver चलाते हैं, और मान लें कि यह आप समाधान (X, Y, Z) = (T, F, F) देता हैं। आप बाधा

not (X and (not Y) and (not Z)) 

साथ --- इस समाधान --- और केवल इस समाधान से इनकार कर सकते हैं इस बाधा खंड

(not X) or Y or Z 

तो अब आप पर अपने solver चला सकते हैं के रूप में लिखा जा सकता है नई समस्या

(X or Y) and (X or Z) and ((not X) or Y or Z) 

और बहुत आगे।


जैसा मैंने कहा, यह वही करने का एक तरीका है जो आप चाहते हैं, लेकिन यह शायद सबसे प्रभावी तरीका नहीं है। जब आपका एसएटी सॉल्वर समाधान की तलाश में है, तो यह समस्या के बारे में बहुत कुछ सीखता है, लेकिन यह आपको वह सारी जानकारी वापस नहीं देता है --- यह आपको वह समाधान देता है जो इसे मिला। जब आप फिर से सॉल्वर चलाते हैं, तो उसे दूर की गई सारी जानकारी को फिर से सीखना होता है।

8

निश्चित रूप से यह कर सकता है।MiniSat [1] एक समाधान पाता है

s SATISFIABLE 
v 1 2 -3 0 

(समाधान 1 = True, 2 = True, 3 = False) तो आप मूल CNF [2] एक खंड है कि इस समाधान पर रोक लगाई में डाल करने के लिए है:

-1 -2 3 0 

(जिसका अर्थ है, या तो 1 या 2 False होना चाहिए या 3 True होना चाहिए)। फिर आप फिर से हल करते हैं। आप तब तक ऐसा करते हैं जब सॉल्वर यूएनएसएटी को वापस लौटाता है यानी समस्या का कोई और समाधान नहीं होता है। आप प्रत्येक पुनरावृत्ति के लिए एक खंड डालेंगे, और प्रत्येक खंड में समाधान के समान प्रारूप होगा, सिवाय इसके कि यह सभी उलटा हुआ है और 0 अंत में

मिनीसैट के C++ इंटरफ़ेस का उपयोग करके ऐसा करने में बहुत तेज़ है, यह तब मध्यवर्ती डेटा बचा सकता है और पुनरावृत्तियों तेजी से हो जाएगा।

[1] http://minisat.se/

[2] http://fairmut3x.wordpress.com/2011/07/29/cnf-conjunctive-normal-form-dimacs-format-explained/

संबंधित मुद्दे

 संबंधित मुद्दे