यहां कुछ विचार।
एक वेनिला ब्रूट फोर्स एल्गोरिदम एक निश्चित क्रम (जैसे पंक्ति प्रमुख) में ग्रिड पोजिशन को समझाकर ग्रिड को भरने का प्रयास करेगा और हमेशा मौजूदा स्थिति में हर संभावित टुकड़े को फिट करने और फिर रिकर्सिंग करने का प्रयास करेगा। आपने जो उल्लेख किया है और यह बहुत अक्षम है।
एक सुधार हमेशा हर मुक्त स्थिति टुकड़े कि फिट की संख्या के लिए गिनती करने के लिए, और उसके बाद की स्थिति है कम से कम फिट बैठता है कि पर recurse है; अगर किसी के पास शून्य फिटिंग टुकड़े हैं, तो तुरंत बैकट्रैक; यदि कोई ऐसा स्थान है जहां केवल एक टुकड़ा भरता है और जारी रहता है (कोई शाखा नहीं बनाई जाती है); अन्यथा उस व्यक्ति का चयन करें जिसमें कम से कम फिटिंग टुकड़े (≥ 2) हैं और वहां से जारी रखें।
एक बार जब आपके पास यह एल्गोरिदम होता है, तो अगला प्रश्न यह है कि आप खोज स्थान को और कैसे छीन सकते हैं। यदि कहें, तो शीर्ष स्थिति पर "1" के साथ एक टुकड़े और नीचे की स्थिति पर "1" के साथ बी टुकड़े, और ए> बी, तो आप जानते हैं कि कम से कम ए - बी "शीर्ष स्थान पर" 1 के टुकड़े वास्तव में शीर्ष पंक्ति पर रखा जाना चाहिए, ताकि आप उन्हें किसी अन्य स्थिति से बाहर कर सकें। इससे शाखाकरण कारक को कम करने और पहले मृत-अंत को स्थानांतरित करने में मदद मिलती है।
तुम भी है कि हर टुकड़ा कम से कम एक स्थान (पुष्टि करने के लिए कोई टुकड़ा है कि गति के लिए केवल एक ही स्थान पर फिट बैठता है है कि वहाँ के बाद इस चेक करते हैं) जहां यह फिट बैठता है कि हर प्रत्यावर्तन कदम पर जांच होनी चाहिए। यदि कोई ऐसा टुकड़ा है जो कहीं भी फिट नहीं होता है तो आपको तुरंत बैकट्रैक की आवश्यकता होती है। आप यह जांचने के लिए विस्तार कर सकते हैं कि प्रत्येक टुकड़े की जोड़ी फिट हो सकती है जो संभावित रूप से बेहतर मृत-लॉक जांच क्षमता के लिए उपयुक्त है।
"गैर-कालक्रम संबंधी बैकट्रैकिंग" या "बैकजंपिंग" नामक एक रणनीति भी है जो अनुसंधान से एसएटी सुलझाने में उत्पन्न होती है। जब आप एक मृत अंत तक पहुंचते हैं तो यह आपको एक से अधिक स्तरों पर बैकट्रैक करने में मदद करता है; यदि आप चाहते हैं, तो आप अधिक जानने के लिए इन शर्तों के लिए Google पर जा सकते हैं, लेकिन आपको अपनी समस्या स्थान में अवधारणा को मानचित्रित करने के लिए कुछ मानसिक कार्य करने की आवश्यकता है।
स्रोत
2010-02-08 19:10:17
बहुत बहुत धन्यवाद, यह वास्तव में सहायक था (भले ही कुछ बिंदु पहले हाइलाइट किए गए थे) और आपके द्वारा उल्लिखित शर्तों में और अधिक देखेंगे। – Erethon