विभाजन एल्गोरिदम और वान डेर वेर्डन नंबर

हेलो, हेब्र! मैंने ग्राफोमेनिया में लिप्त होने और पिछले सप्ताहांत के मनोरंजन के परिणाम को साझा करने का फैसला किया (केवल इस सप्ताह के अंत में बहुत समय बीत गया और लेख मनोरंजन से बहुत लंबा लिखा गया था। जैसा कि वे कहते हैं, समय एक मजेदार घंटे है)।



मैं तथाकथित विभाजन एल्गोरिदम (विशेष रूप से, डीपीएलएल एल्गोरिथ्म के बारे में), प्रमेय और वैन डेर वेरडेन संख्याओं के बारे में बात करूंगा, और लेख के अंत में हम अपने स्वयं के विभाजन एल्गोरिथ्म लिखेंगे और गणना के आधे घंटे में हम यह साबित करेंगे कि संख्या w (2; 5; ) 178 के बराबर है (1978 में खोजकर्ताओं ने ऐसा करने के लिए 8 दिनों से अधिक की गणना की)।

विभाजन एल्गोरिथ्म

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



यह निम्नानुसार किया जाता है: 3 गैर-प्रतिच्छेदन उप-समूह ए, बी, सी प्रत्येक चरण में शुरू और समर्थित होते हैं, जो सेट एस को पूरी तरह से कवर करते हैं, जहां सी उन तत्वों का सेट है जिन्हें हमने अभी तक ए और बी के बीच वितरित नहीं किया है। प्रारंभिक रूप से, सी, एस; A और B खाली हैं। सेट सी में प्रत्येक पुनरावृत्ति पर, एक तत्व एक मनमाने ढंग से चुना जाता है, जिसे या तो सेट ए या सेट बी में रखा जा सकता है। वास्तव में, हम दोनों करते हैं, और फिर दोनों संभावित विकल्पों की पुनरावृत्ति करते हैं।











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



"मुझे दो!", आप कहते हैं, "2 में से एक स्पष्ट खोज से बेहतर क्या है ^{| एस |} विकल्प? ”। और पूरी चीज कट-ऑफ है, जो एल्गोरिदम की प्रस्तावित रीढ़ को जोड़ने के लिए बहुत सुविधाजनक है!



कतरन सूची:

1. यदि आंशिक रूप से निर्मित ए और बी उपयुक्त नहीं हैं - रोलबैक
2. किसी तत्व को S से A या B में ले जाने से S से A या B में अन्य तत्वों को ले जाया जा सकता है
3. प्रत्येक चरण पर एस से उचित चयन से पुनरावृत्ति पेड़ के आकार को काफी कम किया जा सकता है

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



उदाहरण के रूप में क्लासिक डीपीएलएल एल्गोरिथ्म का उपयोग करके सामान्य विभाजन एल्गोरिथ्म और सभी प्रस्तावित कटऑफ की व्याख्या करना सुविधाजनक है।

डीपीएलएल एल्गोरिथ्म

डेविस - पुतनाम - लोगनेमैन - लवलैंड ( डीपीएलएल ) एल्गोरिथ्म को 1962 में विकसित किया गया था, जो सामान्य रूप में लिखे गए बूलियन सूत्रों की व्यवहार्यता को निर्धारित करने के लिए, अर्थात्। SAT समस्या को हल करने के लिए। एल्गोरिथ्म इतना प्रभावी निकला कि 50 से अधिक वर्षों के बाद, यह सबसे प्रभावी एसएटी सॉल्वर के लिए आधार का गठन करता है।



आइए DPLL एल्गोरिथ्म क्या करता है पर एक करीब से देखो। वह बूलियन फॉर्मूला लेता है और सभी वेरिएबल्स को विभाजित करने का प्रयास करता है जो इसके दो सेट ए और बी में विभाजित होते हैं, जहां ए सत्य के साथ सभी वेरिएबल्स का सेट होता है और बी गलत के साथ सभी वेरिएबल्स का सेट होता है।



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



प्रत्येक असाइनमेंट के बाद, सूत्र आगे के दो नियमों द्वारा सरल किया जाता है:

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

जब तक वे लागू होते हैं, तब तक इन दो नियमों को लागू किया जाना चाहिए: आमतौर पर पहले असाइनमेंट के बाद सरलीकरण का एक पूरा झरना निम्नानुसार होता है, जो अच्छी तरह से मुक्त चर की संख्या को कम करता है।



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



