एक आयताकार ग्रिड पर चक्रों की संख्या की गणना के लिए गतिशील प्रोग्रामिंग विधि

यह लेख उन पाठकों को संबोधित किया जाता है जो प्रोग्रामिंग एल्गोरिदम में लगे हुए हैं, और विशेष रूप से कठिन-से-हल समस्याओं में रुचि रखते हैं। वे हब्रालीयूड जो हैबर पर एल्गोरिदम लगाने के खिलाफ हैं, उन्हें तुरंत इस काम को पढ़ना बंद कर देना चाहिए।



लेख में मैं दिखाऊंगा कि प्रोफाइल के लिए डायनेमिक प्रोग्रामिंग विधि का उपयोग कैसे करें, ताकि n द्वारा आकार m के एक आयताकार जाली पर हैमिल्टनियन चक्रों की संख्या की गणना की जा सके। Habré पर कई लेख गतिशील प्रोग्रामिंग के विषय के लिए समर्पित हैं (उदाहरण के लिए, यह एक ), लेकिन कहीं यह विधि के अधिक जटिल अनुप्रयोग का सवाल नहीं है। इस दृष्टिकोण को स्थानांतरण मैट्रिक्स विधि भी कहा जा सकता है, जैसा कि आप चाहते हैं।



मैं आपको चेतावनी देता हूं कि लेख में लगभग 2,000 शब्द (8 ए 4 पृष्ठ) हैं, लेकिन जो चलता है वह सड़क ले जाएगा।

सारांश

1. कठिन कार्यों के बारे में थोड़ा सा
2. समस्या की परिभाषाएँ और कथन
3. स्लाइस और राज्य मशीन
4. स्थानांतरण मैट्रिक्स विधि
5. मैट्रिक्स मुक्त समाधान
6. एल्गोरिथ्म की जटिलता
7. मॉड्यूलर अंकगणित
8. चर्चा और परिणाम
9. उपयोग किए गए स्रोतों की सूची

1. कठिन कार्यों के बारे में थोड़ा सा

मुश्किल काम क्या है? यह एक ऐसा कार्य है जिसमें एक प्रभावी समाधान एल्गोरिदम नहीं है। इसके अलावा, यह आवश्यक रूप से समाधान की घातीय जटिलता के साथ एक समस्या नहीं है, जटिलता बहुपद हो सकती है, लेकिन बहुपदों की एक पर्याप्त बड़ी डिग्री के साथ (उदाहरण के लिए, k रानियों की समस्या, जो मैंने पहले ही यहां लिखी है )। इस तरह की समस्याओं और उनके वर्गीकरण के बारे में एम। गैरी, डी। जॉनसन द्वारा क्लासिक पुस्तक में पाया जा सकता है, "कम्प्यूटिंग मशीन और हार्ड-टू-सॉल्यूशन समस्याएं।"



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



मैं कठिन समस्याओं को हल करना पसंद करता हूं और समय-समय पर मैं इस विषय पर गणितज्ञों-प्रोग्रामर के लिए प्रतियोगिताएं भी आयोजित करता हूं। यह लेख आंशिक रूप से " प्री-हैमिल्टनियन साइकिल " प्रतियोगिता के लिए समर्पित है, जो 1 अक्टूबर को शुरू हुआ और 31 अक्टूबर, 2010 को समाप्त हुआ। प्रतियोगिता की शर्तों में प्रस्तावित समस्या मेरे द्वारा उसी तरह हल की गई है (मामूली बदलावों के साथ), जिसे यहां वर्णित किया जाएगा।



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

2. समस्या की परिभाषाएँ और कथन

