n- क्वींस कम्प्लीटेशन प्रॉब्लम - लीनियर सॉल्यूशन एल्गोरिदम

EricGrig

प्रस्तावना

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

1. "समाधान n- क्वींस कम्प्लीशन प्रॉब्लम के लिए रेखीय एल्गोरिथ्म" लेख को (arXiv.org) 2020 के पहले दिन की शुरुआत में प्रकाशित किया गया था। प्रारंभ में, लेख रूसी में लिखा गया था, इसलिए मूल प्रस्तुति यहां प्रस्तुत की गई है, और अनुवाद है।
2. यह कार्य, और कई अन्य एनपी-कम्पलीट सेटों में से कुछ (बूलियन फॉर्मूलों को संतुष्ट करने का कार्य (3-सैट), अलग-अलग समय में अधिकतम क्लिक, या किसी दिए गए आकार का एक समूह ...) का कार्य मेरे हित में था। मैं विभिन्न कम्प्यूटेशनल प्रयोगों के आधार पर एक एल्गोरिथम समाधान की तलाश कर रहा था, लेकिन कोई ठोस सफलता नहीं थी। यह एक व्यक्ति की तरह सीखने की कोशिश कर रहा था कि एक हाथ पर क्षैतिज पट्टी पर कैसे फिट हो। कोई परिणाम नहीं है, लेकिन हर बार एक उम्मीद है कि सब कुछ जल्द ही काम करेगा। पिछली बार मैंने फैसला किया था कि मुझे एन-क्वींस कम्प्लीशन टास्क पर (परिवार के सदस्यों में से एक के रूप में) रहना चाहिए और कुछ करने की कोशिश करनी चाहिए। यह अद्भुत ओडेसा मजाक याद करने के लिए उपयुक्त है: "एक भीड़ भरी बस में जो शाम को ऊबड़-खाबड़ सड़क पर लौटती है, एक महिला की आवाज सुनाई देती है - यार, अगर तुम पूरी तरह से मुझ पर बिछे हुए हो, तो कम से कम कुछ करो।"
3. अध्ययन काफी लंबे समय तक चला - लगभग डेढ़ साल। एक ओर, यह इस तथ्य के कारण है कि अनुसंधान प्रक्रिया में अन्य कार्यों पर विचार किया गया था, और दूसरी तरफ, रास्ते में कठिन सवाल थे, जिसके बिना हम आगे नहीं बढ़ सकते थे। मैं उनमें से कुछ को सूचीबद्ध करूंगा:
   
   
   • निर्णय मैट्रिक्स में n पंक्तियाँ हैं, अगर इस तरह की पसंद के लिए संभावनाओं की संख्या n है, तो अनुक्रम को किस अनुक्रम में चुना जाना चाहिए!
   • जब एक पंक्ति बनाई जाती है, तो इस पंक्ति में शेष बचे पदों में से किसे चुना जाना चाहिए, क्योंकि इस तरह के चयन के लिए संभावनाओं की संख्या इतनी बड़ी है कि इसे अनंत का "करीबी रिश्तेदार" माना जा सकता है (उदाहरण के लिए, आकार की शतरंज के लिए सभी पंक्तियों में एक मुक्त स्थिति का चयन करने के संभावित तरीकों की संख्या 100 x 100 लगभग 10 ^{124 है} )
   • साथ में, ये दो संकेतक एक राज्य स्थान (एक विकल्प स्थान) बनाते हैं। ऐसा लगता है कि बहुत बड़े अवसर हैं, आप जो चाहें चुन सकते हैं। लेकिन हर कदम पर प्रत्येक विशिष्ट विकल्प के पीछे, एक और समस्या है - सभी बाद के चरणों में पसंद की सीमा। इसके अलावा, समस्या को हल करने के अंतिम चरण में यह विशेष रूप से संवेदनशील है। हम कह सकते हैं कि निर्णय मैट्रिक्स "प्रतिशोधी" है। सभी "अचेतन गलतियाँ" जो आप पिछले चरणों में एक विकल्प बनाते समय करते हैं, "संचित" हैं, और निर्णय के अंत में यह इस तथ्य में प्रकट होता है कि उन पंक्तियों में जहां आपको रानी को रखना चाहिए, कोई खाली स्थान नहीं हैं और खोज शाखा एक ठहराव के लिए आती है। । यहाँ, जैसा कि ज़्वान्त्स्की के साथ: "एक गलत कदम, और आप गर्भवती हैं।"
   • जब किसी समाधान के लिए खोज की शाखा एक ठहराव की ओर आती है, तो हमारे पास पिछले पदों (बैक ट्रैकिंग) में से कुछ पर वापस जाने का अवसर होता है, ताकि इस स्थिति से हम फिर से समाधान के लिए खोज की शाखा बनाने लगें। यह गैर-नियतात्मक समस्याओं का एक प्राकृतिक "संपत्ति" है। सवाल यह है कि पिछले स्तरों में से कौन सा वापस आ जाना चाहिए। यह वही खुली समस्या है, जो पंक्ति अनुक्रमणिका को चुनने या इस पंक्ति में मुक्त स्थिति चुनने के प्रश्न के रूप में है।
   • अंत में, एल्गोरिथ्म की गति से संबंधित एक समस्या पर ध्यान दिया जाना चाहिए। तेजी से चल रहे एल्गोरिदम बनाने के लिए कोई लक्ष्य नहीं था तो यह दुखद होगा। मॉडलिंग की प्रक्रिया में, एक एल्गोरिथ्म विकसित करना संभव नहीं था जो समस्या समाधान के सभी क्षेत्रों में जल्दी और कुशलता से काम करेगा। मुझे तीन एल्गोरिदम विकसित करने थे। वे एक बैटन की तरह एक दूसरे को परिणाम प्रसारित करते हैं। उनमें से एक बहुत जल्दी काम करता है, लेकिन अशिष्ट रूप से, दूसरा - इसके विपरीत, धीरे-धीरे लेकिन कुशलता से काम करता है। उनमें से प्रत्येक "अपनी जिम्मेदारी के क्षेत्र" में काम करता है।
4. प्रारंभ में, अध्ययन का उद्देश्य केवल कम से कम कुछ समाधान खोजना था। पहला समाधान विकसित होने से पहले मुझे बहुत कुछ पता लगाना था। इसमें चार महीने से ज्यादा का समय लगा। वहां रुकना संभव था, लक्ष्य हासिल किया गया - ठीक है, ठीक है। लेकिन यह मुझे प्रतीत हुआ कि इस समस्या के एक एल्गोरिथम समाधान की सभी संभावनाएं समाप्त नहीं हुई थीं। स्वाभाविक रूप से, विकसित एल्गोरिथम में सुधार करने की इच्छा थी ताकि एल्गोरिथ्म की समय जटिलता रैखिक-ओ (एन) हो। जब इस तरह के एक रैखिक समाधान पाया गया था, तो "एक और इच्छा" थी - समाधान खोज की एक शाखा बनाते समय बैक ट्रैकिंग (बीटी) प्रक्रिया को लागू करने के मामलों की संख्या को कम करने के लिए। यह सशर्त रूप से निर्धारित (जहाँ तक संभव हो) निर्धारित करने के लिए कार्य को हस्तांतरित करने के लिए एक "अशिष्ट" इच्छा थी। बहुत समय लग गया, लेकिन लक्ष्य प्राप्त किया गया था, उदाहरण के लिए, एक शतरंज के n = (320, ..., 22500) के आकार के मूल्यों के अंतराल में, बीटी प्रक्रिया का उपयोग नहीं किए जाने वाले मामलों की संख्या 50% से अधिक है। यह पता चला है कि 50% मामलों में जब प्रोग्राम लॉन्च किया जाता है, तो एल्गोरिथ्म "उद्देश्यपूर्ण" एक समाधान बनाता है, कभी भी "ठोकर" नहीं। (सुनहरी के बारे में परी कथा को याद करते हुए, मैं इन दो इच्छाओं पर रुक गया ...)
5. शोध के दौरान जिन प्रकाशनों से मैं परिचित हुआ, उनकी तुलना करते हुए, मैं इस निष्कर्ष पर पहुंचा कि इस तरह की समस्या और इस तरह की अन्य समस्याओं को एक कठोर गणितीय दृष्टिकोण के आधार पर हल नहीं किया जा सकता है, अर्थात्, केवल परिभाषाओं के आधार पर, नींबू का विवरण और प्रमेयों का प्रमाण। लेख में इसके बारे में एक "दार्शनिक टिप्पणी" है। मुझे यकीन है कि कई एनपी-कम्पलीट से कई समस्याओं को केवल कंप्यूटर मॉडलिंग के उपयोग के साथ एल्गोरिथम गणित के आधार पर हल किया जा सकता है। इस तरह के निष्कर्ष का मतलब गणित को सीमित करना नहीं है, इसके विपरीत, इसका अर्थ एल्गोरिथम गणित के तरीकों के विकास के माध्यम से गणित की क्षमताओं का विस्तार करना है। समस्याओं के प्रत्येक परिवार के लिए आपको अपने स्वयं के पर्याप्त गणितीय दृष्टिकोण का उपयोग करने की आवश्यकता है। (एनपी-पूरा परिवार से एल्गोरिथम गणित और कंप्यूटर मॉडलिंग के तरीकों को लागू किए बिना एक समस्या को हल करने के लिए एक स्नातकोत्तर छात्र को क्यों असाइन करें, अगर यह ज्ञात है कि वास्तव में इस तरह के एक उपक्रम से कुछ भी नहीं होगा)।
6. किसी भी एल्गोरिथ्म (प्रोग्राम) में एक साधारण संपत्ति है - या तो यह काम करता है या नहीं! मैं हमारे हाब्रो-समुदाय के उन सदस्यों से अपील करना चाहता हूं जिनके पास पहुँच क्षेत्र में मतलाब वाला एक कंप्यूटर है। मैं आपको एन-क्वींस कंप्लीशन प्रॉब्लम को हल करने के लिए विचार किए गए एल्गोरिदम के संचालन का परीक्षण करने के लिए कहना चाहता हूं। इसमें केवल 5-10 मिनट का समय लगेगा। एल्गोरिथ्म का परीक्षण करने के लिए, आपको कुछ सरल चरणों का पालन करने की आवश्यकता है:
   
   
   • K रानियों से एक यादृच्छिक रचना उत्पन्न करें और इस रचना की शुद्धता की जाँच करें।
   • प्रस्तावित निर्णय एल्गोरिथ्म के आधार पर, इस रचना को पूर्ण समाधान के लिए पूरा करें। या प्रोग्राम को यह तय करना होगा कि इस रचना का कोई हल नहीं है।
   • कॉन्फ़िगरेशन के परिणामस्वरूप प्राप्त समाधान की शुद्धता की जांच करें।
   
   
   आपको इस तरह के परीक्षण के लिए कोई कोड लिखने की आवश्यकता नहीं है। मुख्य कार्यक्रम के अलावा, मैंने मतलाब भाषा में दो और कार्यक्रम तैयार किए:
   
   1. Generarion_k_Queens_Composition - आकार n की एक मनमाना बिसात के लिए k के आकार की एक यादृच्छिक रचना की पीढ़ी
   
   2. कंप्लीटेशन_के_क्यूएन्स_ कॉमपोजिशन - एक पूर्ण निर्णय तक एक मनमानी रचना को पूरा करना, या यह निर्णय लेना कि इस रचना का कोई समाधान ( मुख्य कार्यक्रम ) नहीं है।
   
   3. Validation_n_Queens_Solution.m - n- क्वीन्स समस्या के समाधान की शुद्धता, या k रानियों की रचना की शुद्धता की जाँच करना।
   
   वे बहुत तेजी से काम करते हैं। उदाहरण के लिए, 1000 x 1000 कोशिकाओं के आकार के साथ एक शतरंज के लिए, एक मनमाना रचना (0.0015 सेकेंड) उत्पन्न करने के लिए कुल समय लगता है, इस रचना को पूरा करें (0.0622 s।), और प्राप्त समाधान की शुद्धता की पुष्टि करें (0.0003 s)। 0.1 सेकंड से अधिक नहीं है। (डेटा डाउनलोड करने, या परिणाम सहेजने में लगने वाले समय को छोड़कर)
   
   मुझे ईमेल करें (ericgrig@gmail.com), यदि आपके पास किसी मित्र की मदद करने का अवसर है, तो मैं तुरंत आपको ये तीन कार्यक्रम भेजूंगा। मैं अपने सभी सहयोगियों का आभारी रहूंगा जो कि एल्गोरिथ्म का निष्पक्ष रूप से परीक्षण कर सकते हैं और चर्चा में अपनी राय व्यक्त कर सकते हैं।
7. मैंने कार्यक्रम का स्रोत कोड विस्तृत टिप्पणियों के साथ तैयार किया, जो मुझे आशा है, जल्द ही हेबे पर प्रकाशित होगा। मुझे लगता है कि जो लोग एनपी-पूर्ण परिवार से जटिल समस्याओं को हल करने में रुचि रखते हैं, वे अपने लिए कुछ दिलचस्प पाएंगे।
8. मैं फिर से हबर समुदाय के सदस्यों से अपील करना चाहूंगा, लेकिन एक अलग कारण से। यहां, मार्सिले (फ्रांस) में, फ्रांस फोल्ड ग्रुप टीम का गठन चल रहा है, जिसका उद्देश्य उच्च आणविक भार यौगिकों के भौतिक रासायनिक गुणों की भविष्यवाणी के लिए एल्गोरिदम का अनुसंधान और विकास करना है। मुझे लगता है कि यह कहने लायक नहीं है कि यह एक लंबा इतिहास है, बल्कि यह एक कठिन काम है, और विभिन्न देशों की गंभीर टीमें इस समस्या पर काम कर रही हैं, जिसमें डीप माइंड से खासाबी टीम भी शामिल है (आप Habré (habr__Folding) पर लेख देख सकते हैं ) । लक्ष्य एक मजबूत टीम बनाना है जो जटिल समस्याओं को हल करने से डरता नहीं है। संयुक्त कार्य के संगठन का रूप वितरित किया जाता है। प्रत्येक टीम का सदस्य अपने शहर में रहता है और अपने मुख्य कार्य से अपने खाली समय में परियोजना पर काम करता है। हमें प्रोग्रामर और शोधकर्ताओं (चिकित्सकों, रसायनज्ञ, गणितज्ञ, जीवविज्ञानी) की आवश्यकता है। ), आदि। osto "लापरवाह" प्रोग्रामर- (चुकता)। मुझे लिखें अगर आपको यह दिलचस्प लगता है, तो उपरोक्त मेरा ई-मेल है। और अधिक विस्तार से मैं प्रतिक्रिया पत्र में बता सकता हूं।

लेख की प्रस्तावना लेख के रूप में लंबे समय के रूप में ही निकला। हैबे पर पारिवारिक प्रस्तुति प्रारूप मुझे अपने विचारों को और अधिक स्वतंत्र रूप से व्यक्त करने की अनुमति देता है, लेकिन आकार से देखते हुए, मैंने काफी स्वतंत्र रूप से इसका लाभ उठाया। मैं संक्षेप में लिखना चाहता था, लेकिन "यह हमेशा की तरह निकला।"

