त्रिभुजों से बनी सतहों की गणना का अनुकूलन

कार्य "त्रिकोणासन" के सभी संभावित वेरिएंट के माध्यम से छँटाई का काम करता है। ये एन नियमों की "चमक" हैं जो सरल नियमों का पालन करते हैं:

1. त्रिकोण केवल किनारे से स्पर्श कर सकते हैं
2. एक किनारे को केवल दो त्रिकोणों द्वारा साझा किया जा सकता है, अधिक नहीं

उदाहरण के लिए, अद्वितीय विकल्पों में से तीन त्रिकोणों में से केवल दो हो सकते हैं:
[[एबीसी], [एबीडी], [एसीडी]]
[[एबीसी], [एबीडी], [एसीई]]

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

भोला दृष्टिकोण

एन = 3. तीन त्रिकोण, 9 कोने के साथ विकल्प पर विचार करें। हम संख्या 0 ... 8 को जोड़ते हैं और 000 000 000 से 888 888 888 तक सब कुछ खत्म करते हैं।
जैसा कि आप देख सकते हैं, यह तीन त्रिकोणों के लिए भी बहुत ही नरम है। खैर, त्रिभुजों के दोहराव जो लगातार यहां आएंगे, हमें यहां कुछ भी नहीं चाहिए।

संयुक्त दृष्टिकोण

विचार की लंबी शाम ने सिर को निम्नलिखित विचार को जन्म देने की अनुमति दी:
चूँकि सभी त्रिभुजों को कम से कम एक किनारे से एक साथ सरेस से जोड़ा हुआ होना चाहिए, तब N त्रिभुजों से चमकने के लिए आवश्यक वर्टिकल की संख्या N * 3 से कम होनी चाहिए

वास्तव में, सबसे लंबे समय तक वैध gluing इस तरह दिखेगा:



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

So. तीन त्रिकोण के लिए 5 अद्वितीय कोने।
कुल संयोजन होगा (कॉम्बिनेटरिक्स और द्विपद गुणांक याद रखें) 5! / (3! (5 - 3)!) = 10
यह अद्वितीय त्रिभुजों की संख्या है जो हम सभी संयोजनों के संयोजन उत्पन्न करके प्राप्त कर सकते हैं।

खैर, अब, हम तीन त्रिकोणों के संयोजन के लिए एक ही द्विपद गुणांक पर विचार करते हैं
10! / (3! (10 - 3)!) = 120 । यह सभी विकल्पों को ध्यान में रखने के लिए कितनी झलकियाँ हैं।

सामान्य शब्दों में, संयोजनों की संख्या के लिए सूत्र निम्नानुसार है:



देखें कि कितने तथ्य हैं? उदाहरण के लिए, एन = 10 के लिए कुल 59,473,554,359,599,446 संयोजन होंगे, यह बहुत कुछ है, भले ही समानांतर हो।

जब मैंने छोटे एन (3,4,5 ..) के साथ खोज शुरू की, तो मैंने देखा कि कार्यक्रम जल्दी से सभी संयोजनों को पाता है, और बाकी सिर्फ डुप्लिकेट हैं (उन्हें वीएफ 2 एल्गोरिथ्म द्वारा समाप्त कर दिया गया है, जो आइसोमॉर्फिज़्म के लिए ग्राफ़ की जांच करता है)

बहुत तेज़ - इसका मतलब है कि अंतिम "अच्छा" ग्लूइंग, उदाहरण के लिए, एन = 5 को 324,632 में से 2084 चरणों में पाया गया, जो कि पूरी रेंज का 0.642% है। एन = 6 के लिए, यह 0.3644% है। आखिरी चीज जो मैंने खुद के लिए गणना की थी वह एन = 8 के लिए 0.1352% थी।

यही है, एन + 1 के लिए सामान्य मामले में, हम देखते हैं कि पिछली श्रेणी के कितने प्रतिशत की गणना की गई थी और उसी की गणना की गई थी, यह हमें गारंटी देगा कि सब कुछ जांच लिया गया है। सच है, एन = 9 के लिए यह अभी भी थोड़ा अधिक है (270 485 377 680, यदि आप 0.1352% की जांच करते हैं)

तो, कुछ और के साथ आने के लिए आवश्यक था।

Iterative दृष्टिकोण

कुछ और लंबी शामें और एक और विचार:
लेकिन क्या होगा यदि हम सभी संभावित संयोजनों के साथ एक त्रिकोण जोड़कर N के लिए सभी glues के आधार पर N + 1 के लिए सभी glues उत्पन्न करते हैं?

अर्थात्, हम जानते हैं कि त्रिगुणों के लिए हमारे पास केवल दो हैं

[[एबीसी], [एबीडी], [एसीडी]]
[[एबीसी], [एबीडी], [एसीई]]