इस काम में, हम एक आयताकार जाली P _m × P _n नामक एक ग्राफ का सामना करते हैं। एक आयताकार जाली समन्वय विमान का पूर्णांक बिंदु है, जो निकटतम निकटता के सिद्धांत द्वारा जुड़ा हुआ है। नोटेशन P _m × P _n इस तथ्य के कारण है कि एक पूर्णांक आयत दो श्रृंखलाओं का प्रत्यक्ष उत्पाद है, जिनमें से पहले में m लिंक (P _m द्वारा चिह्नित), और दूसरा n (P _n द्वारा चिह्नित) है। संख्या मीटर जाली की चौड़ाई (बाएं से दाएं की लंबाई) है, और एन इसकी लंबाई (नीचे से ऊपर तक की लंबाई) है।



एक ग्राफ में एक हैमिल्टन चक्र एक चक्र है जो प्रत्येक शिखर से एक बार गुजरता है। अंजीर में। चित्र 1 एक जाली पी ₆ × पी ₈ पर हैमिल्टनियन चक्र का एक उदाहरण दिखाता है।





चित्र 1 - 6 × 8 जाली पर हैमिल्टनियन चक्र का उदाहरण



समस्या यह है कि दिए गए m, n the 2 के लिए, जाली P _m × P _n पर हैमिल्टनियन चक्रों की संख्या ज्ञात करें। उदाहरण के लिए, निम्न आकृति 4 × 4 जाली पर सभी 6 हैमिल्टन चक्रों को दिखाती है।





चित्रा 2 - 4 × 4 जाली पर सभी 6 हैमिल्टन चक्र

3. कटौती और राज्य मशीन

ग्राफ P _m × P _n में किसी भी चक्र को "परतों" P _m × P _k (k = 0,1,2, ..., n) पर क्रमिक रूप से बनाया जा सकता है। स्पष्टता के लिए, अंजीर में। चित्र 3 एक रेखा को ग्राफ़ को दो भागों में काटता है। इसके नीचे ग्राफ पी ₆ × पी _{5 है} , जिस पर अभी भी अधूरा "चक्र" सरल जंजीरों का एक सेट है। चक्र के इस निर्मित भाग को "भूतकाल" कहा जाएगा। रेखा के ऊपर, एक अधूरा "चक्र" पूरा करने के संभावित विकल्पों में से एक को दर्शाया गया है (यह "भविष्य" है)। चक्र बंद है और कटाव रेखा को उसके विभक्ति बिंदुओं पर स्पर्श नहीं करता है। और जब से, किसी भी दिशा में चक्र के चारों ओर जा रहा है, हम प्रारंभिक बिंदु पर लौट आएंगे, कट लाइन को चक्र द्वारा एक समान संख्या में पार किया जाएगा।





चित्र 3 - चक्र की धारा



कट लाइन के साथ ही चक्र के प्रतिच्छेदन को शून्य द्वारा डिस्चार्ज किए गए नियमित ब्रैकेट अनुक्रम के रूप में दर्शाया जा सकता है। उदाहरण के लिए, अंजीर में। 3, इस तरह के अनुक्रम में फॉर्म (0000) है । इस क्रम में, ब्रैकेट खोलने और बंद करने वाले मेल की एक जोड़ी "पास्ट" के माध्यम से जाने वाली एक ही श्रृंखला के दो सिरों के अनुरूप है, और शून्य का मतलब है कि इन बिंदुओं पर चक्र के साथ कट लाइन का कोई चौराहा नहीं है। इस प्रकार, किसी भी चीरा को शून्य ब्रैकेट के साथ डिस्चार्ज किए गए सही ब्रैकेट अनुक्रम के साथ एन्क्रिप्ट किया जा सकता है। चूंकि प्रारंभिक और अंतिम खंड शून्य होना चाहिए (पूरी तरह से शून्य से मिलकर), हमें उनके बीच अंतर करना चाहिए, एक को नीचे की रेखा के साथ और दूसरे को ऊपर की रेखा के साथ।