पीएस मुझे लगा कि हैबर समुदाय के सदस्यों को यह जानने में दिलचस्पी होगी कि अध्ययन के परिणामों को प्रकाशित करने की कोशिश करते समय मुझे किन कठिनाइयों का सामना करना पड़ा। जब लेख तैयार किया गया था, तो मैंने जर्नल ऑफ आर्टिफिशियल इंटेलिजेंस रिसर्च (JAIR) की आवश्यकताओं के अनुसार इसे .tex प्रारूप में सुधार दिया और इसे वहां भेजा। एक समान विषय पर प्रकाशन हुआ करते थे। विशेष रूप से नोट सी। जेंट, आई। पी। का लेख है । जेफरसन और पी। नाइटिंगेल (2017) (एन-क्वीन्स पूरा होने की जटिलता) , जिसमें लेखकों ने साबित किया कि प्रश्न में समस्या एनपी-पूर्ण सेट के अंतर्गत आती है और इस समस्या को हल करने की कोशिश में आने वाली कठिनाइयों के बारे में बात की। निष्कर्ष में, लेखक लिखते हैं: "जो कोई भी शतरंज के नियमों को समझता है, उसके लिए n- क्वींस कंप्लीशन सभी की सबसे प्राकृतिक एनपी-कम्प्लीट समस्याओं में से एक हो सकता है" ( जो कोई भी शतरंज के नियमों को समझता है, उसके लिए n- क्वींस कंप्लीशन टास्क एक हो सकता है सबसे प्राकृतिक एनपी-पूर्ण कार्य )।

10 दिनों के बाद, मुझे JAIR से एक खंडन के साथ इनकार मिला: "लेख पत्रिका के प्रारूप के अनुरूप नहीं है", अर्थात्। विचार के लिए लेख भी नहीं लिया। मुझे इस तरह के जवाब की उम्मीद नहीं थी। मैंने सोचा कि अगर कोई पत्रिका उन लेखों को प्रकाशित करती है जिनमें लेखक यह निष्कर्ष निकालता है कि किसी समस्या को हल करना बहुत मुश्किल है और कोई ठोस समाधान प्रदान नहीं करता है, तो एक प्रभावी समाधान एल्गोरिदम प्रदान करने वाला लेख निश्चित रूप से विचार के लिए स्वीकार किया जाएगा। हालाँकि, इस मामले पर संपादकों की अपनी राय थी। (मेरा मानना ​​है कि सक्षम विशेषज्ञ वहां काम करते हैं, और सबसे अधिक संभावना है कि वे "दिलेर" लेख शीर्षक से पूछताछ की गई थी और सब कुछ वहां बताया गया है। हमने सोचा, "सबसे अधिक संभावना है कि किसी तरह की गलती हो और धीरे-धीरे मुझे भेजा, प्रारूप का जिक्र किया।" ")।

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

अगली पत्रिका, जो सूचना तक मुफ्त पहुंच के सिद्धांत को स्वीकार करती है, कम्प्यूटेशनल गणित का SMAI जर्नल था। उन्होंने भी उसी शब्दों के साथ इनकार कर दिया, हालांकि बहुत तेजी से - दो दिनों में।

फिर एक पत्रिका को चुना गया: असतत गणित और सैद्धांतिक कंप्यूटर विज्ञान । यहाँ आवश्यकताएँ सरल हैं, पहले आपको आर्टिकल को arXiv.org में प्रकाशित करना होगा, और उसके बाद ही विचार के लिए लेख को पंजीकृत करना होगा। ठीक है, हम नियमों का पालन करेंगे - मैंने arXiv.org में एक लेख प्रस्तुत किया। उन्होंने मुझे लिखा कि वे 8 घंटे में लेख प्रकाशित करेंगे। हालांकि, 8 घंटे के बाद ऐसा नहीं हुआ, 8 दिनों के बाद नहीं। यह लेख मेंटर्स द्वारा "आयोजित" किया गया था, और केवल 9 दिनों के बाद ही इसे प्रकाशित किया गया था। लेख के रूप और सार में कोई शिकायत नहीं थी। मुझे लगता है, जैसा कि जेएआईआर के मामले में, संरक्षक को "ऐसा करने और इसके बारे में लिखने" की संभावना के बारे में संदेह था। कुछ समय बाद, तकनीकी त्रुटियों को ठीक करने के बाद, लेख को अद्यतन किया गया और इसके अंतिम रूप को नए साल की रात को जारी किया गया।

मुझे इस पर विस्तार से बताना होगा कि शोध परिणामों के प्रकाशन के चरण में ऐसी समस्याएं हो सकती हैं जिन्हें तार्किक रूप से नहीं समझाया जा सकता है।

निम्नलिखित एक लेख है जिसका अंग्रेजी में अनुवाद (arXiv.org) में प्रकाशित हुआ था।

1. परिचय

एन-क्वींस समस्या को तैयार करने के विभिन्न विकल्पों में से, प्रश्न में एन-क्वींस कम्प्लीशन कार्य की जटिलता की वजह से एक विशेष स्थान है। अपने काम में (Gent at all (2017)) से पता चला कि n- क्वींस कंप्लीशन की समस्या एनपी-कम्प्लीट ( एन-क्वीन्स कंप्लीशन दोनों एनपी-कम्प्लीट और # पी-कम्प्लीट दोनों ) सेट से संबंधित है। यह माना जाता है कि इस समस्या का समाधान हमारे लिए एनपी-पूर्ण के सेट से कुछ अन्य समस्याओं को हल करने का रास्ता खोल सकता है।

समस्या निम्नानुसार तैयार की गई है। K रानियों की एक रचना है, जो लगातार आकार के nxn की एक बिसात पर वितरित की जाती हैं। यह साबित करना आवश्यक है कि इस रचना को एक पूर्ण समाधान के लिए पूरा किया जा सकता है, और कम से कम एक समाधान दे सकता है, या यह साबित करने के लिए कि ऐसा समाधान मौजूद नहीं है। यहाँ, संगति से हमारा तात्पर्य है कि k रानियों की एक रचना, जिसके लिए समस्या की तीन स्थितियाँ पूरी होती हैं: प्रत्येक पंक्ति में, प्रत्येक स्तंभ पर, और बाएँ और दाएँ विकर्णों पर, जहाँ रानी स्थित है, उस कक्ष से होकर गुजरती है जहाँ एक से अधिक रानी स्थित नहीं हैं। इस रूप में समस्या सबसे पहले Nauk (1850) द्वारा तैयार की गई थी।

१.१ परिभाषाएँ

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

अध्ययन कंप्यूटर सिमुलेशन (कम्प्यूटेशनल सिमुलेशन) के आधार पर आयोजित किया गया था। इस या उस परिकल्पना का परीक्षण करने के लिए, हमने n = (१०, २०, ३०, ४०, ५०, hyp०, hyp०, 800०, ९ ००, २००, ३००, ५००, hyp००, ०००, ३०००, ३००) मूल्यों की एक विस्तृत श्रृंखला में कम्प्यूटेशनल प्रयोग किए। 5000, 10000, 30,000, 50,000, 80,000, 10 ⁵ , 3 * 10 ⁵ , 5 * 10 ⁵ , 10 ⁶ , 3 * 10 ⁶ , 5 * 10 ⁶ , 10 ⁷ , 3 * 10 ⁷ , 5 * 10 ⁷ , 8 * 10 ⁷ , 10 ⁸ ) और, n के मूल्य के आधार पर, विश्लेषण के लिए पर्याप्त रूप से बड़े नमूने उत्पन्न किए गए थे। हम इस तरह की सूची को कम्प्यूटेशनल प्रयोगों के संचालन के लिए " एन मूल्यों की आधार सूची " कहते हैं। सभी गणना एक नियमित कंप्यूटर पर की गई। असेंबली (2013 की शुरुआत) के समय, यह काफी सफल कॉन्फ़िगरेशन था: CPU - Intel Core i7-3820, 3.60 GH, RAM-32.0 GB, GPU-NVIDIA Ge Forse GTX 550 Ti, डिस्क डिवाइस- ATA Intel SSD, SCSI, OS- 64-बिट ऑपरेटिंग सिस्टम विंडोज 7 प्रोफेशनल । हम इस किट को केवल डेस्कटॉप -13 कहते हैं ।

2. डेटा की तैयारी

एल्गोरिथ्म एक फ़ाइल को पढ़ने से शुरू होता है जिसमें कश्मीर रानियों की मनमानी रचना के वितरण पर एक आयामी डेटा होता है। यह माना जाता है कि डेटा निम्न तरीके से तैयार किया गया है। आज्ञा देना एक शून्य सरणी Q (i) = 0, i = (1, ..., n) , जहां इस सरणी की कोशिकाओं के सूचकांक समाधान मैट्रिक्स के पंक्ति सूचकांकों के अनुरूप हैं। यदि समाधान मैट्रिक्स की कुछ मनमानी पंक्ति i में स्थिति j में एक रानी है, तो असाइनमेंट Q (i) = j किया जाता है। इस प्रकार, रचना का आकार k , सरणी Q के गैर-अक्षीय कोशिकाओं की संख्या के बराबर होगा । (उदाहरण के लिए, क्यू = (0, 0, 5, 0, 4, 0, 3, 0, 0, 0) का अर्थ है कि हम मैट्रिक्स n = 10 पर k = 3 क्वीन्स की एक संरचना पर विचार कर रहे हैं, जहां क्वीन्स 3rd में स्थित हैं। 5 वीं और 8 वीं पंक्ति, क्रमशः पदों में: 5, 4, 3)।

3. समाधान n- क्वींस समस्या की शुद्धता की पुष्टि के लिए एल्गोरिथ्म

अनुसंधान के लिए, हमें एक एल्गोरिथ्म की आवश्यकता है जो हमें कम समय में n- क्वींस समस्या के समाधान की शुद्धता का निर्धारण करने की अनुमति देगा। प्रत्येक पंक्ति और प्रत्येक स्तंभ में रानियों के स्थान को नियंत्रित करना सरल है। प्रश्न विकर्ण सीमाओं के बारे में है। हम इस तरह के लेखांकन के लिए एक प्रभावी एल्गोरिथ्म का निर्माण कर सकते हैं यदि हम समाधान मैट्रिक्स के प्रत्येक सेल को एक निश्चित नियंत्रण वेक्टर के एक निश्चित सेल में मैप कर सकते हैं जो कि प्रश्न में सेल पर विकर्ण प्रतिबंधों के प्रभाव की विशिष्ट रूप से विशेषता होगी। फिर, नियंत्रण वेक्टर की कोशिका स्वतंत्र या व्यस्त है या नहीं, इस आधार पर, कोई निर्णय कर सकता है कि निर्णय मैट्रिक्स का संबंधित सेल मुक्त या बंद है या नहीं।इस तरह के एक विचार को पहली बार सॉसिक एंड गु (1990) द्वारा उपयोग में लिया गया था और क्वीन्स के विभिन्न पदों के बीच संघर्ष स्थितियों की संख्या को जमा करने के लिए उपयोग किया गया था । हम नीचे प्रस्तुत एल्गोरिथ्म में एक समान विचार का उपयोग करते हैं, लेकिन केवल इस बात को ध्यान में रखते हैं कि समाधान मैट्रिक्स की कोशिका मुक्त है या व्यस्त है। चित्रा 1, एक उदाहरण के रूप में, ऊपर एक 8 x 8 बिसात दिखाता है जिसके ऊपर 24 कोशिकाओं का एक क्रम स्थित है ।


अंजीर। 1. नियंत्रण सारणी D1 और D2 की संबंधित कोशिकाओं के लिए मैट्रिक्स कोशिकाओं के विकर्ण अनुमानों के पत्राचार का एक डेमो उदाहरण , ( n = 8)

नियंत्रण वेक्टर D1 के तत्वों के रूप में पहले 15 कोशिकाओं पर विचार करें।। समाधान मैट्रिक्स के किसी भी सेल से सभी बाएं विकर्णों के अनुमान नियंत्रण वेक्टर डी 1 की कोशिकाओं में से एक में आते हैं । वास्तव में, ऐसे सभी अनुमान दो समानांतर लाइन सेगमेंट के अंदर स्थित होते हैं, जिनमें से एक वेक्टर D1 के पहले सेल के साथ मैट्रिक्स (8.1) की सेल को जोड़ता है , और दूसरा - मैट्रिक्स (1.8) के सेल को कंट्रोल डी 1 के 15 वें सेल के साथ जोड़ता है । हम सही विकर्ण अनुमानों के लिए एक समान परिभाषा देते हैं। ऐसा करने के लिए, सेल 1 से सेल 9 तक मूल को दाईं ओर ले जाएं, और नियंत्रण वेक्टर D2 के तत्वों के रूप में 16 कोशिकाओं के अनुक्रम पर विचार करें।(चित्रा में, ये 9 वीं से 24 वीं तक की कोशिकाएं हैं) समाधान मैट्रिक्स के किसी भी सेल से सभी सही विकर्णों के अनुमान इस नियंत्रण वेक्टर की कोशिकाओं में से एक में गिर जाएंगे, 16 वीं के माध्यम से 2 वें सेल से शुरू होगा (आकृति में, 10 से 24 वीं करने के लिए th)। यहाँ, इस तरह के सभी अनुमान समानांतर लाइनों के दो खंडों के बीच स्थित हैं - सॉल्यूशन मैट्रिक्स के सेल (8,8) को वेक्टर D2 के सेल 16 (आकृति में 24 सेल) और सेल के साथ समाधान मैट्रिक्स के सेल (1,1) को जोड़ने वाले खंड के बीच स्थित है। नियंत्रण वेक्टर डी 2 (चित्रा में सेल 10) के 2। समाधान मैट्रिक्स के सभी कोशिकाओं के अनुमान एक ही बाएं विकर्ण पर पड़े हैं जो बाएं नियंत्रण वेक्टर D1 के एक ही सेल में आते हैं।, क्रमशः, एक ही सही विकर्ण पर पड़ी हुई समाधान मैट्रिक्स की सभी कोशिकाओं के अनुमानों को सही नियंत्रण वेक्टर 2 के एक ही सेल में गिर जाता है । इस प्रकार, ये दो नियंत्रण वैक्टर डी 1 और डी 2 , निर्णय मैट्रिक्स के किसी भी सेल के लिए सभी विकर्ण अवरोधों के पूर्ण नियंत्रण की अनुमति देते हैं।

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

1. विकर्ण अवरोधों को नियंत्रित करने के लिए, दो मैट्रिक्स डी 1 (1: n2) और D2 (1: n2) , जहां n2 = 2 * n, और एक सरणी B (1: n) बनाएं , जो समाधान मैट्रिक्स के स्तंभों के अधिभोग को नियंत्रित करते हैं। शून्य इन तीन सरणियों।

2. हम सही ढंग से स्थापित क्वीन्स की संख्या ( टोटपोस = 0 ) के काउंटर का परिचय देते हैं । लगातार, एक चक्र में, पहली पंक्ति से शुरू करते हुए, हम प्रदान की गई सभी रानियों के पदों पर विचार करते हैं। यदि Q (i)> 0 , तो पंक्ति I के सूचकांक और रानी की स्थिति के सूचकांक के आधार पर j = Q (i) में, हम नियंत्रण सारणी D1 (r) और D2 (t) के लिए संबंधित सूचकांकों का निर्माण करते हैं :
r = n + j - i
t = j + i

3. यदि सभी स्थितियां ( D1 (r) = 0, D2 (t) = 0, B (j) = 0 ) संतुष्ट हैं , तो इसका मतलब यह होगा कि सेल ( i, j) स्वतंत्र है और पहले से स्थापित रानियों द्वारा बनाए गए विकर्ण प्रतिबंधों के प्रक्षेपण क्षेत्र में नहीं आता है। इस स्थिति में रानी की स्थिति सही है। यदि इनमें से कम से कम एक शर्त पूरी नहीं होती है, तो इस तरह की स्थिति का चुनाव क्रमशः गलत होगा, और निर्णय गलत होगा।

4. यदि समाधान सही है, तो सही ढंग से स्थापित क्वीन्स ( टोटपोस = टोटपोस + 1 ) की संख्या के काउंटर को बढ़ाएं , और नियंत्रण सरणियों की संबंधित कोशिकाओं को बंद करें: (डी 1 (आर) = 1, डी 2 (टी = 1, बी (जे) = 1) । इसलिए हम कॉलम के सभी सेल बंद कर देते हैं(j) और सॉल्यूशन मैट्रिक्स की वे कोशिकाएँ जो सेल (i, j) में लेफ्ट और राइट विकर्णों के साथ स्थित होती हैं ।

5. सभी शेष पदों के लिए सत्यापन प्रक्रिया को दोहराएं।
शायद यह n- क्वींस समस्या के समाधान की शुद्धता के मूल्यांकन के लिए सबसे तेज़ एल्गोरिदम में से एक है । डेस्कटॉप -13 पर समाधान 10 ⁶ x 10 ⁶ के मैट्रिक्स के लिए एक मिलियन पदों का सत्यापन समय 0.175 सेकंड है, जो लगभग "एंटर" कुंजी दबाने के समय से मेल खाती है। जाहिर है, यह एल्गोरिथ्म रैखिक है एन के संबंध में गिनती के समय के संबंध में ।

4. समस्या को हल करने के लिए एल्गोरिथ्म का विवरण

सामान्य । n- क्वींस कम्प्लीटेशन समस्या एक क्लासिक नॉन-डिसेंटिविस्टिक समस्या है। इसके समाधान की मुख्य कठिनाई इस पंक्ति में पंक्ति सूचकांक और स्थिति सूचकांक को चुनने के मुद्दे से जुड़ी हुई है, ऐसी स्थिति में जब राज्य का स्थान विशाल होता है। सभी संभावित समाधानों की खोज करते समय, ऐसी समस्या उत्पन्न नहीं होती है। हमें राज्य स्थान में सभी मान्य खोज शाखाओं पर विचार करना चाहिए, और जिस क्रम में उन्हें माना जाता है वह कोई मायने नहीं रखता है। हालांकि, जब k रानियों की एक मनमानी रचना को एक पूर्ण समाधान तक पूरा करने की आवश्यकता होती है, तो इस मामले में पंक्ति और स्तंभ सूचकांकों का चयन करने के लिए एक एल्गोरिथ्म की आवश्यकता होती है, जो मौजूदा संरचना को पर्याप्त रूप से मानता है और दूसरों की तुलना में तेजी से समाधान की ओर जाता है। इस परियोजना में, हमने निम्नलिखित सामान्य स्थिति के आधार पर चुनाव का प्रश्न तय किया - यदि हम ऐसी स्थितियाँ नहीं बना सकते जो किसी पंक्ति या इस पंक्ति की किसी भी स्थिति को दूसरों पर वरीयता दे, तो हम एक यादृच्छिक चयन एल्गोरिदम का उपयोग करते हैं समान रूप से यादृच्छिक संख्याओं का वितरण किया । समस्याओं को हल करने के लिए एक समान यादृच्छिक चयन विधि जिसमें राज्य स्थान विशाल है, काफी स्वाभाविक है। जटिल समस्याओं को हल करने के लिए एल्गोरिदम के विकास में यादृच्छिक चयन के उपयोग के लिए पूरी तरह से एक DIMACS कार्यशाला की कार्यवाही (1999) की श्रृंखला के संस्करणों में से एक था। यादृच्छिक चयन एल्गोरिदम का सही कार्यान्वयन एक काफी उत्पादक समाधान हो सकता है, हालांकि यह समाधान के पूरा होने के लिए एक आवश्यक लेकिन पर्याप्त स्थिति नहीं है। Sosic and Gu (1990) n-Queens समस्या को हल करने के लिए एक यादृच्छिक चयन एल्गोरिदम का उपयोग करने वाले पहले अध्ययनों में से एक है। उन्होंने जिस एल्गोरिथ्म की जांच की वह काफी सरल और संक्षिप्त विचार पर आधारित है। आज्ञा दें कि 1 से n तक की संख्याएँ हैं, जिन्हें यादृच्छिक रूप से पुनर्व्यवस्थित किया गया है। इस तरह की संख्याओं का एक महत्वपूर्ण गुण है। यह इस तथ्य में समाहित है कि क्वीन की स्थिति (प्रति पंक्ति एक नंबर) के रूप में समाधान मैट्रिक्स की विभिन्न पंक्तियों पर कोई फर्क नहीं पड़ता है, कोई फर्क नहीं पड़ता कि समस्या के बयान में पहले दो नियम हमेशा पूरे होंगे: प्रत्येक पंक्ति और प्रत्येक कॉलम में नहीं होगा एक से अधिक रानी। हालांकि, इस प्रकार प्राप्त पदों का केवल एक हिस्सा विकर्ण प्रतिबंधों से मुक्त होगा। अन्य भाग पहले से स्थापित रानियों के साथ "संघर्ष" की स्थिति में होगा। इस स्थिति से बाहर निकलने के लिए, लेखकों ने एक पूर्ण समाधान प्राप्त करने के लिए परस्पर विरोधी स्थितियों की तुलना और परस्पर संबंध बनाने की विधि का उपयोग किया। हमारे प्रस्तावित एल्गोरिथ्म में, संघर्ष की स्थिति असंभव है, क्योंकि समस्या को हल करने के प्रत्येक चरण में, रानी को पंक्ति में सेल में स्थापित किया जाता है, केवल तभी जब सेल मुक्त हो।

4.1 बैक ट्रैकिंग के लिए एक मॉडल का चयन (बीटी)

किसी समस्या का समाधान खोजने की प्रक्रिया में, एक स्थिति उत्पन्न हो सकती है जब समाधान की एक क्रमिक श्रृंखला एक मृत अंत की ओर ले जाती है। यह गैर-नियतात्मक समस्याओं का एक "आनुवंशिक" गुण है। इस मामले में, आपको पिछले चरणों में से एक पर वापस जाने की आवश्यकता है, इस स्तर के अनुसार कार्य की स्थिति को पुनर्स्थापित करें और इस स्थिति से समाधान की खोज फिर से शुरू करें। सवाल यह है कि पिछले स्तरों में से कौन सा वापस आ जाना चाहिए और इस तरह के कितने स्तर होने चाहिए (स्तर से, हमारा मतलब है एक निश्चित संख्या में सही ढंग से स्थापित क्वीन्स के साथ समस्या को हल करने में एक निश्चित कदम)। जाहिर है, वापस जाने के लिए एक समाधान स्तर चुनना उतना ही प्रासंगिक है जितना कि पंक्ति सूचकांक या उस पंक्ति में स्थिति सूचकांक चुनना। इसलिए, इस समस्या को हल करने के दृष्टिकोण की परवाह किए बिना, पहले वापस लौटने के लिए बुनियादी स्तरों की संख्या का निर्धारण करना आवश्यक है, साथ ही इनमें से किसी एक स्तर पर लौटने के लिए तंत्र और शर्तें भी। हमारे प्रस्तावित एल्गोरिथ्म में, हम समाधान मैट्रिक्स को तीन बुनियादी स्तरों में विभाजित करते हैं। ये रिटर्न प्वाइंट हैं। यदि समाधान के परिणामस्वरूप, एक गतिरोध होता है, तो, कार्य के मापदंडों के आधार पर, हम इन तीन बुनियादी स्तरों में से एक पर वापस लौटते हैं। पहला बेस लेवल ( baseLevel1 ) राज्य से मेल खाता है जब प्रश्न में रचना का डेटा सत्यापन पूरा हो जाता है। यह कार्यक्रम की शुरुआत है। निम्नलिखित दो आधार स्तरों ( बेसलवेल 2 और बेसलवेल 3 ) के मूल्य मैट्रिक्स एन के आकार पर निर्भर करते हैं। समाधान मैट्रिक्स के आकार पर इन बुनियादी मूल्यों की अनुभवजन्य निर्भरता बड़ी संख्या में कम्प्यूटेशनल प्रयोगों के आधार पर स्थापित की गई थी। इस निर्भरता के अधिक सटीक प्रतिनिधित्व के लिए, हमने 7 से 10 से ⁸ तक के पूरे अंतराल को दो भागों में विभाजित किया। यू = लॉग (एन) करें , फिर यदि एन <30 000 , तो

बेसलवेल 2 = एन - राउंड (12.749568 * u3 - 46.535838 * u2 + 120.011829 * यू - 89.600272)
बेसलवेल 3 = एन - राउंड (9.717958 * u3 - 46.144187 * u2 + 101.296409 * यू - 50.669273)

अन्यथा

बेसलवेल 2 = एन - राउंड (-0.886344 * u3 + 56.136743 * u2 + 146.486415 * u + 227.967782)
बेसलवेल 3 = एन - राउंड (14.959815 * u3 - 253.661725 * u2 + 1584.713376 * u - 3060.691342)

4.2 ब्लॉक संरचना

एल्गोरिथ्म का निर्माण पांच घटना ब्लॉकों के अनुक्रम के रूप में किया गया है, जहां प्रत्येक घटना समस्या के समाधान के एक निश्चित हिस्से के निष्पादन के साथ जुड़ी हुई है। प्रत्येक ब्लॉक में प्रसंस्करण एल्गोरिदम एक दूसरे से अलग होते हैं। पांच ब्लॉकों में से केवल तीन समाधान की अनुक्रमिक श्रृंखला बनाने के लिए काम करते हैं, और शेष दो ब्लॉक प्रारंभिक हैं। ब्लॉक संख्या का चयन, जिसमें से गणना शुरू होती है, n के मान पर और आधार के आकार की तुलना करने के परिणामों पर निर्भर करती है baseLeve2 और baseLevel3 के मूल्यों के साथ। एक अपवाद मान n = (7, ..., 99) का अंतराल है, जिसे इस खंड में एल्गोरिदम व्यवहार की ख़ासियत के कारण "अशांत क्षेत्र" कहा जा सकता है। मानों के लिए n = (7, ..., 49) , संरचना के आकार की परवाह किए बिना, डेटा में प्रवेश और निगरानी के बाद, गणना 4 वें ब्लॉक से शुरू होती है। मानों के लिए n = (50, ..., 99) , रचना के आकार के आधार पर, गणना दूसरे ब्लॉक से या चौथे से शुरू होती है। जैसा कि ऊपर उल्लेख किया गया है, समस्या को हल करने के प्रत्येक चरण में, लाइन में केवल उन पदों पर विचार किया जाता है जो पहले से स्थापित रानियों द्वारा बनाई गई प्रतिबंधों के क्षेत्र में नहीं आते हैं। यह इन पदों को मुक्त कहा जाता है ।
आइए हम संक्षेप में बताएं कि कार्यक्रम के इन पांच ब्लॉकों में से प्रत्येक में क्या गणना की जाती है।

4.3 एल्गोरिथ्म की शुरुआत

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

4.4 ब्लॉक 1

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

क) दो सूचियाँ बनती हैं: मुक्त पंक्ति सूचकांकों की सूची और मुक्त स्तंभ सूचकांकों की सूची;

बी) इन सूचियों में से प्रत्येक में यादृच्छिक रूप से पुनर्व्यवस्थित संख्या;