एक छोटा C- जैसा छद्म कोड जो बताता है कि क्या होता है:

bool DPLL( eq F, set A, set B, set C ) { while(1) { //    if (F is empty) { //  ! write A, B, C; return true; } if (F contains an empty clause) return false; //    //  bool flag = false; if (unit_propagation(&F, &A, &B, &C)) flag = true; if (pure_literal_elimination(&F, &A, &B, &C)) flag = true; if (!flag) break; //    } //  x = choose_literal(F, ); if (DPLL(F ∧ (x), A^x, B, C^x)) return true; if (DPLL(F ∧ (¬x), A, B^x, C^x)) return true; return false; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

& सिंबल इंगित करता है कि Unit_propagation और pure_literal_elimination फ़ंक्शन में, चर एफ, ए, बी और सी संदर्भ द्वारा पारित किए जाते हैं, अर्थात्। वे अंदर बदल सकते हैं। यदि कुछ बदल गया है, तो ये फ़ंक्शन सही हैं। एक पुनरावर्ती वंश के साथ, इसके विपरीत, वस्तुओं की प्रतियां बनाई जाती हैं। ^ आइकन सेट से किसी ऑब्जेक्ट को बाहर निकालता है अगर यह मौजूद है या नहीं तो जोड़ता है।



निम्नलिखित सूत्र पर विचार करें और देखें कि डीपीएलएल एल्गोरिदम कैसे काम करता है:









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









डबल तीरों से पता चलता है कि हम पहले नियम का उपयोग कर रहे हैं, अर्थात्, हम एक अकेला चर पाते हैं और इसे वांछित मूल्य प्रदान करते हैं।



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









ट्रिपल तीर संकेत करते हैं कि हम दूसरा सरलीकरण नियम लागू कर रहे हैं। इस शाखा में सफलता हमारा इंतजार करती है - 2 समाधान मिल चुके हैं!



संपूर्ण ट्रैवर्सल वृक्ष:









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



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



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

वैन डेर वेर्डन प्रमेय और संख्या

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



पिछली सदी के बिसवां दशा में, एक गणितज्ञ को निम्नलिखित समस्या का सामना करना पड़ा:



बता दें कि सभी प्राकृतिक नंबरों के सेट को 2 अलग-अलग रंगों में चित्रित किया गया है। क्या यह कहना संभव है कि एक मनमाने ढंग से लंबे अंकगणितीय प्रगति है, जिनमें से संख्याओं को एक ही रंग में चित्रित किया गया है?



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



किसी भी r और k के लिए एक नंबर n (r; k) मौजूद है जैसे कि प्राकृतिक संख्याओं के सेट के किसी भी रंग के लिए S = {1, 2, ..., n (r; k)} से अलग-अलग रंगों में, इस सेट S में अंकगणित होगा। एक ही रंग में चित्रित k संख्याओं की प्रगति।



सबूत तथाकथित दोहरे प्रेरण पर आधारित है। इस प्रमाण का एक सरलीकृत संस्करण पाया जा सकता है, उदाहरण के लिए, यहाँ ।



N (r; k) की संख्या को w (r; k) से दर्शाया जाता है। संख्या w (r; k) को वैन डेर वेर्डन संख्या कहा जाता है। वैन डेर वेरडेन प्रमेय का प्रमाण संख्याओं के सटीक मानों को नहीं देता है w (r; k), केवल ऊपरी बाउंड। और मेरा विश्वास करो, यह ऊपरी सीमा बस विशाल है! यह पता चला कि दो रंगों के लिए भी संख्या w (r; k) का अनुमान एकरमैन के कार्य के रूप में बढ़ता है! यह शीर्ष अनुमान धीरे-धीरे सुधर रहा है। 2001 में टिमोथी गोवर्स का नवीनतम परिणाम है:



w (r; k) ^{r 2 2 r 2 2 k + 9}



परिणाम मूल की तुलना में थोड़ा कम डरावना है, लेकिन अभी भी थोड़ा डरावना है। और फिर भी, यह सीमा w (r; k) के सटीक मूल्यों से बहुत दूर है।



अनुसंधान की एक अलग शाखा अलग-अलग r और k के लिए संख्या w (r; k) के सटीक मानों का निर्धारण है। यह कार्य बहुत संसाधन-गहन है (यह रामसे सिद्धांत के अधिकांश कार्यों का विशिष्ट है)। विकिपीडिया कहता है कि इस समय, w (r; k) का सही मूल्य केवल 7 जोड़े संख्याओं r और k के लिए जाना जाता है।

आर / के	3	4	5	6
2 रंग	9	35	178	1132
3 रंग	27	293
4 रंग	76

W (2; 3) का उत्तर तुच्छ रूप से प्राप्त होता है:







W (r, k) के थोड़े बड़े मूल्यों के लिए, प्रमाण आमतौर पर निम्नलिखित पर उबलता है: संख्या n की रंगीन श्रृंखला की लंबाई तय की जाती है, और फिर बूलियन सूत्र को सामान्य सामान्य रूप में बनाया जाता है ताकि यह सत्यापित किया जा सके कि इन n संख्याओं को r और k के प्रतिबंधों को ध्यान में रखते हुए रंगीन किया जा सकता है। एसएटी सॉल्वर का उपयोग करके इसकी व्यवहार्यता की जाँच की जाती है। यदि कोई समाधान पाया जाता है, तो नंबर n + 1 w (r; k) के लिए निचली सीमा है; अन्यथा, नंबर n को w (r; k) के लिए ऊपरी बाध्य माना जाना चाहिए।



यह देखते हुए कि कई SAT-solvers DPLL एल्गोरिथ्म पर आधारित हैं, संख्या w (r; k) को विभाजित एल्गोरिदम का उपयोग करके खोजा जाता है।



हम रंगों की संख्या r = 2 के लिए वांछित बूलियन फार्मूला बनाने का एक सरल तरीका देते हैं। हमें n वैरिएबल x मिलता है जिसका मतलब है कि संबंधित नंबरों को किस रंग में रंगा गया है। सही मान का अर्थ होगा 1 रंग, असत्य - दूसरा। हमें प्रतिबंध लगाने की जरूरत है ताकि किसी भी अंकगणितीय प्रगति में दोनों रंग शामिल हों। यह बहुत सरलता से किया जाता है: फॉर्म का _एक क्लॉज (x _{a 1} ∨x _{a 2} ∨ ... ∨x _{a a} ) पहले रंग की उपस्थिति की गारंटी देता है, और फॉर्म का क्लॉज (∨¬x _{a 1} ax _{a 2} ∨ ... ∨¬x _{a k} ) - दूसरा । खैर, वास्तव में, यह सब है - प्रत्येक अंकगणितीय प्रगति के लिए हम 2 सूत्र बनाते हैं और सब कुछ गोंद करते हैं जो एक बड़े सीएनएफ में हुआ।



R = 2, k = 3 और n = 9 के सूत्र का एक उदाहरण:



(x ₁ xx ₂ 3x ₃ ) ∨ (1x ₁ ∨¬x ₂ )x ₃ ) ∨ (x ₂ ∧x ₃ ∨x ₄ ) ∧ (∨¬x ₂ 3x ₃ ∨x ₃ ) ∨ (x ₃ xx ₄ 5x ₅ ) ∨ (∨¬x ₃ ∨¬x ₄ 5x ₅ ) ∨

(x ₄ xx ₅ 6x ₆ ) ∨ (4x ₄ ∨x ₅ 6x ₆ ) ∨ (x ₅ ∧x ₆ 7x ₇ ) ∧ (∨¬x ₅ 6x ₆ ∨x _{6 7} ) ∨ (x ₆ xx ₇ 8x ₈ ) ∨ (∨¬x ₆ ∨¬x ₇ 8x ₈ ) ∨

(x ₇ xx ₈ 9x ₉ ) ∨ (7x ₇ ∨¬x ₈ 9x ₉ ) ∨ (x ₁ ∨x ₃ ∨x ₅ ) ∧ (∨¬x ₁ 3x ₃ ∨x ₉ ) (x ₂ xx ₄ 6x ₆ ) ∨ (∨¬x ₂ ∨¬x ₄ 6x ₆ ) ∨

(x ₃ xx ₅ 7x ₇ ) ∨ (3x ₃ ∨¬x ₅ 7x ₇ ) ∨ (x ₄ ∧x ₆ ∨x ₈ ) ∨ (4x ₄ 6x ₆ ∨x ₈ ) ∨ (x ₅ xx ₇ 9x ₉ ) ∨ (∨¬x ₅ ∨¬x ₇ 9x ₉ ) ∨

(x ₁ xx ₄ 7x ₇ ) ∨ (1x ₁ ∨¬x ₄ 7x ₇ ) ∨ (x ₂ ∧x ₅ ∨x ₈ ) ∧ (∨¬x ₂ 5x ₅ ∨x _{8 8} ) ∨ (x ₃ xx ₆ 9x ₉ ) ∨ (∨¬x ₃ ∨¬x ₆ 9x ₉ ) ∨

(x ₁ xx ₅ ∨x ₉ ) ¬ (∨¬x ₁ ∨¬x ₅ 9x ₉ )



पिछले स्पॉइलर में, यह साबित हो गया था कि यह सूत्र असंभव है।

ज्ञान को व्यवहार में लाना

अब संख्या w (2; k) को खोजने के लिए अपने स्वयं के विभाजन एल्गोरिथ्म को लिखते हैं, जो किसी सॉल सॉल्वर की तरह किसी भी टिनसेल का उपयोग नहीं करता है। हम C ++ (मैं MS Visual Studio का उपयोग करता हूं) में लिखूंगा। एल्गोरिथ्म का आधार निम्नानुसार है:

 #pragma comment(linker,"/STACK:64000000") #include <iostream> #include <bitset> #include <time.h> #include <memory.h> using namespace std; #define N 178 #define K 5 #define BSET bitset< N > bool dfs( BSET & A, BSET & B ) { int i = choice( A, B ); if (i<0) { for (int a=0; a<N; a++) if (A[a]) cout << "A"; else if (B[a]) cout << "B"; else cout << "?"; cout << "\n"; return true; } A[i] = true; if (check(A, B)) { BSET A1 = A, B1 = B; if (reduce( A1, B1 )) if (dfs( A1, B1 )) return true; } A[i] = false; B[i] = true; if (check( A, B )) { BSET A1 = A, B1 = B; if (reduce( A1, B1 )) if (dfs( A1, B1 )) return true; } B[i] = false; return false; } int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); BSET A, B; if (!dfs( A, B )) cout << "No counterexamples\n"; cout << "n=" << N << " k=" << K << "\n"; cout << "time=" << clock() << "\n"; return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Dfs प्रक्रिया, वास्तव में, एल्गोरिथ्म की रीढ़ है। स्थिरांक N और K (अनुक्रम लंबाई और अंकगणितीय प्रगति लंबाई, क्रमशः) को संख्या के रूप में प्रीप्रोसेसर द्वारा कोड में डाला जाएगा, कभी-कभी यह संकलक को कोड को बेहतर रूप से अनुकूलित करने में मदद करता है। सेट ए और बी (क्रमशः पहले और दूसरे रंगों में रंगे जाने वाले अनुक्रम तत्व) लंबाई एन के एक बिटस्कैम के साथ सेट होते हैं। अब आपको प्रस्तावित कंकाल पर कार्यों को लटका देना चाहिए।

1. पसंद - तत्व की पसंद जिसके द्वारा हम अपने पेड़ को शाखा देंगे।
2. check - जांचें कि लंबाई K की अंकगणितीय प्रगति नहीं है।
3. कम करना - अतिरिक्त तत्वों को चित्रित करना जिसके लिए रंग विशिष्ट रूप से निर्धारित किया जा सकता है।

पसंद समारोह सबसे दिलचस्प में से एक है:

 int cost[N]; int choice( BSET & A, BSET & B ) { memset( cost, 0, sizeof(cost) ); for (int a=0; a<N; a++) for (int d=1; a+d*(K-1)<N; d++) { int cnt1=0, cnt2=0; for (int c=0; c<K; c++) if (A[a+c*d]) cnt1 ++; for (int c=0; c<K; c++) if (B[a+c*d]) cnt2 ++; if (cnt1==0 || cnt2==0) for (int c=0; c<K; c++) if (!A[a+c*d] && !B[a+c*d]) cost[a+c*d] += cnt1+cnt2+1; } int mx = 0; for (int a=0; a<N; a++) mx = max( mx, cost[a] ); if (mx > 0) for (int a=0; a<N; a++) if (cost[a] == mx) return a; return -1; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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



अब जाँच प्रक्रिया पर विचार करें:

 bool check( BSET & A, BSET & B ) { for (int a=0; a<N; a++) for (int d=1; a+d*(K-1)<N; d++) { bool f1=true, f2=true; for (int c=0; c<K; c++) f1 &= A[a+c*d]; for (int c=0; c<K; c++) f2 &= B[a+c*d]; if (f1 || f2) return false; } return true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

यह प्रक्रिया छोटी, सरल और सीधी है, इसलिए इस पर ध्यान देने का कोई मतलब नहीं है।



अंत में, कम करने की प्रक्रिया:

 bool reduce( BSET & A, BSET & B ) { while ( 1 ) { bool flag = false; for (int a=0; a<N; a++) for (int d=1; a+d*(K-1)<N; d++) { int cnt1=0, cnt2=0; for (int c=0; c<K; c++) if (A[a+c*d]) cnt1 ++; for (int c=0; c<K; c++) if (B[a+c*d]) cnt2 ++; if (cnt1+cnt2<K) { if (cnt1 == K-1) for (int c=0; c<K; c++) if (!A[a+c*d]) { B[a+c*d] = true; flag = true; } if (cnt2 == K-1) for (int c=0; c<K; c++) if (!B[a+c*d]) { A[a+c*d] = true; flag = true; } } } if (!flag) break; if (!check( A, B )) return false; } return true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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

परिणाम

कोड का परीक्षण कोर i5 4Gb रैम लैपटॉप पर किया गया था। 2 मिनट में पैरामीटर मान N = 177 K = 5 के साथ, निम्न उदाहरण पाया गया:



BBBABBBBABB?BAAABABBBA?AABAAAABAAAABBBABAAABBBBABBBBABB?BAAABABBBAAAABAAAABAABABBBABAAABA

BBABBBBABBABAAABABBBAAAABAAAABAABABBBABAAABABBABBBBABB?BAAABABBBABAABAAAABAABABBBABAAAB?







ए और बी रंग हैं। एक प्रश्न का अर्थ है कि यह हमारे लिए कोई मायने नहीं रखता कि कौन सी रंग किस स्थिति में है। यही है, वास्तव में, हमने लंबाई 177 के 32 उदाहरणों के रूप में पाया, जिसमें लंबाई 5 की एक-रंग अंकगणितीय प्रगति नहीं है।



एन = 178 के = 5 के मापदंडों पर, कोड ने 20.5 मिनट तक काम किया और दिखाया कि कोई वांछित अंकगणितीय प्रगति नहीं थी। सामान्य मामले में ^2,178 विकल्पों के लिए बुरा नहीं है।



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



बेशक, कोड w (2; 3) और w (2; 4) की गणना करने के लिए भी काम करता है (पूरी बात शुरू से ही उन पर परीक्षण की गई थी)।



केस के बारे में क्या = 6? हाल ही में (2008 में) यह साबित हुआ कि w (2; 6) = 1132 और 200 कोर के क्लस्टर पर लगभग 250 दिनों की गणना हुई। वैसे, उनके एल्गोरिथ्म के कार्यान्वयन से साबित होता है कि w (2; 5) = 178, एक कोर पर 3 सेकंड से भी कम समय में। केस के = 7 के लिए, सवाल खुला रहता है।

आदर

1. लेक्टोरियम पर विभाजन एल्गोरिदम (वीडियो, व्याख्यान स्लाइड)
2. ब्रोन-केर्बोश एल्गोरिथ्म एक ग्राफ में सभी क्लिकों को खोजने के लिए (अनिवार्य रूप से एक विभाजन एल्गोरिथ्म)
3. विकिपीडिया पर DPLL एल्गोरिथ्म ( rus , eng )
4. वैन डेर वेर्डन प्रमेय और संख्याएँ (संलग्न)
5. उ। हां। खिनचिन। संख्या सिद्धांत के तीन मोती
6. बाइबिल कोड, रैमसे थ्योरी और ईश्वर का अस्तित्व
7. रोनाल्ड एल। ग्राहम, जोएल एक्स। स्पेन्सर। रैमसे थ्योरी
8. आरएस स्टीवंस, आर। शांताराम कंप्यूटर जनरेटेड वैन डेर वेर्डन विभाजन (संलग्न, पीडीएफ)
9. मिशल कोर्इल, जेरोम एल पॉल। वैन डेर वेर्डन नंबर डब्ल्यू (2.6) 1132 है (संलग्न, पीडीएफ)

PS उन सभी लिंक के साथ नहीं, जिन्हें मैंने गहराई से पढ़ा है, इसलिए यदि मैं नहीं लेता कि कौन सा लिंक वास्तव में विषय से दूर है।