चक्र के निर्माण की प्रक्रिया में, हमें या तो "भूतकाल" या "भविष्य" जानने की आवश्यकता नहीं है, लेकिन यह केवल इस बात की जानकारी रखने के लिए पर्याप्त है कि किसी दिए गए क्षण में क्या खंड निकला है, और इस खंड से बाकी कैसे प्राप्त किया जा सकता है। वास्तव में, वर्तमान अनुभाग से अगले तक कैसे जाना है? उदाहरण के लिए, जैसा कि अंजीर में है। 3 यह खंड (0000) से अगले अनुभाग 00 () 00 तक संक्रमण को बाहर करता है? इसे उदाहरणों में दिखाया जाएगा।





चित्र 4 - एक खंड से दूसरे खंड में संक्रमण के उदाहरण



अंजीर में। 4 एक खंड से दूसरे में संक्रमण के 3 उदाहरण दिखाता है। आर्किट लाइनों से पता चलता है कि उनके संबंधित ऊर्ध्वाधर चाप के छोर "अतीत" के माध्यम से जुड़े हुए हैं। पहला मामला सिर्फ अंजीर में संक्रमण को दर्शाता है। 3 शेष दो मामले थोड़े अधिक जटिल हैं, लेकिन वे स्पष्ट रूप से प्रदर्शित करते हैं कि क्षैतिज आर्क्स के विभिन्न संयोजनों को जोड़कर क्या नए खंड प्राप्त किए जा सकते हैं।



हालांकि, क्षैतिज चाप के सभी संयोजन एक नए खंड को जन्म नहीं दे सकते हैं। कुछ संयोजन तीन कारणों से अस्वीकार्य हो सकते हैं, चित्र 5 में संकेत दिया गया है।





चित्र 5 - अवैध संक्रमण के उदाहरण। तीन संभव मामले



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



तो, मान लें कि हमारे पास हमारे जाली के सभी संभावित वर्गों के बारे में जानकारी है और किन वर्गों से क्षैतिज चाप शामिल करके प्राप्त किया जा सकता है। यह सब जानकारी एक परिमित राज्य मशीन के रूप में दर्शाई जा सकती है, जिसके नोड्स में कटौती की जाएगी, और आर्क संक्रमण की संभावना का संकेत देंगे। अंजीर में। चित्रा 6 ऐसे परिमित राज्य मशीन का उदाहरण दिखाता है जिसका निर्माण 3 × n जाली के लिए किया गया है।





चित्रा 6 - एक 3 × एन जाली के लिए राज्य मशीन



इस सवाल का जवाब कि जाली P ₃ × P _n पर कितने चक्र हैं, ऑटोमोटिव के प्रारंभिक अवस्था से n चरणों में अंतिम तक जाने के तरीकों की संख्या होगी। यह कैसे करना है? मैं दो तरीके जानता हूं: बुरा और बेहतर। मैं बुरे से शुरू करूंगा।

4. स्थानांतरण मैट्रिक्स विधि

इस समस्या को हल करने के एक तरीके को ट्रांसफर मैट्रिक्स विधि कहा जाता है, जिसमें निम्नलिखित शामिल हैं। हम किसी भी तरह से 1 से लेकर एन तक सभी संभावित कटौती करते हैं, लेकिन इतना है कि प्रारंभिक स्थिति नंबर 1 है और अंतिम स्थिति नंबर एन है। आइए हम एक मैट्रिक्स टी का निर्माण करते हैं जिसमें टी _आईजे नंबर से अनुभाग जे से एक अनुभाग प्राप्त करने के तरीकों की संख्या के बराबर होगा। । जाली P _m × P _{n के} लिए समस्या का हल संख्या (T ⁿ ) _1, ^{N है} _।

उदाहरण के लिए, जाली पी ₃ × पी _{एन के लिए,} हमने पहले से ही एक ऑटोमेटन (छवि 6) का निर्माण किया है, इसलिए हम हस्तांतरण मैट्रिक्स को लिख सकते हैं।





चित्रा 7 - स्थानांतरण मैट्रिक्स, या एक परिमित राज्य मशीन अंजीर के आसन्न मैट्रिक्स। 6 और इसकी छठी डिग्री