c) एक लूप में, मूल्यों की प्रत्येक क्रमिक जोड़ी (i, j) , जहां इंडेक्स (i) को फ्री रो इंडेक्स की सूची से और इंडेक्स (j) को फ्री कॉलम इंडेक्स की सूची से चुना जाता है, एक संभावित रानी स्थिति माना जाता है और यह जाँच की जाती है कि क्या यह विकर्ण अपवाद के प्रक्षेपण क्षेत्र में स्थिति।

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

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

4.5 खंड 2

यह ब्लॉक ब्लॉक -3 में संक्रमण के लिए एक प्रारंभिक चरण के रूप में कार्य करता है। इस स्तर पर, शेष नि: शुल्क लाइनों ( फ्रीरो ) की संख्या n की तुलना में काफी कम है। यह आपको छोटे आकार के एल (1: freeRows, 1: freeRows) के मैट्रिक्स के आकार के मूल मैट्रिक्स से घटनाओं को स्थानांतरित करने की अनुमति देता है। इसके अलावा, मूल समाधान मैट्रिक्स में शेष मुक्त पंक्तियों और मुक्त स्तंभों के बारे में जानकारी के आधार पर, सरणी एल की संबंधित कोशिकाओं को शून्य लिखा जाता है, यह दर्शाता है कि ये कोशिकाएं स्वतंत्र हैं। इस "प्रक्षेपण" संक्रमण के साथ, मूल मैट्रिक्स के संगत सूचकांकों के साथ नई मैट्रिक्स की पंक्ति और स्तंभ सूचकांकों का पत्राचार संरक्षित है। यह ध्यान रखना महत्वपूर्ण है कि हालांकि, इस समस्या को हल करने की प्रक्रिया में, सभी घटनाएं आकार nxn के प्रारंभिक मैट्रिक्स पर प्रकट होती हैं, और इस तरह की मैट्रिक्स कार्रवाई का मुख्य क्षेत्र है, वास्तव में ऐसा मैट्रिक्स नहीं बनाया जाता है , और केवल पंक्ति सूचकांकों A (1: n) के लिए लेखांकन के नियंत्रण को नियंत्रित करता है। इस मैट्रिक्स के कॉलम B (1: n) ।

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

4.6 ब्लॉक 3

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

4.7 ब्लॉक 4

