लगातार अंक के बीच न्यूनतम यूक्लिडियन दूरी को क्रमबद्ध करना

Question

3 डी कार्टेशियन अंतरिक्ष में बिंदुओं के एक सेट को देखते हुए, मैं एक एल्गोरिदम की तलाश कर रहा हूं जो इन बिंदुओं को क्रमबद्ध करेगा, जैसे न्यूनतम यूक्लिडियन दूरी दो के बीच की दूरी लगातार अंक अधिकतम किया जाएगा।

यह भी फायदेमंद होगा यदि एल्गोरिदम औसत लगातार अंक के बीच यूक्लिडियन दूरी को अधिकतम करता है।

संपादित करें:

मैं https://cstheory.stackexchange.com/ पर crossposted और एक अच्छा जवाब मिल गया है। https://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin देखें।

Answer 1

आप ग्राफ द्वारा अपनी समस्या का मॉडल कर सकते हैं, अपने बिंदुओं के बीच रेखा खींच सकते हैं, अब आपके पास एक पूर्ण ग्राफ है, अब आपकी समस्या इस ग्राफ में सबसे लंबा रास्ता ढूंढ रही है जो एनपी-हार्ड है, longest path के लिए विकी देखें।

असल में मैंने समस्या के दूसरे भाग का जवाब दिया, औसत को अधिकतम किया, जिसका अर्थ है कि ग्राफ के प्रत्येक नोड से जो पथ होता है, यदि आप उन्हें 1/दूरी के रूप में भारित करते हैं तो यह एक यात्रा विक्रेता समस्या होगी (पथ की लंबाई को कम करें) और एनपी-हार्ड है। और इस मामले के लिए Metric TSP approximation देखने के लिए उपयोगी हो सकता है। गैर में

क्रमबद्ध अंक के बीच की दूरी और उन पर विचार:

Answer 2

यहाँ समाधान की लागत, जो शाखा और बाध्य या एक अधिक अविश्वसनीय अधूरा खोज एल्गोरिथ्म के लिए एक निर्माण खंड के रूप में काम कर सकते हैं के लिए एक निचली सीमा है - क्रमिक क्रम। अंक के सेटों का ट्रैक रखने के लिए http://en.wikipedia.org/wiki/Disjoint-set_data_structure का उपयोग करें, दो बिंदुओं के बीच एक लिंक से कनेक्ट होने पर दो सेट विलय करें। जब आप सभी बिंदुओं को एक सेट में विलय करते हैं तो उस बिंदु तक की सबसे छोटी दूरी की लंबाई एक पूर्ण समाधान में न्यूनतम दूरी तक ऊपरी सीमा होती है, क्योंकि एक आदर्श समाधान सभी बिंदुओं को एक में विलीन करता है। हालांकि आपकी ऊपरी सीमा एक पूर्ण समाधान के लिए न्यूनतम दूरी से अधिक हो सकती है, क्योंकि जिन लिंकों में आप शामिल हो रहे हैं, वे शायद एक पेड़ बनायेंगे, पथ नहीं।