लगभग सात सिलेंडर

संपर्क में सात सिलेंडरों के बारे में एक लेख पढ़ने के बाद, मैंने सोचा: क्या यह कार्य वास्तव में इतना मुश्किल है? या वह पहले से ही गंभीर रूप से शामिल नहीं थी?

अंतरिक्ष में ज्ञात त्रिज्या के एक अनंत सिलेंडर की स्थिति को चार स्वतंत्र मात्राओं से परिभाषित किया गया है (इसमें स्वतंत्रता की 4 डिग्री है)। सामान्य स्थिति में सात सिलेंडर के लिए, 28 मान आवश्यक हैं। प्रत्येक शर्त "दो सिलेंडर टच" एक प्रतिबंध देता है, कुल मिलाकर स्वतंत्रता की 7 डिग्री हैं। उनमें से छह - अंतरिक्ष की गति, बाद वाला कॉन्फ़िगरेशन पर ही रहता है। यही है, हमें विन्यास के एक या एक से अधिक पैरामीटर वाले परिवार प्राप्त करने चाहिए, जब तक कि टोपोलॉजी को चोट न पहुंचे (जिसके कारण कोई समाधान नहीं हो सकता है)।

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



हमारा पहला काम कम करना है, जहां तक ​​संभव हो, प्रणाली का वर्णन करने वाले चर की संख्या। चलो अंतरिक्ष के विस्थापन से छुटकारा पाने के द्वारा शुरू करते हैं। मान लीजिए कि पहली पंक्ति ओज अक्ष है। मान लीजिए कि हमारे पास एक और रेखा बी है, जिससे ओज़ की दूरी 1 है। बी को ओज़ के सबसे निकट बिंदु पर निर्देशांक (x, y, z) है । फिर, जैसा कि देखने के लिए आसान है, हालत , और लाइन B के निर्देशन वेक्टर को कुछ d के लिए फॉर्म (-y, x, d) में निर्दिष्ट किया जा सकता है। इस प्रकार, लाइन को 4 अतिरिक्त x, y, z, d द्वारा एक अतिरिक्त स्थिति के साथ परिभाषित किया गया है।

हमारे पास अभी भी अंतरिक्ष की गति की स्वतंत्रता के दो डिग्री हैं: ओज़ अक्ष के साथ एक बदलाव और इसके चारों ओर एक घुमाव। हम दूसरी पंक्ति के लिए x = 1, y = z = 0 चुनकर उन्हें ठीक करते हैं। शेष 20 अज्ञात (शेष 5 लाइनों के पैरामीटर) आगे प्रतिबंधित नहीं हैं।