अंजीर में। 7 जाली P ₃ × P _n पर हैमिल्टनियन चक्रों के लिए परिवहन मैट्रिक्स T दिखाता है। समस्या का समाधान संख्या (T ⁿ ) _{15 है} । उदाहरण के लिए, (T ⁶ ) ₁₅ = 4, ऐसी हैमिल्टनियन चक्रों की संख्या जाली P ₃ × P _{6 है} ।



हालांकि, व्यवहार में, समस्या को हल करने का यह तरीका अधिकतम, एम = 12 के लिए लागू होता है, जब जाली पर हैमिल्टनियन चक्र के लिए स्थानांतरण मैट्रिक्स का आकार 3774 × 3774 होता है (चर्चा अनुभाग में तालिका 1 देखें) और एक व्यक्तिगत कंप्यूटर की रैम में फिट बैठता है। मैट्रिक्स में ही लंबी संख्याएं संग्रहीत की जाती हैं, क्योंकि, उदाहरण के लिए, जाली P ₁₂ × P _{20 के उत्तर} में 33 अंक होते हैं, और जाली P ₁₂ × P ₁₀₀ अंकों के लिए अंकों की संख्या 174 तक पहुंचती है।



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

5. मैट्रिक्स का उपयोग किए बिना समाधान

समाधान की यह विधि, जैसा कि यह अजीब नहीं है, को ट्रांसफर मैट्रिक्स विधि भी कहा जाता है, लेकिन मैट्रिक्स स्पष्ट रूप से इसमें प्रकट नहीं होता है, इसलिए, इस पद्धति को गतिशील प्रोग्रामिंग [एक फाइनेंस स्टेट मशीन का उपयोग करके] रूसी भाषा के साहित्य में कॉल करना प्रथा है।



विधि का अर्थ k चरणों में राज्य मशीन के प्रत्येक शीर्ष पर पहुंचने के तरीकों की संख्या को संग्रहीत करना है। चरण k = 0 पर, यह संख्या प्रारंभ को छोड़कर सभी सिरों पर 0 है। परिभाषा के अनुसार, चरण k = 0 पर आरंभिक शीर्ष पर पहुंचने के तरीकों की संख्या 1. मान ली गई है। P को चरण k पर शीर्ष पर i में कुछ विधियाँ होने दें; फिर, चरण k + 1 पर जाएँ, हम संख्या P को सभी शीर्षों की विधियों की संख्या में जोड़ते हैं। j कि मैं से पहुँचा जा सकता है। लेकिन इसके लिए आपको यह जानने की जरूरत है कि आपको कौन से वर्टिकल से मैं मिल सकता है, यानी फिर से मैट्रिक्स स्टोर करें! वास्तव में, यह आवश्यक नहीं है: मैं शीर्ष पर जा रहा हूं, और यह जानने के लिए कि यह किस अनुभाग को निर्दिष्ट करता है, हम ऐसे सभी अनुभागों का पुनर्निर्माण करते हैं जो इससे बाहर आ सकते हैं



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



चरण k पर, हमें अगला भाग i कतार से मिलता है, और P की संख्या इसमें हो सकती है। हम i से प्राप्त सभी संभावित कटों के सेट J का निर्माण करते हैं। जम्मू से प्रत्येक जम्मू के लिए, जांचें कि क्या यह हैश तालिका में है। यदि नहीं, तो विधियों की संख्या के साथ तालिका में j जोड़ें। यदि हाँ, तो तालिका से हम उन विधियों की संख्या लेते हैं जिन्हें j में प्रविष्ट किया जा सकता है और संख्या P + Q को उसके स्थान पर लिख सकते हैं। अपवाद तब होता है जब j शून्य कटौती के बराबर होता है, इसका मतलब है कि हम अंतिम स्थिति में हैं और उत्तर में P को संख्या जोड़ना चाहिए, लेकिन शून्य कटौती को हैश में नहीं जोड़ें।