इस ब्लॉक में, ब्लॉक -5 के नियंत्रण के हस्तांतरण के लिए डेटा तैयार किया जाता है। इस चरण के लिए, ब्लॉक -3 में प्रक्रिया को पूरा करने के बाद, नि: शुल्क लाइनों ( nRow ) की संख्या और भी कम हो गई है। इसलिए, बड़े सरणी से छोटी सरणी में घटनाओं का अनुवाद करना भी फायदेमंद है। यह दृष्टिकोण हमें इस चरण में आवश्यक शेष लाइनों के लिए आवश्यक विशेषताओं को जल्दी से निर्धारित करने का अवसर देता है। विशेष महत्व का तथ्य यह है कि इस तरह के एक सरणी के आधार पर, गणना को पूरा करने के बिना कई चरणों के लिए खोज शाखा की संभावनाओं की भविष्यवाणी करना संभव है। हालत काफी सरल है। यदि यह पता चला है कि शेष नि: शुल्क लाइनों के बीच एक ऐसी रेखा है जिसमें कोई मुक्त स्थिति नहीं है, तो विचाराधीन खोज शाखा बंद है और नियंत्रण निचले स्तर के ब्लॉकों में से एक में स्थानांतरित किया जाता है। यहां की गई प्रारंभिक क्रियाएं काफी हद तक ब्लॉक -2 में किए गए समान हैं। मुक्त पंक्तियों और मुक्त स्तंभों के मूल सूचकांकों के आधार पर, एक नया 2-आयामी सरणी बनाई जाती है, जिसके शून्य मान मूल समाधान मैट्रिक्स में मुक्त पदों के अनुरूप होते हैं। इसके अलावा, इस ब्लॉक में एक विशेष सरणी E (1: nRow, 1: nRow) बनाई गई है, जिसके आधार पर आप रानी को सेट करने के लिए पोजीशन (i, j) का चयन करने पर बंद होने वाली शेष लाइनों में मुक्त पदों की संख्या निर्धारित कर सकते हैं। स्रोत मैट्रिक्स। नियंत्रण को ब्लॉक 5 में स्थानांतरित करने से पहले, निम्नलिखित क्रियाएं की जाती हैं:

क) सभी शेष लाइनों में रिक्त पदों की मात्रा निर्धारित की जाती है,

ख) सवाल में पंक्तियों के लिए नि: शुल्क पदों की मात्रा का एक सरणी, आरोही क्रम में क्रमबद्ध है,

ग) यदि सभी शेष नि: शुल्क लाइनों में मुफ्त स्थितियां हैं (अर्थात इस रैंक सूची में न्यूनतम मान 0 से भिन्न है), तो नियंत्रण को ब्लॉक -5 में स्थानांतरित कर दिया जाता है।

यदि यह पता चलता है कि किसी भी शेष पंक्ति में कोई मुफ्त स्थिति नहीं है, तो संग्रहीत सरणियों के आधार पर आवश्यक सरणियों को पुनर्स्थापित किया जाता है, और, कार्य के मापदंडों के आधार पर, नियंत्रण बुनियादी स्तरों में से एक में स्थानांतरित किया जाता है।

डी) इस 4 वें स्तर के लिए सभी नियंत्रण सरणियों की बैकअप प्रतियां बनाई जाती हैं।

4.8 ब्लॉक 5

यह चरण अंतिम है, और यहां, खोज शाखा के गठन को अधिक "संतुलित" और "तर्कसंगत" किया जाता है। यह "अंतिम मील" है, केवल कुछ ही मुफ्त लाइनें हैं। लेकिन एक ही समय में, यह सबसे कठिन हिस्सा है। सभी गलतियाँ जो संभावित रूप से हल के लिए खोज की शाखा के गठन के पिछले चरणों में की जा सकती थीं, कुल मिलाकर यहाँ दिखाई देती हैं - लाइन में मुक्त स्थिति की कमी के रूप में।

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

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

a) एक मुफ्त लाइन का चयन करें । सभी शेष नि: शुल्क लाइनों को माना जाता है, और प्रत्येक लाइन में मुफ्त पदों की संख्या निर्धारित की जाती है। पंक्ति का चयन किया जाता है जिसके लिए मुक्त पदों की संख्या न्यूनतम है। यह शेष कुछ लाइनों में अंतिम रिक्त पदों को बाहर करने की संभावना के साथ जुड़े जोखिमों को कम करता है जिसमें राज्य रिक्त पदों की संख्या ( न्यूनतम जोखिम नियम ) के संदर्भ में न्यूनतम और महत्वपूर्ण है। संयोग से, यह इस नियम के साथ है कि इस पांचवें ब्लॉक में पहले चक्र का सूचकांक एक पंक्ति में मुक्त पदों की संख्या के न्यूनतम मूल्य के साथ पंक्तियों के क्रमिक चयन के साथ शुरू होता है। यदि कुछ चरणों में यह पता चलता है कि दो पंक्तियों में समान न्यूनतम पद हैं, तो पहले स्थान पर सूचीबद्ध दो पदों में से एक का सूचकांक बेतरतीब ढंग से चुना गया है। यदि मुक्त पदों की समान न्यूनतम संख्या वाली पंक्तियों की संख्या दो से अधिक है, तो पहले स्थान पर सूचीबद्ध तीन पदों में से एक की सूची को बेतरतीब ढंग से चुना गया है।

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

5. चयन एल्गोरिदम की प्रभावशीलता का विश्लेषण

रैंडसेट और रैंडसेट एल्गोरिथ्म की दक्षता । इस एल्गोरिथ्म की क्षमताओं का विश्लेषण करने के लिए, एक कम्प्यूटेशनल प्रयोग किया गया था, जिसमें रैंडसेट और रैंडसेट मॉडल के आधार पर समाधान मैट्रिक्स में रानियों को रखने में शामिल था जब तक कि यह संभावना मौजूद है। जैसे ही खोज शाखा एक मृत अंत तक पहुंच गई, या एक पूर्ण समाधान प्राप्त किया गया था, रचना का आकार, समाधान का समय निर्धारित किया गया था, और परीक्षण फिर से दोहराया गया था। संपूर्ण मान n सूची के लिए कम्प्यूटेशनल प्रयोग किए गए थे । मूल्यों के लिए दोहराया परीक्षणों की संख्या n = (30, 40, ..., 90, 100, 200, 300, 500, 800, 1000) शेष मानों के लिए, एक लाख के बराबर थी , परीक्षणों की संख्या n बढ़ने के साथ, धीरे-धीरे 100000 से घटकर 100 हो गया। कम्प्यूटेशनल प्रयोगों के परिणामों का विश्लेषण हमें निम्नलिखित निष्कर्ष निकालने की अनुमति देता है:

ए) रैंडसेट और रैंडसेट प्रक्रिया के केवल पहले चक्र के परिणामस्वरूप, औसतन सभी रानियों का लगभग 60% सही ढंग से रखा गया है। के लिए n = 100, ठीक से स्थान दिया गया है क्वीन्स की संख्या 60.05% है। N के मूल्य में वृद्धि के साथ, यह मूल्य धीरे-धीरे कम हो जाता है, और n = 10 ^{7 के लिए यह} 59.97% हो जाता है।

बी) प्राप्त रचनाओं की लंबाई के मूल्यों के वितरण का हिस्टोग्राम एक ही रूप है, निर्णय मैट्रिक्स के आकार की परवाह किए बिना एन।। इसके अलावा, उन सभी में एक विशेषता है - वितरण का बाईं ओर (मोडल मान के लिए) दाईं ओर से भिन्न होता है। चित्र 2 में, उदाहरण के लिए,


अंजीर के लिए संबंधित हिस्टोग्राम । 2. रैंडसेट और रैंडसेट मॉडल ( एन = 100, नमूना आकार = 10 ⁶ ) के लिए विभिन्न लंबाई के समाधान के वितरण का एक हिस्टोग्राम ।

n = 100। ऐसा लगता है कि हिस्टोग्राम को दो अलग-अलग घटनाओं के आवृत्ति वितरण से एकत्र किया जाता है, क्योंकि वितरण के बाएं और दाएं हिस्सों में घटनाओं की आवृत्ति अलग-अलग होती है। इस वितरण का वर्णन करने के लिए, यह सामान्य वितरण के घनत्व के दो कार्यों का उपयोग करने के लिए सबसे उपयुक्त है, जिनमें से एक मोडल मान के अंतराल को कवर करता है, दूसरा - मोडल मान के बाद अंतराल।

ग) इस एल्गोरिथ्म पर आधारित निर्णय मैट्रिक्स में निर्धारित क्वीन्स ( क्यूमेन ) की संख्या का औसत मूल्य n के साथ बढ़ता है । जैसा कि चित्र 3 से देखा जा सकता है, जहां मैट्रिक्स आकार n पर qMean / n अनुपात की निर्भरता का एक ग्राफ प्रस्तुत किया जाता है , यह अनुपात मैट्रिक्स आकार में वृद्धि के साथ बढ़ता है। उदाहरण के लिए, अंजीर। 3. समाधान मैट्रिक्स के विभिन्न आकारों के लिए n के मूल्य पर अनुपात qMean / n की निर्भरता । मॉडल रैंडसेट और रैंडसेट है , क्यूमेन समाधान की लंबाई का औसत मूल्य है। यदि 100x100 आकार के मैट्रिक्स के लिए , पदों के चयन के लिए एल्गोरिथ्म रैंडसेट और रैंडसेट है



औसतन 89 लाइनों पर रानियों को रखने के लिए "बिना रुके" की अनुमति देता है, फिर 1000x1000 मैट्रिक्स के लिए , ऐसी लाइनों की संख्या औसतन 967 तक बढ़ जाती है।

घ) रैंडसेट और रैंडसेट एल्गोरिथ्म के आधार पर , आप एक पूर्ण समाधान प्राप्त कर सकते हैं, लेकिन इस दृष्टिकोण की "उत्पादकता" बेहद कम है। । जैसा कि चित्र 4 से देखा जा सकता है,


अंजीर के लिए। 4. एन में वृद्धि के साथ रैंडसेट और रैंडसेट मॉडल में एक पूर्ण समाधान प्राप्त करने की संभावना में कमी । n = 7 के मान , एक पूर्ण समाधान प्राप्त करने की संभावना 0.057 है । इसके अलावा, बढ़ती एन के साथ

एक पूर्ण समाधान प्राप्त करने की संभावना तेजी से घट जाती है, asymptotically शून्य तक पहुंचने। मूल्य n = 48 से शुरू होकर , पूर्ण समाधान प्राप्त करने की संभावना 10 ^-6 के क्रम की है । थ्रेशोल्ड मान n = 70 के बाद , n के बाद के मानों के लिए , एक भी पूर्ण समाधान प्राप्त नहीं हुआ ( एक मिलियन के बराबर परीक्षणों की संख्या के साथ )।

ई) रैंडसेट और रैंडसेट मॉडल बहुत ही उच्च गति पर खोज शाखाएं बनाता है। के लिए n = 1000 रचना की प्राप्ति की औसत समय 0.0015 सेकंड है। रचनाओं की औसत लंबाई 967 है। तदनुसार, n = 10 ^{6 के लिए}2.6754 सेकंड की औसत समय, रचनाओं के एक औसत लंबाई 999793. साथ

) च एक छोटे से अंतराल के अलावा n <= 70 है, जब मॉडल randSet और randSet , बहुत दुर्लभ मामलों में अन्य सभी मामलों में पूर्ण समाधान को जन्म दे सकती, शाखा समाप्त होता है समाधान नकारात्मक रचना के गठन जो पूर्ण समाधान तक पूरा नहीं किया जा सकता है। तो रैंडसेट और रैंडसेट एल्गोरिथ्मइसका एक महत्वपूर्ण लाभ है - खोज शाखा के गठन की उच्च गति, और एक महत्वपूर्ण दोष यह है कि यदि संरचना का आकार एक निश्चित सीमा मूल्य से अधिक है, तो यह एल्गोरिथ्म रचनाओं के गठन की ओर जाता है जो एक पूर्ण समाधान तक पूरा नहीं किया जा सकता है। इस खामी को दूर करने के लिए, हम खोज शाखा के गठन को रोकते हैं जब थ्रेशोल्ड बेसवेल -2 पहुँच जाता है । रैंड और रैंड

एल्गोरिथ्म की दक्षता । रैंड और रैंड एल्गोरिथ्म की क्षमताओं का निर्धारण करने के लिए, एन मूल्यों की एक मूल सूची के लिए एक काफी विस्तृत कंप्यूटर सिमुलेशन किया गया था । मॉडल के मामले में randSet और randSetअधिकांश मामलों में सेवानिवृत्त होने की संख्या एक मिलियन के बराबर थी । अन्य मूल्यों के लिए, परीक्षणों की संख्या धीरे-धीरे 100,000 से घटकर 100 हो गई।

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

ए) रैंड एंड रैंड मॉडल "हार्ड" के रूप में रैंडसेट और रैंडसेट मॉडल के रूप में काम नहीं करता है । अगर हम रैंड एंड रेंड मॉडल के कुछ "इंडेक्स ऑफ़ रैंक्स्ड यूज़ ऑफ़ प्रोवाइड" के बारे में बात करते हैंहर कदम पर संसाधनों का अधिक तर्कसंगत उपयोग करता है। यह इस तथ्य की ओर जाता है कि, उदाहरण के लिए, n = 30 पर, इस मॉडल में 0.00170 का पूर्ण समाधान प्राप्त करने की संभावना रैंडसेट और रैंडसेट मॉडल के लिए 0.00011 के समान मूल्य से 15 गुना अधिक है । इसके अलावा, यहाँ, थ्रेशोल्ड मान n = 370 तक, एक मिलियन परीक्षणों के दौरान कम से कम एक पूर्ण समाधान प्राप्त करने की संभावना बनी हुई है। इस सीमा मूल्य के बाद, एक मिलियन के बराबर परीक्षणों की संख्या के साथ n के बाद के मूल्यों के लिए, रैंड और रैंड मॉडल के आधार पर एक पूर्ण समाधान प्राप्त नहीं किया गया था।

बी) यह एल्गोरिथ्म रैंडसेट और रैंडसेट एल्गोरिथ्म की तुलना में बहुत धीमा है । अगर के लिएn = 1000 आकार 967 की एक रचना उत्पन्न करने के लिए, एक रचना प्राप्त करने का औसत समय 0.0497 सेकंड होगा, जो रैंडसेट और रैंडसेट मॉडल के लिए 0.0015 के संबंधित मूल्य से 33 अधिक है ।

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

एल्गोरिथ्म के संचालन को नेत्रहीन रूप से प्रदर्शित करने के लिएनिम्नलिखित प्रयोग किया गया था:

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


अंजीर। 5. रानियों के स्थान के बाद शेष नि: शुल्क लाइनों में मुफ्त पदों की संख्या को कम करना। क्रमिक रूप से नियमित रूप से पदों का चयन।

