एल्गोरिथम एक्स या एक लकड़ी की पहेली और एक डांसिंग लिंक के बीच क्या आम है?

प्रस्तावना

एक बार एक पार्टी में मैं एक पहेली में आया था जिसमें मुझे 25 समान आंकड़ों में से एक क्यूब को इकट्ठा करने की आवश्यकता थी। मैंने पूरी शाम उसके साथ बिताई, और जैसा कि आप अनुमान लगा सकते हैं, कोई फायदा नहीं हुआ। हालाँकि, मैं इस तरह से हार नहीं मान सकता था।

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

गति में इस अंतर से मुझे पता चला कि इस समस्या और इस तरह के अन्य लोगों की एक पूरी कक्षा को कैसे हल किया जाए।







यह पहेली सटीक कवरेज समस्या का एक क्लासिक प्रतिनिधि है ।

समस्या कथन निम्नलिखित उदाहरण का उपयोग करके प्रस्तुत किया जा सकता है। आप संग्रहणीय कार्ड के लिए स्टोर पर आते हैं। डुप्लिकेट कार्ड के बिना एक पूर्ण संग्रह को एक साथ रखने के लिए आपको क्या डेक खरीदना चाहिए?

ऐसे कार्य के लिए, डोनाल्ड नथ का एल्गोरिदम एक्स है । लेकिन एल्गोरिथ्म पर विचार करने के लिए आगे बढ़ने से पहले, आइए देखें कि हमारी घन पहेली को सटीक कवरेज समस्या में कैसे कम किया जाए।

कार्य की औपचारिकता

सादगी के लिए, हम चार फ्लैट कोनों में से एक बड़े कोने को मोड़ने की इसी तरह की समस्या को हल करेंगे। यदि आंकड़ा मुड़ा हुआ है, तो आकृति का प्रत्येक वर्ग एक और केवल एक कोने का है, जिसे आप देखते हैं, पहले से ही पूर्ण कवरेज की समस्या के बयान के समान है।



आइए हम बड़ी संख्या के सभी वर्गों की संख्याओं को निरूपित करते हैं, और इसके अंदर छोटे कोने के सभी संभावित पदों को अक्षर द्वारा (यहां, स्पष्टता के लिए, कोनों के कुछ "खराब" स्थान जो समाधान में मौजूद नहीं हो सकते हैं, जानबूझकर फेंक दिए गए हैं)। 12 चौकों का सेट सिर्फ इतना है कि हम एएल के प्रावधानों के साथ कवर करने की कोशिश करेंगे। कार्य को तालिका ( घटना मैट्रिक्स ) के रूप में भी प्रस्तुत किया जा सकता है। स्तंभ वर्गों के अनुरूप होंगे, पंक्तियाँ कोने की स्थिति के अनुरूप होंगी, और स्तंभ के चौराहे पर इकाई और पंक्ति को रखा जाएगा यदि कोने की संबंधित स्थिति को संबंधित वर्ग द्वारा कवर किया गया हो।





थोड़े कम स्पष्ट तरीके से, एक पहेली जिसमें सभी टुकड़े अलग हैं, या सुडोकू जैसे खेल, पूर्ण कवरेज की समस्या के लिए कम है। पाठक को स्वतंत्र रूप से यह सोचने के लिए आमंत्रित किया जाता है कि इन स्थितियों को कैसे औपचारिक किया जाए (यदि ऐसा है तो इसका जवाब विकिपीडिया पर है )।

एल्गोरिथम एक्स

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

चरण 1. मैट्रिक्स एस में कुछ कॉलम सी का चयन करें

एक ज्यामितीय भाषा में एक कॉलम चुनने का मतलब है कि एक वर्ग चुनना जो अभी तक कवर नहीं किया गया है। हमारे मामले में, यह एक वर्ग 24 होगा।

चरण 2. प्रत्येक पंक्ति आर के लिए एल्गोरिथ्म को फोर्क करें जैसे कि एस _{आर, सी} = 1

बॉक्स 24 को ए या स्थिति डी द्वारा बंद किया जा सकता है। हमारे पास एक या दूसरे को चुनने के लिए कोई शर्त नहीं है, इसलिए हम दोनों विकल्पों पर अलग से विचार करते हैं। यह वह कदम है जो विकल्पों की गणना करता है। अपनी संख्या को कम करने के लिए, अक्सर चरण 1 में वे एक मनमाना कॉलम नहीं चुनते हैं, बल्कि एक कॉलम जिसमें सबसे छोटी संख्या में इकाइयाँ होती हैं।

चरण 3. चयनित पंक्ति आर के लिए , हम सभी कॉलमों को मानते हैं जैसे कि एस _{आर, जे} = 1

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

चरण 4. कॉलम j के सभी गैर-अक्षीय तत्वों के लिए , उन पंक्तियों को हटा दें जिनमें वे स्थित हैं, और फिर कॉलम स्वयं j

सभी पंक्तियों में चयनित स्तंभों में नॉनज़ेरो तत्व होते हैं जो अब समाधान की इस शाखा के निर्माण में भाग नहीं ले सकते हैं। दूसरे शब्दों में, हम कोने के सभी पदों से मुक्त हो जाते हैं, जो स्थिति ए के साथ एक दूसरे को काटते हैं (सामान्य वर्ग) इसके अलावा, चूंकि हमने पहले से ही चौकों को कवर किया है 24, 33, 34 (पंक्ति ए पहले से ही स्टैक पर है), हमें उनकी देखभाल करने की आवश्यकता नहीं है। आगे, और संबंधित कॉलम भी हटा दिए गए हैं।