शर्त यह है कि मापदंडों के साथ दो लाइनों के बीच की दूरी (x ₁ , y ₁ , z ₁ , d ₁ और (x ₂ , y ₂ , z ₂ , d ₂ 1 है, जिसे प्रपत्र में लिखा जा सकता है।



यह 8 अंको को जोड़ने वाला 6 वाँ डिग्री समीकरण है। डिग्री को चौथे तक कम किया जा सकता है यदि हम लाइन के थोड़ा अलग पैरामीटराइजेशन लेते हैं (कहते हैं कि यह बिंदु (x, y, 0) से गुजरता है और एक दिशा सदिश (u, v, 1) ) है, लेकिन फिर हम ओज़ के लिए लंबवत लाइनों को खो देते हैं।

तो, हमारे पास एक बहुपद समीकरण है। यह 21 अज्ञात के साथ 20 ऐसे समीकरणों की एक प्रणाली की रचना करने के लिए रहता है, और सोचता है कि इसके साथ क्या करना है। इसे याद रखें, और दूसरे तरीके की तलाश करें।

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



जहाँ । यह z ₂ -z _{1 के} लिए एक द्विघात समीकरण है, अर्थात, मात्राओं को जानना हम आसानी से z ₂ -z _{1 के} दो संभावित मान प्राप्त कर सकते हैं।

कार्ययोजना इस प्रकार होगी।

1. चलो एक यादृच्छिक खोज का प्रयास करें। एक यादृच्छिक सेट उत्पन्न करें । तीसरी से 7 वीं तक प्रत्येक पंक्ति के लिए हम दूरी को दूसरी पंक्ति के लिए लिखते हैं - यह हमें अज्ञात ₃ z, ... z _{7 के} दो संभावित मान देगा। इन मूल्यों के 32 संभावित संयोजनों में से प्रत्येक के लिए, हम यह जांचेंगे कि शेष जोड़े लाइनों के बीच की दूरी 1 से कितनी भिन्न होगी, और सबसे अच्छा संयोजन चुनें। कुछ अनुकूलन विधि से, हम सभी दूरियों को ड्राइव करने का प्रयास करेंगे। 1. यदि हम सफल होते हैं, तो हम जीत गए। यदि नहीं, तो एक और मिलियन बार दोहराएं।

2. यदि खोज ने परिणाम वापस नहीं किया, तो हम खोज का विस्तार करेंगे। हम z ₃ , ... z _{7 के} सभी संभावित संयोजनों से जाएंगे।

3. ध्यान दें कि अगर हमारे संपर्क में चार सिलेंडर हैं, तो निश्चित रूप से उन सभी को छूने वाले सिलेंडरों की संख्या। हम किसी भी तरह से पहले 4 सिलेंडरों का निर्माण करते हैं (हमारे पास स्वतंत्रता के 4 डिग्री हैं), फिर देखो (यादृच्छिक खोज द्वारा) जितना संभव हो उतने सिलेंडरों के लिए, उनमें से तीन का चयन करें, जिनमें से कुल्हाड़ियों के बीच जोड़ीदार दूरी 1 जितना संभव हो, और कोशिश करें प्राप्त सेट का अनुकूलन करने के लिए।

4. एक ही बात है, लेकिन सबसे पहले, हम संपर्क में सभी सिलेंडरों की तलाश करते हैं, 4 बहुपद समीकरणों (एक जटिल क्षेत्र में इसकी 32 जड़ें) की एक प्रणाली को हल करते हैं, और फिर उनके तीनों अक्षों पर पुनरावृति करते हैं।

5. यदि आप फिर से अशुभ हैं, तो हम यह सोचना शुरू करते हैं कि ये विन्यास क्या हैं और इनका उपयोग कैसे किया जा सकता है।

दुर्भाग्य से, इस योजना में कुछ भी नहीं आया। क्यों?

यादृच्छिक खोज और अनुकूलन

यादृच्छिक समाधान का अनुकूलन करने के लिए, मैंने सबसे अधिक परीक्षण की गई विधि - न्यूटन की विधि का उपयोग किया। सच है, उसे अज्ञात की संख्या के बराबर समीकरणों की संख्या की आवश्यकता है, इसलिए अज्ञात d ₂ (यानी, पहली और दूसरी सीधी रेखा के बीच का कोण) को ठीक करने का निर्णय लिया गया। आंशिक डेरिवेटिव z _k -z _m द्वारा खोजें तकनीक का मामला है, और हम आसानी से अपने सिस्टम के जैकबिएन मैट्रिक्स को 10 * 10 आकार में बनाते हैं। यह सच है कि सामान्य फॉर्मूले के बजाय x: = xJ ^-1 f (x), मैंने एक स्लो मोशन x: = xc * J ^-1 f (x) का उपयोग किया , जहाँ c 0.1 से 0.001 तक भिन्न होता है (चूंकि उस क्षेत्र में जिससे आपको भटकना पड़ता है) बहुत असमान और बहुत सारे स्थानीय मिनीमा के साथ)। यह आगे पता चला कि यह विधि gluing सीधी रेखाओं को स्वीकार करती है, जिसके बाद यह 0 से विभाजित करने की कोशिश करता है - मुझे उसे समझाना था कि यदि किसी भी जोड़ी के लिए लाइनें शून्य के करीब हैं, फिर इस प्रयास में हम असफल रहे।

ऐसी खोज लिखना मुश्किल नहीं था। सभी बेहिसाब क्षणों को ठीक करने के बाद, मैंने इसे लॉन्च किया - और पहला समाधान कुछ ही सेकंड के बाद, लगभग 9000 वर्षों के प्रयास के बाद मिला। अगले 30 मिनट में, कार्यक्रम में 500 कॉन्फ़िगरेशन पाए गए, फिर औसतन 7,500 प्रयासों में से एक सफल रहा।

एक स्वतंत्र जांच से पता चला कि समाधान सही हैं - लाइनों के जोड़े के बीच की दूरी 1 से 10 ^-9 से अधिक नहीं थी। लेकिन, निर्मित चित्रों को देखकर, मैंने पाया कि उनमें से कई कुछ समान हैं ... तो अगला सवाल था: कौन से विन्यास समान हैं और किस अर्थ में हैं?











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



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



किसी कारण के लिए, यह प्रक्षेपवक्र, हालांकि अनन्तता में समाप्त हो जाता है, लेकिन किसी तरह के मृत अंत में शुरू होता है, जिसके माध्यम से यह विफल रहता है। मैंने अभी तक इस पहेली को हल नहीं किया है। इसके अलावा, ऐसे संकेत हैं कि किसी स्थान पर दो प्रक्षेपवक्र या तो बहुत निकट या अभिसरण करते हैं।

किसी भी मामले में, योजना के 2-5 बिंदुओं की आवश्यकता नहीं थी।



अन्य 70 मिलियन अंकों से गुजरने और 10,000 से अधिक समाधान खोजने के बाद, कार्यक्रम को कुछ नया नहीं मिला। इसलिए केवल स्कोर के पहले मिनट को उपयोगी तरीके से खर्च किया गया था ...



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

अब तक रैंडम खोज एक पहले से पाए गए परिवार से केवल अंक देती है। यह संभव है कि कोई अन्य कॉन्फ़िगरेशन (और समाधान के सेट से जुड़े घटक) नहीं हैं। यह जांचना आवश्यक होगा कि क्या हंगेरियन द्वारा पाए गए विन्यास वास्तव में भिन्न हैं या नहीं।



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

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