विचार के तहत मॉडल के अनुरूप परिणाम प्रस्तुत किए जाते हैं। स्पष्टता के लिए, ग्राफ़ चरणों (10, 40, 60) के बाद ही परिणाम दिखाता है। क्रमिक रूप से चयन करने वाले पदों के मॉडल के लिए, 62 वीं चरण के बाद अंतिम एक ग्राफ है, क्योंकि 63 वीं पंक्ति में एक मुक्त स्थान की कमी के कारण खोज शाखा समाप्त हो जाती है। दूसरी ओर, रैंड एंड रैंड मॉडल में , रानी को रखने के 70 वें चरण के बाद अंतिम ग्राफ प्रस्तुत किया जाता है, हालांकि यहां, सही ढंग से रखी गई रानियों की औसत संख्या 89 तक पहुंचती है, जो अनुक्रमिक मॉडल की तुलना में 26 कदम अधिक है। रैंड एंड रैंड मॉडल में रेखांकन का एक अजीब दृश्यइस तथ्य के कारण कि पंक्ति सूचकांक को शेष मुक्त पंक्तियों के बीच बेतरतीब ढंग से चुना गया है, और इसलिए वे पूरे समाधान मैट्रिक्स में बेतरतीब ढंग से बिखरे हुए हैं। इन दो आंकड़ों की तुलना से पता चलता है कि स्थिति चयन के अनुक्रमिक मॉडल में, मुक्त पदों की संख्या की परिवर्तनशीलता की सीमा रैंड एंड रैंड मॉडल की तुलना में अधिक है । यह इस तथ्य के कारण है कि नियमित चयन के साथ, विकर्ण गैर-समान रूप से शेष पंक्तियों में मुक्त पदों को रोकता है, जो इस तथ्य की ओर जाता है कि कुछ पंक्तियों में रिक्त पदों की संख्या में कमी की दर अन्य पंक्तियों की तुलना में अधिक है।


अंजीर। 6. रानियों के स्थान के बाद शेष मुक्त लाइनों में मुक्त पदों की संख्या को कम करना। पोजिशनिंग मॉडल रैंड एंड रैंड है ।

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

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

6. न्यूनतम जोखिम नियम (n = 100) का उपयोग करने का एक उदाहरण

एक समाधान खोजने के प्रारंभिक चरण में, जब पंक्तियों में नि: शुल्क पदों की संख्या महत्वपूर्ण नहीं होती है, तो नि: शुल्क पंक्ति के सूचकांक, या इस पंक्ति में स्थिति के सूचकांक का चुनाव घातक नहीं होता है। हालांकि, अंतिम चरण में, जब कुछ पंक्तियों में मुफ्त पदों की संख्या 1 या 2 है, तो इस मामले में, आपको एक अलग चयन एल्गोरिदम चुनना चाहिए। इस स्तर पर, यादृच्छिक चयन एल्गोरिदम रैंडसेट और रैंडसेट और रैंड एंड रैंड अब काम नहीं करेगा।

यादृच्छिक चयन एल्गोरिदम काम नहीं करेगा इसका कारण निम्नलिखित सरल उदाहरण द्वारा समझाया जा सकता है। समस्या को हल करने के कुछ चरणों में, n के एक मनमाने मूल्य के लिए, शेष पंक्तियों में I ₁ , i ₂ , ..., i _kरिक्त पदों की संख्या (कोष्ठक में इंगित) है: i ₁ (1), i ₂ (2), i ₃ (4), i ₄ (5), i ₅ (3), i ₆ (4) , आदि। यदि आप अनियमित रूप से किसी भी पंक्ति का चयन करते हैं, लेकिन पंक्ति i _{1 नहीं है} , जिसमें केवल एक मुफ़्त स्थिति है, तो यह जोखिम की स्थिति पैदा कर सकता है जब चयनित पंक्ति में रानी की स्थिति से संबंधित विकर्ण निषेध पंक्ति में एकमात्र मुक्त स्थिति को बंद कर सकता है। i ₁ , जो एक ठहराव के समाधान का नेतृत्व करेगा। सभी पंक्तियों में से I ₁ , i ₂ , ..., i _kरो इंडेक्स की पसंद के लिए सबसे कमजोर और संवेदनशील पंक्ति I _{1 है} । ऐसी स्थितियों में, आपको पहले उस पंक्ति का चयन करना चाहिए जिसकी स्थिति सबसे महत्वपूर्ण है और समस्या को हल करने के लिए जोखिम पैदा करता है। इसलिए, समस्या को हल करने के अंतिम चरण में, प्रत्येक चरण पर न्यूनतम जोखिम के एक सरल एल्गोरिथ्म के आधार पर लाइन की स्थिति चुनना आवश्यक है।

स्पष्टता के लिए, आइए, उदाहरण के रूप में, 100 x 100 मैट्रिक्स के लिए , 88 वें चरण के बाद कुछ वास्तविक समाधान के निर्माण में अंतिम चरण पर विचार करें। कार्य पूरा होने तक, 12 नि: शुल्क लाइनें बनी रहीं, जिनमें से प्रत्येक के लिए नि: शुल्क पदों की संख्या पाई गई थी (मुक्त पदों की संख्या के क्रम में लाइनों को क्रमबद्ध किया गया है):चरण -89 - 25 (1), 12 (2), 22 (2), 82 (2), 88 (2), 7 (3), 64 (3), 3 (4), 76 (4), 91 (४), ४ (५), ९ ६ (५) - एक मुक्त रेखा के सूचकांक को दर्शाता है, और कोष्ठक में - इस पंक्ति में मुक्त पदों की संख्या। न्यूनतम जोखिम नियम के अनुसार, समस्या को हल करने के 89 वें चरण में, पंक्ति 25 का चयन किया जाता है और यह एक मुक्त स्थिति है। रिकाउंट के परिणामस्वरूप, हमारे पास 11 नि: शुल्क लाइनें बची हैं: चरण -90 - 7 (2), 12 (2), 22 (2), 82 (2), 88 (2), 3 (3), 64 (3), 76 (3), 4 (4), 91 (4), 96 (4)।जैसा कि आप देख सकते हैं, पहले पांच लाइनों में मुक्त पदों की संख्या समान और 2 के बराबर है। इसलिए, पहली तीन पंक्तियों में से एक का सूचकांक बेतरतीब ढंग से चुना गया है। इस मामले में, 12 वीं पंक्ति का चयन किया गया था और इस पंक्ति में शेष दो की स्थिति, जिससे न्यूनतम क्षति होती है। इस प्रकार, समाधान के गठन के 91 वें चरण में, हमारे पास 10 मुफ्त लाइनें हैं: चरण -91 - 22 (1), 3 (2), 7 (2), 82 (2), 88 (2), 64 (3) 76 (3), 91 (3), 4 (4), 96 (4) । इस चरण में, लाइन 22 का चयन किया गया है और यह एक मुक्त स्थिति है। इसी तरह से जारी रखते हुए, निर्णयों के निम्नलिखित अनुक्रम का गठन किया गया था (तालिका 1)। चयनित पंक्तियों के सूचकांक बोल्ड में दिखाए गए हैं।

इस विशेष उदाहरण में, 12 में से 11 मामलों में, ऐसी स्थिति थी जब शेष मुक्त लाइनों की सूची में कम से कम एक पंक्ति थी जिसमें केवल एक मुक्त स्थिति बनी हुई थी। यदि हमने न्यूनतम जोखिम नियम का उपयोग नहीं किया, तो हम अंत तक नहीं पहुंच पाएंगे। चूंकि एक फ्री लाइन के एक इंडेक्स को चुनने में एक "गलत चाल", यह सबसे अधिक संभावना है कि केवल एक ही मुफ्त स्थिति को नष्ट कर देगा जो कि शेष फ्री लाइनों में से एक था। यही कारण है कि जब पूर्ण समाधान प्राप्त करने के लिए केवल रैंडसेट x रैंडसेट या रैंड एक्स रैंड एल्गोरिथ्म का उपयोग किया जाता है, तो समाधान एक मृत अंत में जाता है।
यह ध्यान दिया जाना चाहिए कि न्यूनतम जोखिम एल्गोरिथ्म का एक सरल रोजमर्रा का अर्थ है, और अक्सर निर्णय लेने में उपयोग किया जाता है। उदाहरण के लिए, सबसे पहले डॉक्टर उस मरीज को संचालित करता है जिसकी स्थिति जीवन के लिए सबसे महत्वपूर्ण है, इसी तरह, किसान, एक गंभीर सूखे के दौरान, फसल को बचाने की कोशिश कर रहा है, सबसे पहले उन क्षेत्रों को पानी पिलाया जो सबसे महत्वपूर्ण स्थिति में हैं ...

7. एल्गोरिथ्म की दक्षता का विश्लेषण

N के विभिन्न मूल्यों के लिए एल्गोरिथ्म की दक्षता का मूल्यांकन करने के लिए, एक काफी लंबा (कुल समय के संदर्भ में) कम्प्यूटेशनल प्रयोग किया गया था। प्रारंभ में, एन के मनमाने मूल्य के लिए समाधान nQueens Problem के सरणियों को उत्पन्न करने के लिए एक काफी तेज़ एल्गोरिथम विकसित किया गया था। फिर, इस कार्यक्रम के आधार पर, एन मूल्यों की एक मूल सूची के लिए समाधान के बड़े नमूने बनाए गए थे। क्रमशः n के विभिन्न मूल्यों के लिए nQueens समस्या के समाधान के प्राप्त नमूनों के आकार बराबर थे: (10) - 1000, (20, 30, ..., 90, 100, 200, 300, 500, 800, 1000, 3000, 5000, 10,000 / -) -10000, (30000, 50000, 80000) - 5000, (105, 3 * 105) - 3000, (5 * 105, 8 * 105, 106) - 1000, (3 * 106) - 300, ( 5 * 106) - 200, (10 * 106) - 100, (30 * 106) - 50, (50 * 106) - 30, (80 * 106, 100 * 106) - 20। यहां, कोष्ठक में, n मानों की एक सूची इंगित की गई है, और एक डबल डैश प्राप्त किए गए समाधानों के नमूने के आकार को इंगित करता है।उसके बाद, समाधान के प्रत्येक नमूने के आधार पर मनमाने आकार की यादृच्छिक रचनाएं बनाई गईं। उदाहरण के लिए, n = 1000 के प्रत्येक 10,000 समाधानों के लिए, मनमाने आकार के 100 यादृच्छिक रचनाएं बनाई गईं। परिणाम एक मिलियन गीतों का एक नमूना था। चूँकि एक मौजूदा समाधान के आधार पर बनाई गई एक मनमाने आकार की किसी भी रचना को पूर्ण समाधान तक कम से कम एक बार पूरा किया जा सकता है, इसलिए कार्य प्रत्येक नमूने को n- क्वींस कम्प्लीशन समस्या समाधान एल्गोरिथ्म पर आधारित पूर्ण समाधान के लिए उत्पन्न नमूने से पूरा करना था। । चूँकि प्रत्येक कदम पर विचाराधीन एल्गोरिथ्म में चेसबोर्ड पर रानी की सही नियुक्ति की जाँच की जाती है, यहाँ, सिद्धांत रूप में, वे नहीं हो सकते हैंसमाधानों के प्रत्येक नमूने के आधार पर मनमाने आकार की यादृच्छिक रचनाएँ बनाई गईं। उदाहरण के लिए, n = 1000 के प्रत्येक 10,000 समाधानों के लिए, मनमाने आकार के 100 यादृच्छिक रचनाएं बनाई गईं। परिणाम एक मिलियन गीतों का एक नमूना था। चूँकि एक मौजूदा समाधान के आधार पर बनाई गई एक मनमाने आकार की किसी भी रचना को पूर्ण समाधान तक कम से कम एक बार पूरा किया जा सकता है, इसलिए कार्य प्रत्येक नमूने को n- क्वींस कम्प्लीशन समस्या समाधान एल्गोरिथ्म पर आधारित पूर्ण समाधान के लिए उत्पन्न नमूने से पूरा करना था। । चूँकि प्रत्येक कदम पर विचाराधीन एल्गोरिथ्म में चेसबोर्ड पर रानी की सही नियुक्ति की जाँच की जाती है, यहाँ, सिद्धांत रूप में, वे नहीं हो सकते हैंसमाधानों के प्रत्येक नमूने के आधार पर मनमाने आकार की यादृच्छिक रचनाएँ बनाई गईं। उदाहरण के लिए, n = 1000 के प्रत्येक 10,000 समाधानों के लिए, मनमाने आकार के 100 यादृच्छिक रचनाएं बनाई गईं। परिणाम एक मिलियन गीतों का एक नमूना था। चूँकि एक मौजूदा समाधान के आधार पर बनाई गई एक मनमाने आकार की किसी भी रचना को पूर्ण समाधान तक कम से कम एक बार पूरा किया जा सकता है, इसलिए कार्य प्रत्येक नमूने को n- क्वींस कम्प्लीशन समस्या समाधान एल्गोरिथ्म पर आधारित पूर्ण समाधान के लिए उत्पन्न नमूने से पूरा करना था। । चूँकि प्रत्येक कदम पर विचाराधीन एल्गोरिथ्म में चेसबोर्ड पर रानी की सही नियुक्ति की जाँच की जाती है, यहाँ, सिद्धांत रूप में, वे नहीं हो सकते हैंमनमाने आकार की 100 यादृच्छिक रचनाएँ बनाई गईं। परिणाम एक मिलियन गीतों का एक नमूना था। चूँकि किसी मौजूदा समाधान के आधार पर बनाई गई एक मनमाने आकार की किसी भी रचना को पूर्ण समाधान तक कम से कम एक बार पूरा किया जा सकता है, इसलिए यह कार्य था कि उत्पन्न रचना से प्रत्येक रचना को n- क्वींस कम्प्लीशन प्रॉब्लम सॉल्यूशन एल्गोरिथ्म के आधार पर पूर्ण समाधान से पूरा करना था। । चूँकि प्रत्येक कदम पर विचाराधीन एल्गोरिथ्म में चेसबोर्ड पर रानी की सही नियुक्ति की जाँच की जाती है, यहाँ, सिद्धांत रूप में, वे नहीं हो सकते हैंमनमाने आकार की 100 यादृच्छिक रचनाएँ बनाई गईं। परिणाम एक मिलियन गीतों का एक नमूना था। चूँकि एक मौजूदा समाधान के आधार पर बनाई गई एक मनमाने आकार की किसी भी रचना को पूर्ण समाधान तक कम से कम एक बार पूरा किया जा सकता है, इसलिए कार्य प्रत्येक नमूने को n- क्वींस कम्प्लीशन समस्या समाधान एल्गोरिथ्म पर आधारित पूर्ण समाधान के लिए उत्पन्न नमूने से पूरा करना था। । चूँकि प्रत्येक कदम पर विचाराधीन एल्गोरिथ्म में चेसबोर्ड पर रानी की सही नियुक्ति की जाँच की जाती है, यहाँ, सिद्धांत रूप में, वे नहीं हो सकते हैंतब कार्य प्रत्येक नमूने को एन-क्वींस कंप्लीशन प्रॉब्लम सॉल्यूशन एल्गोरिदम के आधार पर पूर्ण समाधान के लिए तैयार करना था। चूँकि प्रत्येक कदम पर विचाराधीन एल्गोरिथ्म में चेसबोर्ड पर रानी की सही नियुक्ति की जाँच की जाती है, यहाँ, सिद्धांत रूप में, वे नहीं हो सकते हैंतब कार्य प्रत्येक नमूने को एन-क्वींस कंप्लीशन प्रॉब्लम सॉल्यूशन एल्गोरिदम के आधार पर पूर्ण समाधान के लिए तैयार करना था। चूँकि प्रत्येक कदम पर विचाराधीन एल्गोरिथ्म में चेसबोर्ड पर रानी की सही नियुक्ति की जाँच की जाती है, यहाँ, सिद्धांत रूप में, वे नहीं हो सकते हैंगलत सकारात्मक निर्णय (यानी गलत निर्णय जिन्हें हम गलती से सही मानते हैं)। हालांकि, गलत नकारात्मक समाधान हो सकते हैं - इस घटना में कि मौजूदा समाधान के आधार पर बनाई गई कोई भी रचना कार्यक्रम द्वारा पूरी नहीं होती है जब तक कि समाधान पूरा नहीं होता है (हालांकि हम जानते हैं कि सभी रचनाओं का एक समाधान है)। इस तरह के n मानों की एक विस्तृत श्रृंखला में एक कम्प्यूटेशनल प्रयोग को अंजाम देते हुए, हम खुद को निम्नलिखित लक्ष्य

