एक-दूसरे सेट में सब से अधिक दूर बिंदु निर्धारित ढूँढना

Question

मेरा लक्ष्य एल्गोरिथ्म के एक अधिक कुशल कार्यान्वयन उत्पन्न in this question है।

(, एन अंतरिक्ष में। आरजीबी colorspace का उदाहरण मामले के लिए 3-अंतरिक्ष जबकि 1-अंतरिक्ष 2-अंतरिक्ष के लिए एक समाधान केवल दूरी गणना में अलग है) अंक के दो सेट पर विचार करें। आप दूसरे सेट में अपने निकटतम पड़ोसी से सबसे दूर के सेट में बिंदु कैसे पा सकते हैं?

1-स्पेस उदाहरण में, सेट ए: {2,4,6,8} और बी: {1,3,5} दिए गए, उत्तर 8 होगा, क्योंकि 8 से 3 इकाइयां दूर हैं 5 (अपने बी में निकटतम पड़ोसी), जबकि एक के अन्य सभी सदस्यों बी संपादन में उनके निकटतम पड़ोसी से केवल 1 इकाई की दूरी पर हैं: 1-अंतरिक्ष, बहुत ज्यादा सरल है के रूप में छंटाई एक तरह से दूर करने के लिए है कि वह उच्च में नहीं है से संबंधित है आयाम।

स्रोत प्रश्न में समाधान में एक सेट में सभी बिंदुओं की एक ब्रूट फोर्स तुलना शामिल है (सभी आर, जी, बी जहां 512> = आर + जी + बी> = 256 और आर% 4 = 0 और जी% 4 = 0 और बी% 4 = 0) दूसरे सेट (रंगटेबल) में हर बिंदु पर। इस सवाल के लिए, अनदेखा करें, कि पहले सेट को दूसरे सेट की तरह संग्रहीत सूची के रूप में पुनरावृत्त करने के बजाए प्रोग्रामेटिक रूप से विस्तारित किया गया है।

Answer 1

सबसे पहले आप दूसरे सेट में प्रत्येक तत्व का निकटतम पड़ोसी खोजने की जरूरत है।

इस कुशलता से आप एक nearest neighbor एल्गोरिथ्म की जरूरत है ऐसा करने के लिए। निजी तौर पर मैं kd-tree को लागू करता हूं क्योंकि मैंने इसे अपने एल्गोरिदम वर्ग में अतीत में किया है और यह काफी सरल था। एक और व्यवहार्य विकल्प R-tree है।

छोटी से छोटी सेट में प्रत्येक तत्व के लिए एक बार ऐसा करें। (सबसे छोटे से एक से एक तत्व जोड़ें और अपने निकटतम पड़ोसी को खोजने के लिए एल्गोरिदम चलाएं।)

इससे आप प्रत्येक तत्व के लिए निकटतम पड़ोसियों की एक सूची प्राप्त करने में सक्षम होना चाहिए।

जबकि निकटतम पड़ोसियों के जोड़े को खोजने के लिए, उन्हें जो एक तेजी से इसके अलावा विधि और इस तरह के एक heap के रूप में एक तेजी से getMax विधि,, Euclidean distance के अनुसार क्रमबद्ध है एक क्रमबद्ध डेटा संरचना में रहते हैं।

फिर, जब आप काम हो गया बस अधिकतम के लिए ढेर पूछना।

इस प्रकार इस के लिए रन टाइम टूट जाती है:

एन = छोटे सेट
एम के आकार = बड़े के आकार को निर्धारित

• एन * हे (एम + 1 लॉग इन करें) सभी के लिए निकटतम पड़ोसी चेक केडी-पेड़।
• एन * ओ (1) इसे यूपक्लिडियन दूरी की गणना के लिए ढेर में जोड़ने से पहले।
• एन * ओ (लॉग एन) जोड़ों को ढेर में जोड़ने के लिए।
• हे (1) अंतिम जवाब पाने के लिए: डी

तो अंत में पूरे एल्गोरिथ्म हे है (N * लोग इन एम)।

यदि आपको प्रत्येक जोड़ी के आदेश की परवाह नहीं है तो आप केवल अधिकतम पाया गया अधिकतम समय और स्थान बचा सकते हैं।

* अस्वीकरण: यह सब मानता है कि आपके आयामों की एक अत्यधिक उच्च संख्या का उपयोग नहीं किया जाएगा और कि आपके तत्व एक ज्यादातर यादृच्छिक वितरण का पालन करें।

Answer 2

संपादित करें: मेरा मतलब था नलॉग (एन) जहां एन दोनों सेटों के आकार का योग है।

1-अंतरिक्ष सेट मैं आप इस (स्यूडोकोड) की तरह कुछ कर सकता है

की तरह इस

Struct Item { 
    int value 
    int setid 
} 

(1) मैक्स दूरी = 0
सभी (2) पढ़ें एक संरचना का प्रयोग करें में आइटम संरचनाओं में सेट
(3) सभी आइटमों के लिए पॉइंटर्स का एक ऐरे बनाएं
(4) संरचना के आइटम-> मूल्य फ़ील्ड द्वारा पॉइंटर्स की सरणी को क्रमबद्ध करें
(5) से सरणी चलाएं , अंत करने के लिए शुरू की जाँच करता है, तो आइटम,> setid पिछले आइटम, से अलग है> setid अगर (SetIDs अलग हैं)
जांच अगर यह दूरी अधिकतम दूरी से अधिक है यदि ऐसा है तो यह दूरी

वापसी करने के लिए MaxDistance सेट अधिकतम दूरी।

Answer 3

सबसे स्पष्ट दृष्टिकोण मुझे लगता है कि एक सेट पर पेड़ की संरचना बनाने के लिए आपको अपेक्षाकृत तेज़ी से खोज करने की अनुमति मिलती है। एक kd-tree या इसी तरह के लिए शायद इसके लिए उपयुक्त होगा।

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

यह nlog (एन) है पेड़ का निर्माण, और एक खोज इसलिए पूरी बात nlog (एन) में चलाना चाहिए के लिए लॉग इन करें (एन) के लिए।

Answer 4

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

उदाहरण के लिए, यदि आप 2-अंतरिक्ष में काम कर रहे थे, अपने विमान एक 5 x 5 ग्रिड में विभाजित, 25 वर्गों दे रही है, अंक की 25 समूहों के साथ।

3 अंतरिक्ष में, एक 5 x 5 x 5 ग्रिड में अपने घन विभाजित, 125 क्यूब्स, प्रत्येक दे अंक का एक सेट के साथ।

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

Answer 5

सेट बी में प्रत्येक बिंदु के लिए, सेट ए में अपने निकटतम पड़ोसी के लिए दूरी

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

Answer 6

शायद मैं इस सवाल को गलत समझ रहा हूं, लेकिन एक डेटा सेट में सभी निर्देशांकों पर हस्ताक्षर को रिवर्स करना सबसे आसान नहीं होगा (यानि -1 के निर्देशांक के एक सेट को गुणा करें), फिर पहले निकटतम पड़ोसी को ढूंढें (जो सबसे दूर पड़ोसी होगा)? आप अपने पसंदीदा knn एल्गोरिदम का उपयोग k = 1 के साथ कर सकते हैं।