चरण 5. कम मैट्रिक्स के साथ चरण 1 पर जाएं।

पंक्तियों और स्तंभों को हटाने के बाद, हमें एक छोटी तालिका मिली। और ज्यामिति के दृष्टिकोण से, हमें एक छोटी आकृति को कवर करने का कार्य मिला, और शेष रेखाएं इस आंकड़े में कोनों के संभावित पदों के अनुरूप हैं।

एल्गोरिथम अंत

चरण 1 पर आगे बढ़ने के बाद, हम विशेष स्थितियों का अनुभव कर सकते हैं।

स्थिति 1. हम एक कॉलम का चयन नहीं कर सकते क्योंकि मैट्रिक्स में कोई कॉलम नहीं बचा है। इसका मतलब है कि हमने सभी उपलब्ध वर्गों को कवर किया है, इसलिए, हमने समस्या का हल ढूंढ लिया। स्टैक की सामग्री को मिला समाधान की सूची में जोड़ा जा सकता है।

स्थिति 2. हमने एक कॉलम चुना है, लेकिन इसमें एक भी इकाई नहीं है, जैसे कि अंतिम चित्र में स्तंभ 44। इसका मतलब है कि चयनित वर्ग के लिए उस कोने की एक भी स्थिति नहीं है जो इसे कवर कर सके। इसलिए, इस शाखा का कोई हल नहीं है। इस स्थिति का एक विशेष मामला यह है कि मैट्रिक्स में कोई पंक्तियाँ नहीं बची हैं। यह ध्यान देने योग्य है कि चरण 1 में सबसे छोटी इकाइयों के साथ कॉलम का चयन करना, जैसे ही यह दिखाई देता है हमें हमेशा एक खाली कॉलम मिलता है।

चूंकि हम एल्गोरिथ्म के पुनरावृत्ति के लिए जानबूझकर एक पंक्ति और एक कॉलम से छुटकारा पाते हैं, पंक्तियों और स्तंभों की संख्या कम हो जाती है, और जल्द ही या बाद में हम स्थिति 1 या स्थिति 2 पर आ जाएंगे।

डांसिंग लिंक

एल्गोरिदम को जल्दी से काम करने के लिए, आपको मैट्रिक्स से पंक्तियों और स्तंभों को जल्दी से निकालने में सक्षम होना चाहिए। यदि आप मैट्रिक्स को द्वि-आयामी सरणी के रूप में संग्रहीत करते हैं, तो यह काफी समस्याग्रस्त है। दूसरी ओर, परिणामस्वरूप मैट्रिक्स लगभग हमेशा बहुत विरल है (विशेष रूप से, पेंटामिनो समस्या के लिए मैट्रिक्स में केवल 4% इकाइयां शामिल हैं), और इसलिए इसे दो-आयामी दोहरी रूप से जुड़ी सूची के रूप में प्रतिनिधित्व करना सुविधाजनक है। ऐसा प्रतिनिधित्व हमें न्यूनतम समय में एक पंक्ति या स्तंभ के सभी गैर-अक्षीय तत्वों को प्राप्त करने की अनुमति देता है।

अंत में, आपके निपटान में ऐसी सूची होना, कॉलम और पंक्तियों को हटाने के लिए बहुत सुविधाजनक है, और उन्हें पुनर्स्थापित करने के लिए वापस शाखा में वापस आ जाता है।

//   node->next->prev = node->prev; node->prev->next = node->next; //   node->next->prev = node; node->prev->next = node; 

यह इस विचार पर है कि नॉट की डांसिंग लिंक पद्धति आधारित है। (वैसे, यदि आप एकवचन में "डांसिंग लिंक" में Google में इस विधि का नाम दर्ज करते हैं, तो चित्रों में ज़ेल्डा के मुख्य चरित्र लीजेंड के साथ कई gif होंगे।)

पहेली हल

मूल पहेली को हल करने के लिए अंतिम कोड जीथब पर देखा जा सकता है (अधिकांश कोड मैट्रिक्स की तैयारी और पहचान के लिए समाधान की जाँच के कार्य द्वारा कब्जा कर लिया गया है)। मेरे लैपटॉप पर, 5 सेकंड में कार्यक्रम को 4 अद्वितीय समाधान मिलते हैं (बारी-बारी से और परावर्तन द्वारा एक-दूसरे के लिए नहीं) और 50 सेकंड के भीतर यह सुनिश्चित करता है कि कोई अन्य नहीं है। यह महसूस करना अच्छा था कि आपका कार्यान्वयन Burr Tools समाधान से अधिक तेज़ है।


एल्गोरिथ्म के अनुकूलन में से एक क्यूमेन्ट (0, 0, 0) को कवर करने वाले पेंटामिनो के केवल 2 प्रमुख पदों को छोड़ना था, क्योंकि इसके अन्य संभावित स्थान घुमाव और प्रतिबिंब हैं। इससे खोज विकल्पों की संख्या 6 गुना कम हो गई। (वास्तव में, यह एक स्थिति को छोड़ने के लिए पर्याप्त है, लेकिन इसके लिए अतिरिक्त औचित्य की आवश्यकता है)।

इस (और अन्य पहेलियों) का हल Puzzlewillbeplayed.com पर पाया जा सकता है। और उन लोगों के लिए जिन्होंने अंत तक पढ़ा है - एल्गोरिथ्म के एक टुकड़े के दृश्य के रूप में एक बोनस। शायद यह एनीमेशन एल्गोरिदम के नाम पर विशेषण "नृत्य" को सही ठहराएगा।