निर्धारित करते हैं : क) एल्गोरिथ्म की समय जटिलता निर्धारित करने के लिए,

ख) n,

c के विभिन्न मूल्यों के लिए दिखाई देने वाले गलत नकारात्मक समाधानों की संभावना निर्धारित करने के लिए ) जिसके साथ बैक ट्रैकिंग प्रक्रिया का उपयोग किया जाता है। n के विभिन्न मूल्य।

इस तरह के कम्प्यूटेशनल प्रयोग के परिणाम तालिका 2 में प्रस्तुत किए गए हैं।

प्राप्त परिणामों के आधार पर सामान्य निष्कर्ष निकाला जा सकता है:

ए) एल्गोरिथ्म जल्दी से पर्याप्त काम करता है। उदाहरण के लिए, एक मिलियन कंप्यूटिंग प्रयोगों के आधार पर प्राप्त 1000 x 1000 आकार के एक बिसात के लिए एक मनमाना रचना का औसत संकलन समय 0.062157 सेकंड है। इसका मतलब यह है कि यदि रचना में समाधान है, तो "एंटर" कुंजी दबाने के तुरंत बाद मिल जाएगा । एक मनमाना रचना का औसत संकलन समय, n के सभी मूल्यों के लिए , 7 से 30,000 की सीमा में, एक सेकंड से अधिक नहीं होता है।

बी) प्रत्येक नमूने में, लगभग 10% रचनाएं होती हैं, जिन्हें पूरा करने के लिए बहुत अधिक समय की आवश्यकता होती है। इस तरह की रचनाएं वितरण हिस्टोग्राम में एक लंबी दाएं पूंछ बनाती हैं। यदि हम इन 10% रचनाओं को बाहर करते हैं और शेष 90% समाधानों के लिए गणना करते हैं, तो गणना समय ( t90 _{माध्य} ) बहुत कम होगा। उदाहरण के लिए, 1000 x 1000 शतरंज की बिसात के लिए , औसत गिनती का समय 0.027727 सेकंड होगा, जो पूरे नमूने से प्राप्त औसत समय से 2.24 गुना कम है।

ग) मान n ) 800 के लिए , रचनाओं के नमूने में वे थे जो एक पूर्ण समाधान तक पूरा नहीं किए जा सकते थे। यह झूठी नकारात्मक हैसमाधान। कार्यक्रम में निर्दिष्ट सीमा के भीतर, बैक ट्रैकिंग प्रक्रिया को 1000 बार करने की अनुमति देता है , एल्गोरिथ्म इन रचनाओं को पूरा करने में विफल रहा। उन्हें गलती से नकारात्मक रचनाओं के रूप में वर्गीकृत किया गया था, अर्थात्। जिनका कोई हल नहीं है। इस तरह के गलत नकारात्मक समाधानों की संख्या नगण्य है, और नमूने में उनकी हिस्सेदारी 0.0001 से कम है। इसके अलावा, जैसे-जैसे n बढ़ता है , गलत नकारात्मक समाधानों का अनुपात घटता जाता है। N > 800 के सभी मूल्यों के लिए , कम्प्यूटेशनल प्रयोगों की इस श्रृंखला में, झूठी नकारात्मक समाधान का एक भी मामला नहीं था । हालांकि, यह स्पष्ट है कि यदि नमूना आकार कई बार बढ़ा दिया जाता है, तो झूठी नकारात्मक की उपस्थिति की संभावना को बाहर नहीं किया जाता हैसमाधान, हालांकि इस तरह की घटना की संभावना बहुत कम संख्या होगी।

एल्गोरिथ्म की समय जटिलता । चित्र 7, n के विभिन्न मूल्यों के लिए यादृच्छिक रचनाओं के औसत उठान समय में परिवर्तनों का एक ग्राफ दिखाता है ।


अंजीर। 7. निर्णय मैट्रिक्स के आकार ( n ) पर यादृच्छिक रचनाओं के औसत पिकिंग समय ( t ) की निर्भरता । N के मान का दशमलव लघुगणक एब्सिस्सा अक्ष पर प्लॉट किया जाता है , और लॉगरिथम, औसत गिनती समय के 1000 गुना बढ़ाकर, ऑर्डिनेट अक्ष पर प्लॉट किया जाता है। स्पष्टता के लिए, आंकड़ा चतुर्भुज के विकर्ण की बिंदीदार रेखा को भी दर्शाता है। यह देखा जा सकता है कि पिकिंग समय n में वृद्धि के साथ रैखिक रूप से बढ़ता है। N की पूरी रेंज 50 से 10 से ^{8 तक}

गिनती के समय के प्रायोगिक मूल्य एक सीधी रेखा बनाते हैं, जिसका काफी उच्च सहसंबंध होता है ( R = 0.9998 ) का वर्णन रेखीय प्रतिगमन समीकरण

लॉग (1000 * t) = - 0.628927 + 0.781568 * लॉग से होता है (n)

सामान्य प्रवृत्ति से थोड़ा सा विचलन केवल n = ( मान) के लिए विशिष्ट है। 10, ... 49) , जो इस तथ्य के कारण है कि समस्या को हल करने के लिए गणना का केवल पांचवां ब्लॉक इस सीमा में उपयोग किया जाता है, जिनमें से एल्गोरिथ्म पहले और तीसरे ब्लॉकों के एल्गोरिदम के संचालन से काफी भिन्न होता है। परिणामी निर्भरता में, रैखिक गुणांक ( 0.781568)) एकता से कम है, जो इस तथ्य की ओर जाता है कि एन के बढ़ते मूल्य के साथ, प्रतिगमन रेखा और चतुर्थांश विचलन के विकर्ण। प्रारंभिक समय के बजाय इस तरह की विसंगति का कारण स्पष्ट रूप से समझाने के लिए, हम उस औसत समय पर विचार करते हैं जो एक पंक्ति में एक रानी के स्थान के लिए आवश्यक है, अर्थात्। औसत गिनती के समय को n से विभाजित करें । हम ऐसे संकेतक को कम समय कहते हैं । जाहिर है, अगर कम समय n बढ़ने के साथ नहीं बदलता है , तो ऐसा समाधान रैखिक होगा ( O (n) )। चित्रा 8, जहां भी समय, के लघुगणक की एक साजिश के रूप में देखा


अंजीर। 8 औसत समय निर्भरता ( टी _{पंक्ति}), जो कि समाधान मैट्रिक्स के आकार ( n ) से रानी को एक मनमानी लाइन पर स्थित होना आवश्यक है ।

( tRow ), समाधान मैट्रिक्स के आकार के लघुगणक से 10 ⁶ गुना बढ़ा , n की सीमा में 50 से 10 ^{8 तक} , घटे हुए समय के साथ n कम होता जाता है । यदि n = 50 के लिए कम समय 10.7146 * 10 ^-6 सेकंड है, तो n = 10 ^{8 के} लिए संगत समय 21 गुना कम है और 0.5084 * 10 ^{-6 है}सेकंड। एल्गोरिथ्म का ऐसा व्यवहार, पहली नज़र में, गलत लगता है, क्योंकि कोई उद्देश्य कारण नहीं हैं कि एल्गोरिथ्म इसे बड़े मूल्यों के लिए n के छोटे मूल्यों के लिए धीमा क्यों समझेगा। हालांकि, कोई त्रुटि नहीं है, और यह इस एल्गोरिथम का एक उद्देश्य संपत्ति है। यह इस तथ्य के कारण है कि यह एल्गोरिथ्म तीन एल्गोरिदम की एक रचना है जो विभिन्न गति से संचालित होता है। इसके अलावा, इनमें से प्रत्येक एल्गोरिदम द्वारा संसाधित लाइनों की संख्या एन के बढ़ते मूल्य के साथ बदलती है। यह इस कारण से है कि मतगणना का समय मूल्यों की प्रारंभिक श्रेणी n = (10, 20, 30, 40) में बढ़ रहा है, क्योंकि इस छोटे से क्षेत्र में सभी गणना केवल प्रक्रियाओं के पांचवें ब्लॉक के आधार पर की जाती है, जो बहुत कुशलता से काम करती है, लेकिन उतनी तेजी से नहीं प्रक्रियाओं का पहला ब्लॉक। इस प्रकार, यह देखते हुए कि रानी को एक पंक्ति में रखने के लिए आवश्यक गणना समय,शतरंज के बढ़ते आकार के साथ घट जाती है, इस एल्गोरिथ्म की समय जटिलता को घटते - रैखिक कहा जा सकता है।

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


चित्र दिखाया गया है। 9. नमूना समाधान जो प्रक्रिया में वापस ट्रैकिंग इस्तेमाल कभी नहीं का प्रतिशत

ग्राफ कि शो कैसे बीटी प्रक्रिया के बिना समाधान के अनुपात ( शून्य वापस ट्रैकिंग ) की बढ़ती मूल्यों के साथ n। यह देखा जा सकता है कि मानों की सीमा में n = (7, ..., 100000) , बीटी प्रक्रिया का उपयोग नहीं किए जाने वाले समाधानों की संख्या 35% से अधिक है। इसके अलावा, मानों की सीमा में n = (320, ..., 22500) , ऐसे मामलों की संख्या 50% से अधिक है। सबसे प्रभावी परिणाम 5000 x 5000 के आकार के साथ एक शतरंजबोर्ड के लिए प्राप्त किए गए , जहां, 10,000 रचनाओं के नमूने में , 61.92% मामलों में गैर-नियतात्मक समस्या का "निर्धारक" समाधान किया गया था, क्योंकि 61.92% पर बीटी प्रक्रियामामलों का कभी उपयोग नहीं किया गया। शेष समाधानों में, 21.87% मामलों में, बीटी प्रक्रिया का उपयोग 1 बार किया गया था, 9.07% मामलों में - 2 बार, और 3.77% मामलों में - 3 बार। कुल मिलाकर, यह 96.63% मामलों में है। तथ्य यह है कि मूल्य n = 5000 के बाद , बीटी प्रक्रिया का उपयोग किए बिना कॉन्फ़िगरेशन समस्या को हल करने के मामलों की संख्या धीरे-धीरे कम हो रही है, बेसलेवेल 2 और बेसलवेल 3 के सीमा मूल्यों का चयन करने के लिए चयनित मॉडल के साथ जुड़ा हुआ है । आप इन मापदंडों को बदल सकते हैं और बीटी प्रक्रिया का उपयोग किए बिना समाधानों की संख्या में वृद्धि प्राप्त कर सकते हैं। हालांकि, इससे गणना समय में वृद्धि होगी, चूंकि एल्गोरिथ्म के संचालन में पांचवें ब्लॉक की भागीदारी बढ़ जाएगी।

समय लेने के वितरण का हिस्टोग्राम । चित्रा 10 में, n = 1000 के मान के लिएएक मिलियन समाधानों के लिए समय लेने के वितरण का हिस्टोग्राम प्रस्तुत किया गया है। वितरण हिस्टोग्राम का काफी सामान्य दृश्य (जो संभवतः सबसे ऊंची इमारतों की रात सिल्हूट जैसा दिखता है) लंबाई या अंतराल की संख्या के चयन में एक त्रुटि के साथ जुड़ा नहीं है। यह इस एल्गोरिथम की एक प्राकृतिक संपत्ति है। समझने के लिए,


अंजीर। 10. मनमाने आकार की रचनाओं के संकलन के समय का एक हिस्टोग्राम। ( n = 1000 ; नमूना आकार = 1,000,000 )

हिस्टोग्राम का यह रूप क्यों है, समान आकार वाले रचनाओं के लिए चुनने के समय के वितरण पर विचार करें। इसके लिए, एक उदाहरण के रूप में, प्रारंभिक नमूने से हम उन सभी रचनाओं का चयन करेंगे, जिनका आकार 800 है। दस लाख के नमूने में ऐसी 998 रचनाएँ थीं। चित्रा 11 इस नमूने के लिए गिनती के समय के वितरण का एक हिस्टोग्राम दिखाता है। यह आंकड़ा से देखा जा सकता है कि वितरण में छह अलग-अलग हिस्टोग्राम होते हैं, जिनमें आकार में कमी होती है।


अंजीर। 11. एक ही आकार (k = 800) की रचनाओं के संकलन समय का एक हिस्टोग्राम। ( n = 1000 ; नमूना आकार = 998 )

कारण क्यों 998 रचनाओं का संकलन समय, जिनमें से प्रत्येक में 800 क्वीन्स को यादृच्छिक रूप से वितरित किया जाता है, को 6 समूहों में "क्लस्टर" किया जाता है, क्योंकि बैक ट्रैकिंग प्रक्रिया का उपयोग किया जाता है। आकृति में पहला हिस्टोग्राम, अधिकतम नमूना आकार के साथ, उन समाधानों को चुनना है जहां बीटी प्रक्रिया का उपयोग कभी नहीं किया गया है। यह सबसे तेज़ समाधानों का एक समूह है। दूसरा हिस्टोग्राम, जो पहले की तुलना में आकार में काफी छोटा है, वे समाधान हैं जिनमें बीटी प्रक्रिया का उपयोग केवल एक बार किया गया था। इसलिए, इस समूह में निर्णय का समय पहले की तुलना में थोड़ा लंबा है। तदनुसार, तीसरे समूह में, बीटी प्रक्रिया का उपयोग दो बार किया गया था, चौथे में - तीन बार, आदि, अर्थात्। जिन निर्णयों में बार बार बीटी प्रक्रिया का उपयोग किया गया था, वे लंबे समय तक किए गए थे। इस तरह के समाधान वांछित वितरण की लंबी दाहिनी पूंछ बनाते हैं।

