अन्य सभी दिए गए बिंदुओं से न्यूनतम मैनहट्टन दूरी के साथ सभी बिंदु [अनुकूलित]

Question

समस्या यहां सभी पूर्णांक बिंदुओं का सेट ढूंढना है जो अंक के दिए गए सेट से सभी मैनहट्टन दूरी पर न्यूनतम राशि प्रदान करते हैं!

उदाहरण के लिए:

की सुविधा देता है अंक की दी गई सेट {P1, P2, पी 3 ... Pn}

बुनियादी समस्या एक बिंदु का कहना है कि एक्स जो सभी दूरी पर कम से कम राशि के लिए होता है मिल रहा है अंक से {पी 1, पी 2, पी 3 ... पीएन}।

i.e. | पी 1-एक्स | + | पी 2 एक्स | + .... + | पीएन-एक्स | = डी, जहां डी सभी एक्स

एक कदम आगे बढ़ने पर न्यूनतम होगा, एक्स के ऊपर एक से अधिक मूल्य शर्त से संतुष्ट हो सकता है। यानी एक से अधिक एक्स संभव हो सकते हैं जो एक ही मूल्य डी दे देंगे। इसलिए, हमें ऐसे सभी एक्स को खोजने की आवश्यकता है।

कोई मूल दृष्टिकोण जो किसी के बारे में सोच सकता है वह इनपुट के मध्य और फिर बल बल this post

लेकिन इस तरह के दृष्टिकोण के साथ समस्या यह है कि: यदि मध्य दो मूल्यों को बहुत अलग करता है, तो हम सभी बिंदुओं को मजबूर कर देते हैं जो कि दिए गए समय में कभी नहीं चलेंगे।

तो, क्या कोई अन्य दृष्टिकोण है जो परिणाम तब भी देगा जब अंक बहुत दूर हैं (जहां औसत 10^9 के क्रम में एक सीमा प्रदान करता है)।

Answer 1

यदि औसत आपको 10^9 के आदेश का अंतराल देता है तो उस अंतराल में प्रत्येक बिंदु किसी अन्य के समान होता है।

तो आप उन बिंदुओं के बाद जो करना चाहते हैं उसके आधार पर आप या तो उस सीमा में सीमा या गणना अंक वापस कर सकते हैं। इसके चारों ओर कोई रास्ता नहीं ..

जाहिर है दो आयामों में आप एक bouding आयत, 3 आयामों में प्रत्येक आयाम के लिए प्राप्त तिथियों के बाउंडिंग घनाभ एक कार्तीय उत्पाद आदि ..

परिणाम हमेशा रहेंगे मिलेगा, इसलिए आप परिणामस्वरूप उन श्रेणियों की एक सूची वापस कर सकते हैं।

Answer 2

चूंकि मैनहट्टन दूरी में प्रत्येक घटक अलग-अलग योगदान देता है, तो आप उन्हें अलग से भी विचार कर सकते हैं। इष्टतम उत्तर है (औसत (एक्स), औसत (वाई))। आपको पूर्णांक समाधान के लिए इस बिंदु को देखने की आवश्यकता है।

नोट: उत्तर देने के दौरान मैंने आपके प्रश्न को ठीक से नहीं पढ़ा। मेरा जवाब अभी भी है, लेकिन शायद आप पहले से ही इस समाधान के बारे में जानते थे।

Answer 3

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

---

सबूत: यदि हम अंकों की सम संख्या है, वहाँ दो माध्यिकाओं हो जाएगा। दो मध्यस्थों के बीच एक बिंदु के पास बाएं और एन/2 अंक दाएं कोने के लिए एन/2 अंक होंगे, और एस के उन बिंदुओं के लिए कुल दूरी होगी।

यदि हम यह बाईं ओर एक बिंदु को स्थानांतरित, एस ऊपर से n/2 नीचे से n/2 जाना होगा (हम सही-सबसे अधिक अंक से अलग हो रहे के बाद से) और (हम कर रहे हैं के बाद से बाएं सबसे अधिक बिंदुओं की ओर बढ़ते हुए), इसलिए कुल मिलाकर एस एक ही रहता है। यह तब तक सच रहता है जब तक हम बाएं सबसे अधिक औसत बिंदु पर नहीं आते। जब हम बाईं ओर सबसे अधिक मध्य बिंदु के बाईं ओर जाते हैं, तो अब हमारे पास दाईं ओर (एन/2 + 1) अंक होते हैं, और (एन/2 - 1) बाईं ओर बिंदु होते हैं, इसलिए एस दो से ऊपर जाता है। बाईं ओर जारी रखने से केवल एस आगे बढ़ेगा।
एक ही तर्क से, दाएं-दाएं मध्यस्थ के दाईं ओर सभी बिंदुओं में भी उच्च एस

यदि हमारे पास अंक की एक विषम संख्या है, तो केवल एक औसत है। उपरोक्त के समान तर्क का उपयोग करके, हम दिखा सकते हैं कि इसका सबसे कम मूल्य एस

Answer 4

हां मुझे यह भी लगता है कि ग्रिड पर एन अंकों की विषम संख्या के लिए, केवल एक बिंदु (यानी माध्यम) होगा जो अन्य सभी बिंदुओं से मैनहट्टन दूरी की न्यूनतम राशि होगी।

एन के मूल्य के लिए, परिदृश्य थोड़ा अलग होगा।

मेरे हिसाब से अगर दो सेट X = {1,2} and Y= {3,4} उनके कार्तीय उत्पाद हमेशा 4.

यानी X × Y = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)} हो जाएगा। यही वह है जिसे मैंने अभी तक समझा है।

मूल्यों की संख्या के लिए हम हमेशा "मध्य दो" मूल्यों को मेडियन के रूप में लेते हैं। वाई से एक्स और 2 से 2 लेना हमेशा 4 अंक के कार्टेशियन उत्पाद को वापस कर देगा।

अगर मैं गलत हूं तो मुझे सुधारें।