चरण k के अंत में, कतार खाली है, इसलिए हम हैश तालिका से डेटा को कतार में ले जाते हैं, हैश को साफ़ करते हैं और चरण k + 1 पर जाते हैं।



मैं खुले पते और डबल हैशिंग के साथ एक हैश का उपयोग करता हूं। टकराव की संख्या 0.6 प्रति कॉल है। यानी 60% मामलों में, तालिका के अनुसार एक कदम उठाया जाता है, और अन्य मामलों में यह तुरंत दूर हो जाता है। मुझे ऐसे कार्य के लिए यह एक अच्छा हैश लगता है।

6. एल्गोरिथ्म की जटिलता

सबसे पहले, मैं जटिलता की ऊपरी सीमा को इंगित करूंगा, और फिर मैं दिखाऊंगा कि वास्तव में व्यवहार में क्या होता है।



शून्य और लंबाई मीटर के द्वारा डिस्चार्ज किए गए सभी नियमित ब्रैकेट अनुक्रमों का सेट वर्णमाला { 0 , ( , )) से अधिक लंबाई के Motskin शब्द हैं जो एक संदर्भ-मुक्त व्याकरण द्वारा उत्पन्न किए गए हैं।



जेड → वाई | Y ( Z ) Z,

Y → ε | 0 वाई,



जहां empty खाली शब्द है। ऐसे शब्दों की संख्या की गणना जुबान से की जा सकती है:







इस सूत्र में, k कोष्ठक के युग्मों की संख्या है। योग चिह्न के तहत पहली अभिव्यक्ति (अंश और बहुत पहले द्विपद गुणांक) कैटलन संख्या है , जो सही ब्रैकेट अनुक्रमों की संख्या को दर्शाता है, और दूसरा द्विपद गुणांक 2 पदों कोष्ठक को m पदों पर रखने के तरीकों की संख्या है (शेष पदों को शून्य से भरना)।