गलत नकारात्मक समाधान । अगर हम n के मनमाने मूल्य के लिए सभी संभव रचनाओं को विभाजित करते हैंसकारात्मक और नकारात्मक के लिए, फिर सकारात्मक रचनाओं के बीच वे हैं जिन्हें यह एल्गोरिथम नकारात्मक के रूप में वर्गीकृत कर सकता है। यह इस तथ्य के कारण है कि, खोज मापदंडों द्वारा निर्धारित सीमा के भीतर, एल्गोरिथ्म ऐसी रचनाओं को पूरा करने का सही तरीका नहीं खोज सकता है। जैसा कि प्रायोगिक परिणाम (तालिका 2) दिखाते हैं, ऐसे मामलों की संख्या नमूना आकार के 0.0001 से अधिक नहीं होती है, और इस त्रुटि का मान बढ़ते हुए एन के साथ घटता है । इसके अलावा, n> 800 के सभी मूल्यों के लिए , झूठी नकारात्मक समाधान का एक भी मामला नहीं था । यहां तक ​​कि n = 1000 के लिए नमूना आकार को एक मिलियन तक बढ़ाने के परिणामस्वरूप झूठी नकारात्मक नहीं हुईसमाधान। परिणाम हमें समस्या को हल करने के लिए निम्नलिखित नियम तैयार करने की अनुमति देता है: “ k रानियों की कोई भी यादृच्छिक रचना जो आकार nxn के अनियंत्रित बिसात पर लगातार वितरित की जाती है, जब तक कि एक पूर्ण समाधान नहीं किया जाता है, या यह तय किया जाएगा कि यह रचना नकारात्मक है और नहीं पूरा होना। इस तरह के निर्णय लेने की संभावना 0.0001 से अधिक नहीं है । जैसे ही शतरंज की बिसात का आकार बढ़ता है, गलत निर्णय लेने की संभावना कम हो जाती है। एल्गोरिथ्म का समय जटिलता रैखिक है। "

8. निष्कर्ष

1. एक एल्गोरिथ्म प्रस्तुत किया जाता है, जो कि रेखीय समय में, संपूर्ण सेट समस्या को हल करने के लिए, k रानियों की एक यादृच्छिक रचना के पूर्ण समाधान तक, लगातार मनमाने आकार के nxn के बिसात पर वितरित किया जाता है। इसके अलावा, k रानियों (1 for k <n ) की किसी भी रचना के लिए, यदि कोई हो, या कोई निर्णय लिया जाता है, तो यह समाधान दिया जाता है कि यह रचना पूरी नहीं हो सकती। इस तरह के निर्णय लेने में त्रुटि की संभावना 0.0001 से अधिक नहीं होती है, और यह मूल्य शतरंज के आकार में वृद्धि के साथ घटता है।

2. इस एल्गोरिथ्म का संचालन दो महत्वपूर्ण नियमों के उपयोग पर आधारित है:

a) समस्या को हल करने के अंतिम चरण में, सभी शेष नि: शुल्क लाइनों से, एक का चयन किया जाता है, जिसके लिए मुफ्त पदों की संख्या न्यूनतम ( न्यूनतम जोखिम नियम ) है। यह कुछ शेष लाइनों में अंतिम रिक्त पदों को बाहर करने की संभावना से जुड़े जोखिमों को कम करता है।

ख) प्रश्न में लाइन में सभी रिक्त पदों के लिए, उस स्थिति का चयन किया जाता है जो शेष मुक्त लाइनों ( न्यूनतम क्षति नियम ) में मुक्त पदों पर कम से कम नुकसान पहुंचाता है । " न्यूनतम क्षति " से अभिप्राय ऐसी पंक्ति में ऐसी स्थिति का चयन करना है जो सभी शेष मुक्त रेखाओं में कम से कम मुक्त पदों को शामिल न करे।

3. यह स्थापित किया गया था कि इस एल्गोरिथ्म के संचालन के परिणामस्वरूप, रानी को एक पंक्ति में रखने के लिए आवश्यक औसत समय n के मूल्य में वृद्धि के साथ कम हो जाता है। मामले में एक पंक्ति पर रानी को रखने के लिए आवश्यक औसत समय जब n 10 है तो केस n = 50 के लिए संबंधित समय की तुलना में 21 गुना कम है।

4. यह पाया गया कि मूल्यों की श्रेणी में n = (7, ..., 100000) समाधानों की संख्या जिसमें बैक ट्रैकिंग प्रक्रिया का उपयोग कभी नहीं किया गया है, 35% से अधिक है। इसके अलावा, मानों की सीमा में n = (320, ..., 22500) , ऐसे मामलों की संख्या 50% से अधिक है, जो इस एल्गोरिथ्म की उच्च दक्षता को इंगित करता है।

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

6. दो यादृच्छिक चयन विधियों के तुलनात्मक विश्लेषण के परिणाम, जिन्हें रैंडसेट और रैंडसेट और रैंड एंड रैंड कहा जाता है, प्रस्तुत किया जाता है । रैंडसेट और रैंडसेट एल्गोरिथ्म तेज पाया गया है, लेकिन असभ्य है। इसलिए, दूसरे मूल स्तर तक पहुँचने पर इसका उपयोग सीमित है। उसके बाद, रैंड एंड रैंड एल्गोरिथ्म का उपयोग किया जाता है, जो इतना तेज़ नहीं है, लेकिन अधिक कुशलता से शतरंज की बिसात पर जगह बनाता है।

7. n- क्वींस समस्या समाधान की शुद्धता की पुष्टि के लिए एक प्रभावी एल्गोरिथ्म दिया गया है। यह कार्यक्रम मनमाने आकार के यादृच्छिक रचना की शुद्धता को सत्यापित करने के लिए भी बनाया गया है। कार्यक्रम काफी तेजी से काम करता है। उदाहरण के लिए, 5 मिलियन पदों वाले समाधान को मान्य करने के लिए आवश्यक समय 0.85 सेकंड है।

9. टिप्पणियाँ

1. जैसा कि लेख की शुरुआत में संकेत दिया गया था, अध्ययन 7 से 100 मिलियन तक एन मान की सीमा में आयोजित किए गए थे। हालांकि, कार्यक्रम को एक अरब तक के एन मूल्यों की एक विस्तृत श्रृंखला में परीक्षण किया गया था। सच है, बाद के मामले में, कार्यक्रम को थोड़ा अनुकूलित किया जाना था, बड़े आकार को देखते हुए। इसलिए, यदि रैम का आकार अनुमति देता है, तो एन के बड़े मूल्यों के लिए गणना करना संभव है।

2. बेसलाइन संकेतक, साथ ही साथ विभिन्न स्तरों पर पुनरावृत्ति की संख्या के सीमा मूल्यों को पूरे शोध रेंज के भीतर समस्या को हल करने के लिए अनुकूलित किया गया था। उन्हें एक छोटी सीमा के भीतर बदला जा सकता है और गिनती के समय को कम किया जा सकता है। यह महत्वपूर्ण है कि गलत नकारात्मक समाधानों की हिस्सेदारी न बढ़े।

3. इस लेख में, मैंने एल्गोरिथ्म कितनी तेजी से काम करता है इसका मूल्यांकन करने के लिए समय की एक माप के रूप में Enter कुंजी प्रेस समय का उपयोग किया। यदि कुंजी दबाने के तुरंत बाद परिणाम दिखाई देता है, तो उपयोगकर्ता धारणा के स्तर पर ऐसा लगता है कि कार्यक्रम "बहुत" तेजी से काम करता है। कोई फर्क नहीं पड़ता कि एल्गोरिथ्म कितनी तेजी से काम करता है, परिणाम कुंजी पूरा होने तक स्क्रीन पर दिखाई नहीं देगा। इसलिए, यह मुझे प्रतीत हुआ कि समय का ऐसा सशर्त माप विभिन्न एल्गोरिदम की गति की कड़ाई से तुलना नहीं करने के लिए एक दहलीज स्तर के रूप में काम कर सकता है।

4. दार्शनिक ... अध्ययन के दौरान, गैर-निर्धारक समस्याओं के समाधान से संबंधित प्रकाशनों की एक बड़ी संख्या पर विचार किया गया था। ज्यादातर मामलों में, ये ऐसे कार्य थे जिनमें दिए गए प्रतिबंधों की शर्तों के तहत राज्यों के एक बड़े स्थान पर चुनाव करना आवश्यक था। उनकी तुलना करते हुए, यह जानना दिलचस्प था कि मानक गणितीय दृष्टिकोण का उपयोग करके ऐसी समस्याओं को हल करने में कितना आगे बढ़ सकता है। मुझे यह आभास हुआ कि केवल परिभाषाओं, नींबूओं के बयान और प्रमेयों के प्रमाण के आधार पर ऐसी समस्याओं को हल करना असंभव है। यह मुझे लगता है कि ऐसी समस्याओं को हल करने के लिए कंप्यूटर सिमुलेशन का उपयोग करके एल्गोरिथम गणित के तरीकों का उपयोग करना आवश्यक है। इस निष्कर्ष की वैधता को प्रदर्शित करने के लिए, एक साधारण उदाहरण के रूप में, मैंने शतरंज की बिसात के लिए तैयार किया, जिसका आकार 10 ⁹ x 10 ⁹ दो समान रचनाओं की रचना है, जिसमें 999,999,482 रानियाँ शामिल हैं। वे लेख की शुरुआत में वर्णित के रूप में तैयार किए जाते हैं और उन्हें .mat प्रारूप में दो फ़ाइलों के रूप में प्रस्तुत किया जाता है। उन्हें इस लिंक (दो परीक्षण फ़ाइलों) पर डाउनलोड किया जा सकता है। फाइलें काफी "भारी" हैं, उनमें से प्रत्येक का आकार लगभग 3.97 जीबी है। 999 997 976 लाइनों में (99.9998% मामलों में) दोनों रचनाओं में रानियों के पद मेल खाते हैं, और केवल मनमानी 1506 लाइनों में रानियों के पदों में अंतर होता है।

कंपोजिशन डेटा को पूर्ण समाधान के लिए, आपको शेष 518 मुफ्त लाइनों में रानियों को सही ढंग से रखने की आवश्यकता है। शेष नि: शुल्क लाइनों में 518 रानियों की व्यवस्था के संभावित तरीकों की संख्या (चयनित पंक्ति में एक मुक्त स्थिति का चयन करने के तरीकों की संख्या को ध्यान में रखते हुए) लगभग 10 ^{1466 है} । इन दो रचनाओं के बीच अंतर केवल इतना है कि उनमें से एक सकारात्मक है और एक पूर्ण समाधान तक पूरा किया जा सकता है, और दूसरी रचना नकारात्मक है - इसे पूर्ण समाधान तक पूरा नहीं किया जा सकता है। प्रश्न: "क्या यह संभव है कि एक कठोर गणितीय दृष्टिकोण के आधार पर (जो कि एल्गोरिथम कम्प्यूटेशनल संचालन को पूरा किए बिना), यह निर्धारित करने के लिए कि इन दोनों में से कौन सी रचना सकारात्मक है?" यदि यह हल करना असंभव है, तो हम मान सकते हैं कि बनाया गया प्रस्ताव विरोधाभास से सिद्ध होता है।

मैं यह नोट करना चाहता हूं कि इस समस्या के कड़ाई से गणितीय समाधान के लिए कोई फर्क नहीं पड़ता है, किसी को शेष मुक्त लाइनों में 518 * 10 ⁹ कोशिकाओं की स्थिति निर्धारित करने की आवश्यकता है। ऐसा करने के लिए, पहले से स्थापित रानियों की प्रत्येक स्थिति पर विचार करना आवश्यक है, और उनमें से लगभग एक अरब प्रतिबंधों को स्थापित करने के लिए हैं जो प्रत्येक स्थापित रानी शेष 518 लाइनों में मुक्त पदों पर लगाती हैं। मुझे "फुलक्रम" नहीं मिला, जो मुझे एल्गोरिथम गणना के बिना, केवल कड़ाई से गणितीय दृष्टिकोण के आधार पर यह काम करने की अनुमति देगा।

मैंने यहाँ केवल दो रचनाओं से मिलकर एक न्यूनतम उदाहरण दिया है। यदि आवश्यक हो, तो ऐसी रचनाओं की संख्या बढ़ाई जा सकती है।

यह ध्यान दिया जाना चाहिए कि प्रस्तावित रेखीय एल्गोरिथ्म के आधार पर, बड़ी रचनाओं के साथ काम करने के लिए थोड़ा अनुकूलित किया गया है, दो टेस्ट रचनाओं में से कौन से कार्य डेस्कटॉप -13 पर पूरा समाधान प्रस्तुत करने से पहले पूरा किया जा सकता है, लगभग 4.5 मिनट (लोडिंग समय को छोड़कर) इनपुट डेटा)।

10. जोड़

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

1. आकार nxm के एक आयताकार "शतरंज" बोर्ड पर n क्वीन्स की व्यवस्था की समस्या पर विचार करें। Denote k = m - n । कुछ समाधान प्राप्त करने दें, और प्रत्येक एन लाइनों में एक रानी स्थित होनी चाहिए। हम उन पदों को बाहर करते हैं जहां रानी आगे के विचार से स्थित हैं। अब प्रत्येक पंक्ति में एम -1 मुक्त स्थिति है। शेष मुक्त पदों के भीतर, हम फिर से एक समाधान पाते हैं। पहले की तरह, हम उन पदों पर और विचार करते हैं जिन्हें दूसरे समाधान की रानियाँ स्थित हैं। अब प्रत्येक पंक्ति में एम -2 मुक्त स्थान हैं। जाहिर है, पहला और दूसरा समाधान किसी भी पंक्ति में उनके पदों में अंतर नहीं करते हैं - वे ऑर्थोगोनल हैं। कश्मीर के विभिन्न मूल्यों के लिए पारस्परिक रूप से ऑर्थोगोनल समाधानों की अधिकतम संख्या निर्धारित करना आवश्यक है। यदि मूल्य k = 0 के लिए n पारस्परिक रूप से ऑर्थोगोनल समाधान पाए जाते हैं, तो रॉयल लैटिन स्क्वायर का निर्माण किया जाएगा।

रिमार्क । ग्रिगोरियन ई (2018) ने दिखाया कि किसी भी एन-क्वींस समस्या समाधान के लिए, एक पूरक समाधान है जो इसके साथ अंतर नहीं करता है। इसका मतलब यह है कि एन के एक मनमाने मूल्य के लिए, एन-क्वींस समस्या के सभी समाधानों के सेट को दो समान आकार के सबसेट में विभाजित किया गया है। दूसरे सबसेट से कोई समाधान पहले उपसमूह से संबंधित समाधान के लिए एक पूरक समाधान है। नियम काफी सरल है, अगर Q1 (i) पहले सेट से एक समाधान है, तो दूसरे उपसमूह से संबंधित पूरक समाधान Q2 (i) सूत्र Q2 (i) = n + 1 - Q1 (i) द्वारा निर्धारित किया जाता है , जहां मैं = (1, ... , एन) । यह नियम है जो इस तथ्य की व्याख्या करता है कि एन-क्वींस समस्या के सभी समाधानों की संख्या, एन के मनमाने मूल्य के लिए, हमेशा एक सम संख्या होती है। (यह नियम हमें शतरंजबोर्ड के एक मनमाने आकार के एन के लिए सभी पूर्ण समाधानों की गणना के लिए समय को आधा करने की अनुमति देता है। यदि हम सभी समाधानों की कुल संख्या 2 * k से निरूपित करते हैं, तो मूल्य k , Q (k) + Q के सभी अनुक्रमों की अनुक्रमिक सूची में सूचकांक के बराबर है। k + 1) = n + 1 )।

