3 डी मठ - केवल गज की एक निश्चित राशि के भीतर पदों को रखते हुए

Question

मैं अपनी सूची को काफी कम करने के लिए स्थिति के एक बड़े सेट से निर्धारित करने की कोशिश कर रहा हूं।

अभी मेरे पास 3000 पदों (x, y, z) हैं और मैं मूल रूप से उन पदों को रखना चाहता हूं जो एक दूसरे से अलग हैं (मुझे 100 पदों को रखने की आवश्यकता नहीं है जो सभी 2 यार्ड के भीतर हैं एक दूसरे से त्रिज्या)।

एक ब्रूट फोर्स विधि करने और सचमुच 3000^2 तुलना करने के अलावा, क्या किसी के पास कोई विचार है कि मैं इस सूची को और कैसे कम कर सकता हूं?

मैं थोड़ा उलझन में हूं कि मुझे गणित परिप्रेक्ष्य से कैसे संपर्क करना चाहिए।

Answer 1

ठीक है, मुझे इस एल्गोरिदम के लिए नाम याद नहीं है, लेकिन मैं आपको इसे संभालने के लिए एक मजेदार तकनीक बताऊंगा। मुझे लगता है कि 3 डी वातावरण में अंक की अर्ध-यादृच्छिक बिखरने वाली है।

सरल संस्करण: फूट डालो और राज

1. फूट डालो घनों के एक 3 डी ग्रिड में अपने अंतरिक्ष। प्रत्येक घन प्रत्येक तरफ एक्स गज होगा।
2. एक बहु-आयामी सरणी [x, y, z] घोषित करें कि आपके ग्रिड में प्रत्येक घन के लिए आपके पास तत्व है।
3. सरणी के प्रत्येक तत्व या तो एक शीर्ष या एक शीर्ष (एक्स, वाई, जेड) संरचना के संदर्भ में किया जाना चाहिए, और प्रत्येक, अपने डेटासेट में हर शीर्ष के माध्यम से
4. दोहराएं शून्य पर डिफ़ॉल्ट का निर्धारण करना चाहिए जो घन शिखर गिरता में
   • कैसे? खैर, आप मान सकते हैं कि (5.5, 8.2, 9.1) vertex MyCubes [5,8,9] में है, मानते हैं कि एक्स (घन-साइड-लम्बाई) आकार 1 है। नोट: मैंने बस दशमलव/फ्लोट को छोटा कर दिया निर्धारित करें कि कौन सा घन।
5. यह देखने के लिए जांचें कि क्या यह प्रासंगिक क्यूब पहले से ही कशेरुक द्वारा लिया गया है या नहीं। जांचें: अगर MyCubes [5,8,9] == शून्य तो किसी और (मेरे शिखर इंजेक्षन) (कुछ भी नहीं, यह पता टॉस लिया, साथी स्पॉट!)

के कुछ स्मृति

सहेजने दें यह आपको एक पास में एक अच्छी तरह से सरलीकृत डेटासेट देगा, लेकिन संभावित रूप से बड़ी मात्रा में स्मृति की लागत पर।

तो, आप बहुत अधिक मेमोरी के बिना इसे कैसे करते हैं?

मैं एक हैशटेबल का उपयोग करता हूं जैसे कि मेरी कुंजी ऊपर दिए गए नमूने में ग्रिड-क्यूब समन्वय (5,8,9) है।

If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...) 

अब, आप कम से कम स्मृति के उपयोग (खाली क्यूब्स के एक बड़े समूह के साथ कोई विशाल सरणी के साथ एक-पास समाधान सेटअप अपने संरचना/वर्ग के लिए प्रोग्रामिंग समय होगा। क्या लागत है? ठीक है, ताकि आप एक HashTable में .contains कार्यवाही नहीं कर सकता (या अपनी भाषा-बराबर)

अरे, मेरे परिणाम chunky, कि किसी भी घन में फिट कर रहे हैं!

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

तो, हम इसे कैसे संभालेंगे? खैर, आइए शीर्ष पर सरणी विधि पर वापस जाएं (स्मृति-गहन!)।

इसके बजाय केवल अगर एक शीर्ष घन-इन-सवाल में पहले से ही है देखने के लिए, यह भी इस दूसरे की जांच करते हैं जाँच की

:

If Not ThisCubeIsTaken() 
    For each SurroundingCube 
     If not Is_Your_Vertex_Sufficiently_Far_Away_From_Me() 
     exit_loop_and_outer_if_statement() 
     end if 
    Next 
    //Ok, we got here, we can add the vertex to the current cube because the cube is not only available, but the neighbors are far enough away from me 
End If 

मुझे लगता है कि आप शायद इस की सुंदरता देख सकते हैं, के रूप में यह है यदि आपके पास 3 डी सरणी है तो पड़ोसी क्यूब्स प्राप्त करना वास्तव में आसान है।

यदि आप इस तरह कुछ चिकनाई करते हैं, तो आप शायद '0.25X' नीति या कुछ के साथ 'जोड़ना न करें' लागू कर सकते हैं। एक ध्यान देने योग्य चिकनाई प्रभाव प्राप्त करने के लिए आपको बहुत सख्त होने की आवश्यकता नहीं होगी।

फिर भी भी chunky, मैं इसे चिकनी

इस बदलाव में चाहते हैं, हम एक शीर्ष एक घन में निवास लेने की अनुमति है या नहीं योग्यता कार्रवाई बदल जाएगा।

If TheCube is empty OR if ThisVertex is closer to the center of TheCube than the Cube's current vertex 
    InsertVertex (overwrite any existing vertex in the cube 
End If 

ध्यान दें, हम इस एक के लिए पड़ोसी का पता लगाने प्रदर्शन करने के लिए नहीं है। हम बस प्रत्येक घन के केंद्र की ओर अनुकूलित करते हैं।

यदि आप चाहें, तो आप पिछले बदलाव के साथ इस बदलाव को विलय कर सकते हैं।

Cheat मोड

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