पर बिंदुओं के एक सेट से सबसे नज़दीकी बिंदु ढूँढना 2-डी विमान पर एन अंक दिए गए, बिंदु क्या है कि सभी बिंदुओं से दूरी कम हो गई है? इस बिंदु को दिए गए अंकों के सेट से नहीं होना चाहिए। क्या यह सेंट्रॉइड है या कुछ और?विमान
एल्गोरिदम के साथ ऐसे सभी अंक (यदि एक से अधिक) कैसे ढूंढें?
इसे "दूरी का केंद्र" के रूप में जाना जाता है और यह केंद्र से अलग है।
सबसे पहले आपको यह निर्धारित करना होगा कि आप किस दूरी का उपयोग कर रहे हैं। यदि हम मानते हैं कि आप डी = sqrt ((x1-x2)^2 + (y1-y2)^2 के मानक मीट्रिक का उपयोग कर रहे हैं तो यह अद्वितीय नहीं है, और समस्या इस राशि को कम कर रही है।
इस उत्तर को दिखाने का सबसे आसान उदाहरण सीधा रेखा उदाहरण अद्वितीय नहीं है। दो बिंदुओं के बीच किसी भी बिंदु के सभी बिंदुओं से बराबर कुल दूरी होती है।
1 डी में, सही उत्तर कोई जवाब होगा जिसमें दाएं और बाएं बिंदुओं की संख्या समान होगी। जब तक यह सच है, तब बाएं और दाएं किसी भी कदम से बाएं और दाएं किनारे एक ही राशि से बढ़ जाएंगे और इसलिए दूरी को छोड़ दें। यह भी साबित करता है कि केंद्र आवश्यक रूप से सही उत्तर नहीं है।
यदि हम 2 डी तक विस्तार करते हैं तो यह अब मामला नहीं है - क्योंकि वर्गमीटर समस्या को भारित करता है। आश्चर्यजनक रूप से मेरे लिए एक मानक एल्गोरिदम प्रतीत नहीं होता है! पृष्ठ here एक ब्रूट फोर्स विधि का उपयोग करने लगता है। मुझे नहीं पता था!
अगर मैं एल्गोरिदम का उपयोग करना चाहता था, तो मुझे एक्स और वाई में मध्य बिंदु को प्रारंभ बिंदु के रूप में मिलेगा, फिर gradient descent algorithm का उपयोग करें - इससे उत्तर बहुत जल्दी मिलेगा। संपूर्ण समीकरण एक वर्ग के रूप में समाप्त होता है, इसलिए ऐसा लगता है कि एक सटीक समाधान होना चाहिए।
क्या आपके पहले लिंक में ब्रूट फोर्स एल्गोरिदम किसी क्षेत्र पर बिंदुओं के लिए नहीं करता है? –
नहीं, मैंने एन अंक के लिए ढाल वंश कहा। अपना स्कोरिंग फ़ंक्शन लिखें ताकि यह सभी एन अंकों की कुल दूरी की गणना कर सके, फिर अपने मूल कार्य को इस मान को कम करने दें। मैं होमवर्क के मामले में कोड जोड़ने वाला नहीं हूं, इसे लिखना आसान होना चाहिए। –
@ मैथिज, शायद, मैं बहुत मुश्किल नहीं लग रहा था। इंगित करने के लिए धन्यवाद। यह एक दिलचस्प सवाल है यह नहीं है। –
एक से अधिक बिंदु हो सकते हैं। इस पर केवल दो बिंदुओं के साथ एक विमान पर विचार करें। वे बिंदु एक रेखा सेगमेंट का वर्णन करते हैं। उस लाइन-सेगमेंट पर किसी भी बिंदु पर दो अंत-बिंदुओं से समान दूरी होगी।
में कर रहा हूं तो एल्गोरिदम के साथ ऐसे सभी बिंदु कैसे ढूंढें? – nowonder
असल में जवाब एक साधारण बहुभुज होने जा रहा है। कारण यह है कि उत्तल कार्यों (जैसे दूरी समारोह) का योग उत्तल है। आप शायद त्रिकोण से शुरू करके और अंक जोड़कर अपने सटीक निर्देशांक पा सकते हैं। हालांकि यह मूर्खतापूर्वक कर रहा है 'n^2' होगा। –
एक क्रूर बल अलगो। आपको सबसे अच्छा परिणाम दे सकता है। सबसे पहले, इनपुट बिंदुओं को बाध्य करने वाले आयताकार/किसी भी चतुर्भुज को ढूंढें। अंत में, आयताकार के अंदर प्रत्येक बिंदु के लिए, अन्य बिंदुओं से दूरी की गणना करें। इनपुट सेट से बिंदु की दूरी को मापें। कहें कि यह बिंदु की 'लागत' है। प्रत्येक बिंदु के लिए दोहराएं और न्यूनतम के साथ बिंदु चुनें। लागत।
इंटेलिजेंस को भी अहंकार में जोड़ा जा सकता है। यह औसत लागत, आदि के आधार पर क्षेत्रों को खत्म कर सकता है ...
Thats मैं कम से कम समस्या से कैसे संपर्क करूंगा ... उम्मीद है कि यह मदद करता है।
लेकिन इसकी बहुत जटिलता है। आयताकार के अंदर प्रत्येक बिंदु की जांच करना, यह कैसे करना है, बिंदु निर्देशांक कोई फ़्लोटिंग पॉइंट नंबर हो सकता है। – nowonder
अच्छी तरह से आपको कुछ चरण आकार की आवश्यकता है, लगातार दो बिंदुओं के बीच न्यूनतम दूरी, सी का उपयोग करके एक साधारण उदाहरण हो सकता है: (int पंक्ति = minR; पंक्ति
इस विस्तार यहाँ http://www.ddj.com/architect/184405252?pgno=1 में चर्चा की है
यह दिलचस्प था लेकिन एक अलग समस्या हल करता है। प्रश्नकर्ता ने उस बिंदु से पूछा कि सभी बिंदुओं की दूरी को कम करता है। डीडीजे लेख एक दूसरे के करीब दो बिंदुओं को पाता है। –
इस बंद न करें, ज्यामिति एल्गोरिदम ढेर अतिप्रवाह –
यह होमवर्क है के दायरे के भीतर पूरी तरह से कर रहे हैं? इसके अलावा, आप किस भाषा में इसे लागू करने की कोशिश कर रहे हैं? – Piskvor
नहीं, यह होमवर्क नहीं है। मैं कम्प्यूटेशनल ज्यामिति पर एल्गोरिदम का अध्ययन कर रहा हूं। तो मुझे संदेह हो गया। मैं इसे सी – nowonder