2. क्वीन प्रॉब्लम (i, j) को स्थिति में रखने के बाद n-Qeens प्रॉब्लम प्रॉब्लम के शुरुआती फॉर्मूलेशन में, निम्न एक्शन किए जाते हैं:

a) पंक्ति I और कॉलम j की सभी कोशिकाओं को बाहर करें

बी) सेल (i, j) से गुजरने वाले बाएं और दाएं विकर्ण की रेखा पर स्थित सभी कोशिकाओं को बाहर रखा गया है।

हम समस्या के बयान में स्थिति बी) को बदलते हैं। कोशिकाओं को खत्म करने के बजाय, हम सेल स्विचिंग का उपयोग करेंगे। यदि बाएं या दाएं विकर्ण की रेखा पर स्थित सेल स्वतंत्र है, तो हम इसे बंद कर देंगे; यदि सेल बंद है, तो हम इसे खोल देंगे। इससे समाधान खोजने में आसानी होती है। हालांकि, वर्ग मैट्रिक्स nxn के बजाय, हम आकार nx (n - k) के एक आयताकार मैट्रिक्स पर विचार करते हैं। यह आवश्यक है, n के दिए गए मूल्य के लिए, k का अधिकतम मान ज्ञात करने के लिए जिस पर कम से कम तीन ऑर्थोगोनल समाधान प्राप्त किए जा सकते हैं। N के बढ़ते मूल्य के साथ k का मान कैसे बदलेगा?

3. n- क्वींस समस्या समस्या के प्रारंभिक सूत्रीकरण में कुछ शर्तों को बदलें। जब रानी को आकार nxn की एक बिसात पर स्थिति (i, j) में रखा जाता है:

क) पंक्ति I में सभी कोशिकाओं को बाहर करना,

b) यदि इंडेक्स j एक सम संख्या है, तो:

b1) स्तंभ j की सम पंक्तियों में कोशिकाओं को बाहर करें,

b2) हम सेल के माध्यम से गुजरने वाले बाएं और दाएं विकर्णों के साथ प्रतिच्छेद करते हुए भी पंक्तियों में कोशिकाओं को बाहर करते हैं (i, j) ,

ग) यदि इंडेक्स जे एक विषम संख्या है, तो अंक बी 1) और बी 2) विषम पंक्तियों पर स्थित कोशिकाओं के लिए संतुष्ट हैं।

3.1 यह ज्ञात है (Sloane-2016) कि nQueens Problem के सभी समाधानों के मूल्यों की सूची, क्रमशः n = (8, 9, 10, 11, 12, 13, 14, 15, 16) के लिए है (92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512) । समस्या के बयान में, सभी समाधानों की संख्या कैसे बदल जाएगी, विकर्ण अपवादों के लिए मानक स्थिति पैरा बी में बदल जाती है) या पैरा सी)?

3.2 यह ग्रिगोरियन (2018) द्वारा ज्ञात है कि अगर हम सभी समाधानों की एक सूची के निर्माण में निर्णय मैट्रिक्स की विभिन्न कोशिकाओं की भागीदारी की आवृत्ति का निर्धारण करते हैं, तो हम पा सकते हैं कि संबंधित कोशिकाओं के ऊर्ध्वाधर और क्षैतिज समरूपता के रूप में सभी कोशिकाओं के बीच सामंजस्यपूर्ण संबंध हैं। इसका मतलब यह है कि अगर हम मानते हैं कि k <n / 2 है , तो k-th पंक्ति की कोशिकाओं की आवृत्ति पंक्ति n-k + 1 की कोशिकाओं की आवृत्तियों के समान होगी। इसी प्रकार, k-th कॉलम की कोशिकाओं की आवृत्ति कॉलम n-k + 1 की कोशिकाओं की आवृत्तियों के समान होगी। प्रश्न: "ये सौहार्दपूर्ण संबंध कार्य के संदर्भ में कैसे बदलेंगे?"

4. शतरंज के सभी कक्षों को उनके रंग से दो वर्गों में विभाजित किया गया है। ऐसा माना जाता है कि एक रंग सफेद है, दूसरा काला है। दो चेसबोर्ड पर विचार करें और उनमें से एक को दूसरे पर रखें ताकि किनारों को पूरी तरह से मेल खाना। नतीजतन, हमें दो शतरंजों से एक "सैंडविच" मिलता है, जिसमें सफेद और काले रंग की कोशिकाओं का संयोग होता है। कार्य दो बोर्डों पर एक साथ समाधान खोजने के लिए है, निम्नलिखित स्थितियों का अवलोकन:

क) यदि किसी एक बोर्ड पर रानी इंडेक्स (i, j) के साथ एक ब्लैक सेल पर स्थित है, तो:

- दोनों बोर्डों पर, पंक्ति i और कॉलम j पर पाए जाने वाले सभी ब्लैक सेल को बाहर रखा गया है

- दोनों बोर्डों पर सेल (i, j) से गुजरने वाले बाएं और दाएं विकर्णों के साथ स्थित सभी काली कोशिकाओं को बाहर रखा गया है।

b) यदि किसी एक बोर्ड पर रानी इंडेक्स (i, j) के साथ एक सफेद सेल पर स्थित है, तो पैराग्राफ की सभी क्रियाएं a) केवल सफेद कोशिकाओं के लिए की जाती हैं।

5. कल्पना करें कि आकार nxn के एक समाधान मैट्रिक्स में, पंक्तियों को के कोशिकाओं के एक चरण के साथ दाएं या बाएं एक दूसरे के सापेक्ष स्लाइड कर सकते हैं। इसके अलावा, यदि पिछली पंक्ति को स्थानांतरित किया गया था, उदाहरण के लिए, बाईं ओर, तो अगली पंक्ति को दाईं ओर स्थानांतरित किया जाना चाहिए, अर्थात। प्रत्येक अगली पंक्ति को पिछली रेखा के विपरीत दिशा में स्थानांतरित किया जाता है। इस निर्माण के परिणामस्वरूप, हम आकार nx (n + k) का एक आयताकार मैट्रिक्स प्राप्त करते हैं, जहां पंक्ति के अंत से या अंत से प्रत्येक पंक्ति k कोशिकाओं में विचार से बाहर रखा जाएगा। कार्य n के मनमाने मूल्य के लिए k का अधिकतम मान ज्ञात करना है जिसके लिए कम से कम एक समाधान n- क्वींस समस्या है ।
उस समस्या के एक प्रकार पर विचार करें जिसमें एक लाइन से दूसरे के संबंध में ऑफसेट k1 से k2 तक की एक यादृच्छिक संख्या है ।

6. nQueens Problem का एक -आयामी प्रारूपण । मनमाने ढंग से लंबाई के n सेगमेंट्स, 1 से n तक की संख्या वाले, आधे अक्ष पर रखे जाएं। प्रत्येक खंड को मनमाने आकार की n कोशिकाओं में विभाजित करें, और प्रत्येक खंड के भीतर, संख्या कोशिकाओं को 1 से n तक । ऐसी कोशिकाओं को हम खुला कहते हैं। प्रत्येक खंड में एक सेल को बंद करना आवश्यक है, निम्नलिखित प्रतिबंधों को ध्यान में रखते हुए:

a) हम i- वें सेगमेंट से नंबर j के साथ एक ओपन सेल चुन सकते हैं, यदि:

डी 1 (आर) = 0;

डी 2 (टी) = 0;

जहाँ r = n + j - i, t = j + i, D1 और D2 एक आयामी नियंत्रण सरणियाँ हैं जिनमें 2n कोशिकाएँ होती हैं जो पहले शून्य थीं।

बी) इस चयन के बाद, सभी खंडों में नंबर I के साथ खंड I और सेल बंद हो जाएंगे। नियंत्रण सरणियों में संबंधित कोशिकाओं को बंद करना भी आवश्यक है:

डी 1 (आर) = 1;

डी 2 (टी) = 1;

इस सेटिंग में, कार्य मूल एक के समान है। ब्याज की अन्य बाधाओं के साथ इस समस्या का सूत्रीकरण है। उदाहरण के लिए, यदि सूत्रों के बजाय:
r = n + j - i, t = j + i ,,
अन्य संबंधों पर विचार किया जाएगा कि कार्यात्मक रूप से निर्णय मैट्रिक्स के सूचकांकों (i, j) के साथ आर और टी को जोड़ते हैं।

7. गेंदों के साथ एक कलश के आधार पर कार्य का शब्दांकन (पिछले शब्द के समान)। बता दें कि 1 से n तक की संख्या में n मतपेटियां हैं, और प्रत्येक मतपेटी में n गेंदें हैं, जिन्हें 1 से n तक भी गिना जाता है। निम्नलिखित प्रतिबंधों को ध्यान में रखते हुए, प्रत्येक कलश से एक गेंद का चयन करना आवश्यक है:

क) हम i- वें कलश से संख्या j के साथ एक गेंद चुन सकते हैं:

डी 1 (आर) = 0 ,

डी 2 (टी) = 0 ,

जहाँ r = n + j - i, t = j + i, D1 और D2 एक आयामी नियंत्रण सरणियाँ हैं जिनमें 2n कोशिकाएँ होती हैं जो पहले शून्य थीं।

ख) इस पसंद के बाद, सभी j मुक्त मतपेटियों में नंबर j के साथ मतपेटी i और गेंदों को बंद कर दिया जाएगा। नियंत्रण सरणियों में संबंधित कोशिकाओं को बंद करना भी आवश्यक है:

डी 1 (आर) = 1 ,

डी 2 (टी) = 1 ।

इस सेटिंग में, कार्य मूल एक के समान है। पिछले मामले की तरह, इस समस्या का विवरण अन्य शर्तों के साथ है जो निर्णय मैट्रिक्स के सूचकांकों (i, j) के साथ कार्यात्मक रूप से सूचकांकों को r और t से जोड़ते हैं।

8. खेल । आकार nxn की एक बिसात पर विचार करें। चलो रानियों को रंग वापस करते हैं, कुछ रानियों को सफेद रंग, दूसरों को काला करने देते हैं। हम शतरंजबोर्ड की कोशिकाओं में बारी-बारी से सफेद और काले रंग को भी लौटाते हैं, इस तथ्य के आधार पर कि सूचकांक (1, n) के साथ सेल सफेद होना चाहिए। खेल की शुरुआत में सभी कोशिकाओं को स्वतंत्र माना जाता है। सफेद रानियां पहली चाल। खिलाड़ी रानी को एक मनमाना मुक्त सेल में सूचकांकों (i, j) के साथ रखता है। इसे एक सफेद कोशिका होने दें। इस विकल्प के परिणामस्वरूप, पास:

क) पंक्ति की सभी सफेद कोशिकाएँ,

ख) सभी स्तंभों की सफेद कोशिकाएं

ग) सभी सफेद कोशिकाएं जो सेल के माध्यम से गुजरने वाले बाएं और दाएं विकर्ण पर झूठ बोलती हैं (i, j) ।

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

9. यादृच्छिक चयन की स्थिरता पर। रैंडसेट और रैंडसेट मॉडल पर विचार करें।चक्र के पहले चरण में पंक्ति और स्तंभ सूचकांकों के n यादृच्छिक जोड़े की तुलना करने के परिणामस्वरूप , k * n पंक्तियों पर औसतन रानियों को स्थापित करना संभव है । का मान कश्मीर एक निरंतर 0.6 के बराबर माना जा सकता है। इसका मान 0.605701 से n = 10 , और 0.599777, n = 10 ⁶ पर भिन्न होता है , और, n बढ़ने के साथ , इस मान का विचरण कम हो जाता है। ऐसे "कब्ज" का कारण क्या है? पंक्ति के यादृच्छिक चयन और इस पंक्ति में रानी की स्थिति सूचकांक के यादृच्छिक चयन के साथ, 1 से n तक की संख्या के यादृच्छिक क्रम के आधार पर प्राप्त संख्याओं की दो सूचियों के आधार पर, 60% लाइनों पर लगातार (औसतन) कतारों को रखना संभव है?

10. बिसात का आकार बराबर करेंnxn । रैंडसेट और रैंडसेट प्रक्रिया के आधार पर, हम बिसात को शतरंज की बिसात पर रख देते हैं जब तक कि खोज शाखा मृत अंत तक नहीं पहुंच जाती। इस प्रकार k द्वारा प्राप्त रचना की लंबाई को निरूपित करें । यदि n के दिए गए मान के लिए , इस प्रक्रिया को कई बार दोहराएं, और k के मानों के वितरण का एक हिस्टोग्राम का निर्माण करें , तो यह पता चलता है कि वितरण मोड के मूल्य की घटनाओं की आवृत्ति में परिवर्तन इस मूल्य के बाद होने वाली घटनाओं की आवृत्ति में परिवर्तन से भिन्न होता है। यदि, मोडल मूल्य के आधार पर, हिस्टोग्राम को दो भागों में विभाजित किया जाता है, तो बाएं भाग दाएं भाग के साथ मेल नहीं खाएगा। यह पैटर्न एन के किसी भी मूल्य के लिए विशेषता है। क्यों, मोडल मूल्य के माध्यम से रचना की लंबाई के संक्रमण के बाद, घटनाओं की शुरुआत की आवृत्ति एक अलग रूप लेती है? एक घटना से हमारा तात्पर्य है, गतिहीन अवस्था में पहुँचने से पहले, किसी दिए गए आकार की संरचना प्राप्त करना।

साहित्य

1. नावक, एफ। (1850)। ब्रीफचसेल माइट एलन फर । इलस्ट्रेटर ज़िटुंग, 15, 182.

2. जेंट, आईपी, जेफरसन, सी। और कोकिला, पी। (2017)। एन-क्वींस पूरा होने की जटिलता ,
आर्टिफिशियल इंटेलिजेंस रिसर्च जर्नल।, 59, 815-848।

3. सॉसिक, आर।, और गु, जे। (1990)। एन-क्वेंस समस्या के लिए एक बहुपद समय एल्गोरिथ्म । सिग्त बुलेटिन, १ (३), ART-११।

4. रिचर्ड्स, एम। (1997)। बिट पैटर्न और पुनरावृत्ति का उपयोग करके MCPL में एल्गोरिदम का बैकट्रैकिंग ।
टेक। प्रतिनिधि।, कंप्यूटर प्रयोगशाला, कैम्ब्रिज विश्वविद्यालय।

5. एल्गोरिदम डिजाइन में रैंडमाइजेशन के तरीके, एक DIMACS कार्यशाला, प्रिंसटन, न्यू जर्सी, संयुक्त राज्य अमेरिका, 12-14 दिसंबर, 1997 की कार्यवाही। असतत गणित और सैद्धांतिक कंप्यूटर विज्ञान में DIMACS श्रृंखला, DIMACS / AMS 1999, ISBN 978-0-8218-0916-7

6. Grigoryan ई। (2018)। समाधान n- क्वींस समस्या के गठन में नियमितताओं की जांच । आर्टिफिशियल इंटेलिजेंस की मॉडलिंग, 5 (1), 3-21

7. स्लोएन एन-जेए (2016)। पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश।