निकटतम पड़ोसी को हल करने के लिए सर्वश्रेष्ठ प्रदर्शन-महत्वपूर्ण एल्गोरिदम

Question

हमारे पास x, y जोड़े की एक सूची है। प्रत्येक जोड़ी 2 डी स्पेस पर एक बिंदु का प्रतिनिधित्व करती है। मैं इस सूची से निकटतम बिंदु को एक विशिष्ट बिंदु xq, yq में ढूंढना चाहता हूं। इस समस्या के लिए सबसे अच्छा प्रदर्शन-महत्वपूर्ण एल्गोरिदम क्या है? अंक का लिस्पी बदलने वाला नहीं है; जिसका मतलब है कि मुझे सम्मिलन और हटाना करने की आवश्यकता नहीं है। मैं सिर्फ इस सेट में लक्ष्य xq, yq बिंदु के निकटतम पड़ोसी को ढूंढना चाहता हूं।

संपादित करें 1: सभी को धन्यवाद! जैसा कि स्टीफन 202 ने सही ढंग से अनुमान लगाया है, मैं इसे बार-बार करना चाहता हूं; एक समारोह की तरह। एक सूची जरूरी नहीं है (वास्तव में मुझे समझ में नहीं आता कि इसे कैसे हल किया जा सकता है? 2 कॉलम ए और वाई की प्राथमिक कुंजी वाली तालिका की तरह? यदि इससे मदद मिलती है तो मैं इसे सॉर्ट करूंगा)।

मैं एक बार सूची के आधार पर डेटा संरचना का निर्माण करूंगा, और फिर मैं फ़ंक्शन में इस जेनरेट की गई डेटा संरचना का उपयोग करूंगा (यदि यह प्रक्रिया स्वयं प्रासंगिक है)।

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

संपादित करें 2: मुझे पता चला है कि, इस समस्या का नाम "निकटतम पड़ोसी" है!

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

Answer 1

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

मैं एक केडी-पेड़ की सिफारिश करता हूं, जिसका कार्यान्वयन OpenCV 2.0 जैसे कई पैकेजों में आसानी से पाया जा सकता है। या आप खुद को लागू कर सकते हैं!

संपादित करें: मैंने केडी-पेड़ कार्यान्वयन here के बारे में एक प्रश्न पूछा था - उपयोगी हो सकता है।

संपादित करें: केडी के पेड़ों को व्यापक रूप से एनएन खोजों के लिए :) सफलतापूर्वक इस्तेमाल किया गया है - इसके अलावा, अगर आप लगभग मैचों स्वीकार करने को तैयार हैं, तो आप Fast Library for Approximate Nearest Neigbor (FLANN) उपयोग कर सकते हैं। FLANN कार्यान्वयन OpenCV 2.0 में मौजूद है।

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

Answer 2

क्यू (xq, yq) से न्यूनतम दूरी खोजने के लिए दूरी सूत्र का उपयोग करके हर दूसरे बिंदु के माध्यम से Iterate।

हालांकि, आपने प्रदर्शन-महत्वपूर्ण उत्तर के लिए पर्याप्त जानकारी नहीं दी है।

उदाहरण के लिए, यदि क्यू एक बहुत आम बिंदु है, तो आप क्यू की दूरी की गणना करना और प्रत्येक बिंदु के साथ इसे स्टोर करना चाहते हैं।

दूसरा उदाहरण, यदि आप अंक की एक बड़ी संख्या है, तो आप अंक अनुभागों में व्यवस्थित और प्र

Answer 3

यदि क्वेरी पॉइंट (xq, yq) भिन्न होता है और सूची नहीं होती है, तो आपको अंक की सूची के Voronoi diagram की गणना करने की आवश्यकता होती है।यह आपको बहुभुज या "कोशिकाओं" का सेट देगा (जिनमें से कुछ अनंत हैं); प्रत्येक बहुभुज मूल सूची से एक बिंदु से मेल खाता है, जिसे उस सेल की "साइट" कहा जाता है। किसी भी बिंदु जो पूरी तरह से एक बहुभुज के अंदर स्थित है वह उस बहुभुज की साइट के करीब है जो मूल सूची की अन्य साइटों के मुकाबले है। दो बहुभुज के बीच सीमा पर कोई भी बिंदु प्रत्येक साइट से समान रूप से दूर है।

एक बार जब आप इसे प्राप्त कर लेते हैं, तो आपको यह पता लगाने का एक आसान तरीका चाहिए कि आप किस बहुभुज में हैं। इसे point location problem के नाम से जाना जाता है।

इस तरह की चीज़ के लिए वास्तव में, वास्तव में अच्छी किताब Computational Geometry: Algorithms and Applications है। वे वोरोनोई आरेख गणना और बिंदु स्थान के ट्रैपेज़ॉयडल स्लैब विधि दोनों में विस्तार से चर्चा करते हैं।

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

Answer 4

आपको spatial index की आवश्यकता है।

यदि आप अपना खुद का रोल करते हैं, तो आप R-Tree या Quad-tree एल्गोरिदम चुनने से बहुत खराब कर सकते हैं।

Answer 5

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

यदि आपके निर्देशांक फ़्लोटिंग पॉइंट टाइप किए गए हैं तो एक अच्छा ऑप्टिमाइज़ेशन चाल है: एक प्रश्न में आपको सबसे पहले उस पत्ते-नोड को ढूंढना होगा जिसमें सबसे नज़दीकी बिंदु पूछा जाता है। ऐसा करने के लिए आपको जड़ से पत्ते तक पेड़ में जाना होगा - प्रत्येक पुनरावृत्ति में यह तय करना होगा कि कौन सा बच्चा-नोड कदम उठाना है। नोड संरचना में 4-आकार वाली सरणी में बच्चे-नोड्स के पहचानकर्ता/पते स्टोर करें। क्वेरी एल्गोरिदम में बिंदु निर्देशांक को डिजिटाइज करें। फिर आप डिजिटलीकृत बिंदु निर्देशांक के 2 उचित बिट्स द्वारा सरणी को अनुक्रमणित करके उचित उप-नोड ढूंढ पाएंगे। डिजिटाइजिंग तेज़ है: इसे एक साधारण static_cast के साथ कार्यान्वित करें।

लेकिन पहले ऑप्टिमाइज़ेशन के बिना क्वाड्री को कार्यान्वित करें क्योंकि बिट-ऑपरेशंस के साथ बग बनाना आसान है। इस अनुकूलन के बिना भी, यह अभी भी सबसे तेज़ समाधान होगा।