और चौके छक्के हैं

[[एबीसी], [एबीडी], [एसीडी], [बीसीडी]]
[[एबीसी], [एबीडी], [एसीडी], [बीसीई]]
[[एबीसी], [एबीडी], [एसीई], [एडीई]]
[[एबीसी], [एबीडी], [एसीई], [एडीएफ]]
[[एबीसी], [एबीडी], [एसीई], [बीसीएफ]]
[[एबीसी], [एबीडी], [एसीई], [बीडीएफ]]

यह देखा जा सकता है कि सभी चार पिछले तिकड़ी से आए थे (क्रमबद्धता क्रमबद्ध रूप से उत्पन्न होती है)

सब कुछ ठीक हो जाएगा, आगे अपने आप को उत्पन्न, लेकिन! जब मैंने इस दृष्टिकोण की जाँच की, तो पाया गया कि सभी नहीं, उदाहरण के लिए, इस तरह से, fives उत्पन्न होते हैं।

[[एबीसी], [एबीडी], [एसीडी], [बीसीई], [बीडीई]]
[[एबीसी], [एबीडी], [एसीडी], [बीसीई], [बीडीएफ]]
[[एबीसी], [एबीडी], [एसीडी], [बीसीई], [बीईएफ]]
[[एबीसी], [एबीडी], [एसीई], [एडीई], [बीसीएफ]]
[[एबीसी], [एबीडी], [एसीई], [एडीएफ], [एईएफ]]
[[एबीसी], [एबीडी], [एसीई], [एडीएफ], [एईजी]]
[[एबीसी], [एबीडी], [एसीई], [एडीएफ], [बीसीजी]]
[[एबीसी], [एबीडी], [एसीई], [एडीएफ], [सीईजी]]
[[एबीसी], [एबीडी], [एसीई], [बीडीई], [सीडीई]]
[[एबीसी], [एबीडी], [एसीई], [बीडीएफ], [सीईजी]]

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

वैसे भी, वहाँ एक रास्ता है। हम एन के लिए सभी परिणामी संयोजनों को लेते हैं, अंत से एक त्रिभुज को मोड़ते हैं, अन्य सभी दो विकल्पों को "उत्पन्न" करते हैं और जांचते हैं। वैसे भी, जुगनू खोज की तुलना में कई गुना अधिक तेज होता है।
लेकिन नहीं, N = 8 पर एक त्रिभुज था जो सभी सेवियों से भिन्न होता है 2 नहीं, बल्कि 3 त्रिकोणों द्वारा।

इसलिए, N = 9 से शुरू होने पर, 2 त्रिकोण बंद हो जाते हैं और तीन "उत्पन्न" होते हैं। इससे एन = 11 तक लगभग सभी विकल्पों की गणना करना संभव हो गया और 12 की शुरुआत (लगभग - क्योंकि सबसे अधिक संभावना है कि वहां ग्लूिंग्स हैं जो 3 से भिन्न हैं, या इससे भी अधिक त्रिकोण हैं)। इस तथ्य के बावजूद कि मैंने इस पूरी चीज को समानांतर किया। मेरे लिए एक धागा ग्लूइंग की प्रारंभिक जांच करता है, शेष 3 डुप्लिकेट को काटने में लगे हुए हैं, क्योंकि आइसोमोर्फिज्म के लिए रेखांकन की जाँच करना एक संसाधन-गहन कार्य है।

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

लेकिन पूरा दिलचस्प है!

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

उदाहरण के लिए, जब त्रिभुजों का संयोजन उत्पन्न होता है, तो पहले वाला हमेशा कुछ इस तरह से होता है:

एबीसी ABD एबीई एबीबी एबीबी ...
यह देखा जा सकता है कि एबी 2 से अधिक बार दोहराता है। यदि हम ऐसे वेरिएंट उत्पन्न कर सकते हैं जहाँ इस तरह के मामले शुरू में मौजूद नहीं होंगे, तो एक कॉम्बीनेटरियल वेरिएंट का विचार सरल होगा, लेकिन मुझे नहीं पता कि इस तरह के क्रम कैसे उत्पन्न होते हैं।

पुनश्च यह सतहों के वर्गीकरण पर वैज्ञानिक कार्य के लिए आवश्यक है। बेशक, वे नाराज नहीं होंगे यदि मैं N = 11 तक डेटा प्रदान करता हूं, तो उनके पास ऐसा कोई डेटा नहीं है (हालांकि, उदाहरण के लिए, 14 त्रिकोणों से एक टोरस बनाया जा सकता है, मुझे इसे एक और वर्ष के लिए गणना करना होगा)। लेकिन यह इस तरह से आना दिलचस्प होगा जो इसे एन को दूर करने की अनुमति देगा। आपका ध्यान देने के लिए धन्यवाद।

युपीडी

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