रेखा खंडों में सेट से कनेक्ट बिंदु

मुझे एक कार्य दिया गया है जहां मुझे 2 डी विमान में सभी बिंदुओं को जोड़ना है। मिलने के लिए चार स्थितियां हैं:

  1. सभी सेगमेंट की लंबाई एक साथ जुड़ गई है न्यूनतम होना चाहिए।
  2. एक बिंदु केवल एक पंक्ति खंड का हिस्सा हो सकता है।
  3. रेखा सेगमेंट अंतर नहीं कर सकते
  4. सभी बिंदुओं का उपयोग किया जाना चाहिए (कोई अकेला नहीं छोड़ा जा सकता है, लेकिन केवल तभी इसे टाला जा सकता है)

Image to visualize the problem: enter image description here

गलत छवि सही ढंग से जुड़े बिंदुओं, हालांकि कुल लंबाई बड़ी है कि बाईं ओर एक है।

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

9
मुझे इसके बारे में बहुत कुछ पता नहीं है, लेकिन अगर आपने के-साधन विश्लेषण के साथ शुरुआत की है ( en.wikipedia.org/wiki/K-means_clustering ) जहां k = n/2 ? n अंक की संख्या होने के नाते। आपके उदाहरण पर रनिंग के-साधन हर बार जब मैंने कोशिश की तो सही परिणाम उत्पन्न करना प्रतीत होता था। क्या आपके पास अंक के बड़े संग्रह के साथ अधिक हल किए गए उदाहरण हैं?
जोड़ा लेखक גלעד ברקן, स्रोत

4 उत्तर

मैं कहूंगा कि यह प्रसिद्ध यात्रा विक्रेता समस्या का विस्तार है।

एक अच्छी तकनीक (यदि थोड़ा पुराना है) एक अनुरूपित एनीलिंग ऑप्टिमाइज़ेशन तकनीक का उपयोग करना है।

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

1
जोड़ा

I would start with a Delaunay triangulation of the point set. This should already give you the nearest neighbor connections of each point without any intersections. In the next step I'd look at the triangles that result from the triangulation - the convenient property here is that based on your ruleset you can pick exactly one side from each triangle and remove the remaining two from the selection.

अब जो समस्या बनी हुई है वह उन किनारों को चुनना है जो आपको सबसे छोटी कुल राशि देते हैं, जो निश्चित रूप से सबसे छोटी तरफ नहीं रहेंगे क्योंकि वह पहले से ही पड़ोसी त्रिकोण द्वारा अवरुद्ध हो सकता है। मैं एक लालची दृष्टिकोण से शुरू करूंगा, हमेशा छोटे शेष किनारे को चुनता हूं जिसे अभी तक पड़ोसी त्रिकोणों द्वारा अवरुद्ध नहीं किया गया है।

Edit: In the next step you retrieve a list of all the edges in that triangulation and sort them by length. You also make another list in which you count the amount of connections each point has. Now you iterate through the edge list going from the longest edge to the shortest one and check the two points it connects in the connection count list: if each of the points has still more than 1 connection left, you can discard the edge and decrement the connection count for the two points involved. If at least one of the points has only one connection left, you have got yourself one of the edges you are looking for. You repeat the process until there are no edges left and this should hopefully give you the smallest possible edge sum.

अगर मुझे गलत नहीं लगता है तो यह समस्या एनपीएस-हार्ड है जो knapsack समस्या से कम है, इसलिए मुझे यकीन नहीं है कि यह समाधान वास्तव में आपको सबसे अच्छा संभव बनाता है।

1
जोड़ा

वाह, यह एक मुश्किल है। यह मिलने के लिए बहुत सी स्थितियां हैं।

मुझे प्रोग्रामिंग दृष्टिकोण से लगता है, "सरलतम" समाधान वास्तव में केवल लूप के माध्यम से हो सकता है, पिछली 3 स्थितियों को पूरा करने वाली सभी संभावनाओं को ढूंढ सकता है, और कुल लम्बाई रिकॉर्ड कर सकता है जैसे आप लूप करते हैं, और केवल सबसे छोटी लंबाई के साथ चुनें अंत में - क्रूर बल, अनुमान और जांच। मुझे लगता है कि आप अपने ओपी में इसका जिक्र कर रहे थे जब आपने "व्यापक रेखा और सभी संभावनाओं के पेड़ का निर्माण" का उल्लेख किया था। यह दृष्टिकोण बहुत कम्प्यूटेशनल रूप से महंगा है, लेकिन यदि कोड सही लिखा गया है, तो इसे हमेशा अंत में काम करना चाहिए।

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

0
जोड़ा

संभावित सिद्धांतों में से एक ग्राफ सिद्धांत का उपयोग करना है।

एक द्विपक्षीय ग्राफ जी का निर्माण करें, जैसे कि प्रत्येक बिंदु की प्रतिलिपि दोनों भागों में होती है। अब i = j के साथ किनारों को weight = i == j के साथ रखें। अनंतता: दूरी [i] [जे] । ग्राफ में न्यूनतम वजन अधिकतम मिलान आपकी वांछित विन्यास होगी।

Notice that since this is on a euclidean 2D plane, the resulting "edges" of the matching will not intersect. Let's say that edges AB and XY intersect for points A, B, X, Y. Then the matching is not of the minimum weight, because either AX, BY or AY, BX will produce a smaller total weight without an intersection (this comes from triangle inequality a+b > c)

0
जोड़ा