इस प्रकार, जाली पर हैमिल्टन के चक्रों के लिए सभी संभव कटौती की संख्या, कम से कम, मोत्स्किन शब्दों की संख्या से अधिक नहीं है, और मोत्स्किन शब्द लगभग 3 ^मीटर की गति से बढ़ते हैं। वास्तव में, ऐसे बहुत कम खंड हैं, क्योंकि कुछ अस्वीकार्य हो सकते हैं। उदाहरण के लिए, इस तरह के कटौती (0) 000 या ((0) 0 के रूप में चौड़ाई 6 के एक जाली के लिए अस्वीकार्य होगा, क्योंकि हैमिल्टन चक्र का निर्माण करते समय उन्हें प्राप्त नहीं किया जा सकता है। चर्चा अनुभाग में, एक तालिका दिखाई जाएगी। 1, जो कुछ मीटर के लिए कटौती की कुल संख्या को इंगित करता है। वास्तव में, यह पता चला है कि केवल एक तिहाई मोत्ज़किन के शब्द अनुमेय हैं, और समरूपता को ध्यान में रखते हुए, उनमें से केवल पांचवां हिस्सा संग्रहीत करने के लिए पर्याप्त है।



मैं समझा दूंगा। कुछ खंड पैलिंड्रोम हैं और सममित प्रतिबिंब के तहत खुद के साथ मेल खाते हैं, लेकिन जो एक दूसरे के सममित हैं उन्हें एक खंड के रूप में संग्रहीत किया जा सकता है। उदाहरण के लिए, कट (()) और () () () को एक ही माना जा सकता है। इसे ध्यान में रखते हुए, यह पता चला है कि कार्यक्रम में औसतन केवल पांचवीं मोत्ज़किन के शब्दों को संग्रहीत किया जाना चाहिए।



प्रत्येक अनुभाग के लिए, हमें क्षैतिज आर्क्स सेट करने के लिए 2 ^{मीटर -1 के} माध्यम से जाना चाहिए। और यह सब एक साथ हम n बार करना चाहिए।



कुल, एल्गोरिथ्म में जटिलता ओ (6 ^मीटर · एम ^-1/2 · एन) है। लेकिन वास्तव में, इस तथ्य के कारण कि कई खंड अस्वीकार्य हैं, व्यवहार में एल्गोरिथ्म की जटिलता ओ (5 ^मीटर · एन) हो जाती है। यह एल्गोरिथ्म के मेरे अवलोकन के दौरान हुआ।



उपयोग की गई स्मृति के लिए, संसाधनों का मुख्य भाग कतार और हैश तालिका द्वारा कब्जा कर लिया गया है। M bit32 के लिए प्रत्येक खंड को 64-बिट पूर्णांक में संग्रहीत किया जा सकता है, क्योंकि 2 बिट्स को कोष्ठक और संख्या 0. प्लस को स्टोर करने के लिए आवश्यक है, एक लंबा अंकगणित जो सभी संसाधनों को स्थायी रूप से खाता है। लेकिन एक चाल है जो आपको लंबी गणित को छोड़कर गणना को धीमा करने की अनुमति देती है।

7. मॉड्यूलर अंकगणित

आइए उत्तर माडुलो विभिन्न अभाज्य संख्याओं की गणना करें: 2 ³¹ -1 = 2147483647, 2147483629, 2147483587, ... ऐसा करने के लिए, आपको प्रोग्राम को कई बार चलाने की आवश्यकता है जितने अलग-अलग मॉड्यूल हम चुनते हैं (हालांकि, आप 2-3 मॉड्यूल एक ही बार में पढ़ सकते हैं, जब तक यह टूट जाता है। स्मृति में)। चीनी शेष प्रमेय के अनुसार , उपयोग किए गए सभी प्राइमों के उत्पाद तक उत्तर को बहाल किया जा सकता है। यदि सभी primes का उत्पाद समस्या के उत्तर से अधिक है, तो उत्तर विशिष्ट रूप से पुनर्स्थापित किया जाता है। मॉड्यूल की सही संख्या का चयन कैसे करें?



उदाहरण के लिए, चलो दो मॉड्यूल के लिए n द्वारा आकार 16 के एक जाली पर चक्रों की संख्या की गणना करते हैं। एन = 1,2, ..., 16। तब हमें उत्तर मिलते हैं



[0, 1, 128, 405688, 24980352, 776813457, 729683652, 1087605227, 2000673777, 456710131, 1550214608, 568568609, 2047094091, 1175631455, 380271385, 153668154949] (21)।



[0, 1, 128, 405688, 24980352, 776813727, 729709644, 1107434405, 301217473, 1373982040, 103268356, 218888622, 1185113726, 2085126539, 1315887233, 200804641010]।



चीनी शेष प्रमेय के अनुसार, हमारे पास है:



[0, 1, 128, 405,688, 24,980,352, +३२९८९०६८१६२, 3101696069920, 2365714170297014, 309656520296472068, 2415277789552788286, 3926649012293853406, 726889843182193849, 153366515247378747, 1645735649663585962, 3698490188721496226, 1337259901989820598] (आधुनिक · 2147483647 +२१४७४८३६२९)।



अगर हमारे पास 2 मॉड्यूल हैं तो कैसे जांचें? इस समस्या में, यह स्पष्ट है कि संख्या में तेजी से वृद्धि होनी चाहिए, इसलिए उनके लघुगणकों को रैखिक रूप से बढ़ना चाहिए। लघुगणक लें (जैसे, प्राकृतिक):



[-INF, 0, 4.852, 12.91, 17.03, 24.22, 28.76, 35.40, 40.27, 42.33, 42.81, 41.13, 39.57, 41.94, 42.75, 41.74]।



हमारे दो मॉड्यूल के उत्पाद का लघुगणक 42.98 है। हम देखते हैं कि एक ही राशि के बारे में संख्याओं के बीच का अंतर नीरस रूप से बढ़ता है, और, n = 9 से शुरू होता है, किसी कारण से यह बढ़ना बंद हो जाता है। इसके अलावा, इस स्थान पर एक सीमा समाप्त हो गई थी, जिसके आगे संख्याएं नहीं रह सकती हैं। इसका मतलब है कि दो मॉड्यूल पर्याप्त नहीं थे। चलो 4 मॉड्यूल लेते हैं और उत्तर को पुनर्स्थापित करते हैं:



[0, 1, 128, 405,688, 24,980,352, +३२९८९०६८१६२, 3101696069920, 2365714170297014, 309656520296472068, 168435972906750526954, 27738606105535271640888, 12142048779807437697982030, 2344813362310160031818110686, 888511465584607682074513271223, 191678405883294971709423926242394, 65882516522625836326159786165530572] (आधुनिक 2147483647 +२१४७४८३६२९ · · · +२१४७४८३५८७ +२१४७४८३५७९)।



लघुगणक समान हैं:



[-आईएफएन।, ०, ४. ,५२, १२.९ १, १ 24.०३, २४. ,२, २6. ,६, ३५.४०, ४०.२40, ४६.५,, ५१.६,, ५ 57. ,६, ६३.०२, ६ 68.९ ६, 3४.३३, .1०.१7]।



संख्या में सख्ती से वृद्धि होती है, उसी राशि के बारे में बढ़ रही है। 4 चयनित मॉड्यूल के उत्पाद का लघुगणक 85.95 है, जो अनुक्रम में अंतिम संख्या से काफी बड़ा है। इसका मतलब है कि उत्तर सही है। आप Google में "65882516522625836326159786165530572" अनुरोध टाइप करके इसे सत्यापित कर सकते हैं।

8. चर्चा और परिणाम

इस एल्गोरिथ्म के साथ, मैं 22 × 100 जाली पर चक्रों की संख्या की गणना करने में सक्षम था। क्लस्टर के 32 कोर पर एक मॉड्यूल के लिए गणना लगभग 30 घंटे तक चली। कुल मिलाकर, लगभग 50 मॉड्यूल की आवश्यकता थी। प्रति कोर 1 जीबी से कम मेमोरी आवश्यक है। कंप्यूटिंग की प्रक्रिया में, मैंने समाधान की मात्रात्मक विशेषताओं के बारे में कुछ जानकारी एकत्र की। तालिका में। 1 यह जानकारी है।

मीटर	कटौती की वास्तविक संख्या	मोटज़किन की शब्द गणना
3	3	4
4	6	9
5	12	21
6	23	51
7	62	127
8	109	323
9	365	835
10	607	2188
11	2355	5798
12	3774	15,511
13	16020	41,835
14	25,188	113,634
15	113,198	310,572
16	176,061	853,467
17	821,923	2356779
18	1270562	6536382
19	6097041	18199284
10	9387784	50852019
21	46013564	142547559
22	70652188	400763223

तालिका 1 - स्मृति में भंडारण के लिए आवश्यक मोत्स्किन संख्या और कटौती की वास्तविक संख्या की तुलना



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



यदि आप एक वर्ग जाली P _2n × P _2n पर हैमिल्टनियन चक्रों की संख्या देखना चाहते हैं, तो इस क्रम का एक लिंक स्रोतों की सूची में है।

9. उपयोग किए गए स्रोतों की सूची

1. एम। गैरी, डी। जॉनसन। कंप्यूटर और मुश्किल काम।
2. A003763 - अंकों के 2n X 2n वर्ग ग्रिड पर हैमिल्टनियन चक्रों की संख्या।
3. चीनी शेष प्रमेय ।
4. कैटलन संख्या , सूत्र और स्पर्शोन्मुख दवाओं की व्युत्पत्ति।

आपका ध्यान देने के लिए धन्यवाद।