के साथ सभी बिंदुओं को जोड़ने के लिए एल्गोरिदम मेरे पास बिंदुओं और दूरी की एक जोड़ी है जो प्रत्येक जोड़ी के लिए लागू होती है। मैं न्यूनतम कुल दूरी के साथ सभी बिंदुओं को एक साथ जोड़ना चाहता हूं। क्या आप इसके लिए उपयोग किए जा सकने वाले मौजूदा एल्गोरिदम के बारे में जानते हैं?न्यूनतम कुल दूरी
प्रत्येक बिंदु कई अंक से जोड़ा जा सकता है, तो यह हमेशा की तरह "विक्रेता यात्रा कार्यक्रम" समस्या :)
धन्यवाद नहीं है!
आप जो चाहते हैं वह है।
दो सबसे आम एल्गोरिदम एक उत्पन्न करने के लिए कर रहे हैं:
एल्गोरिदम जिसे आप ढूंढ रहे हैं उसे न्यूनतम स्पैनिंग पेड़ कहा जाता है। पानी, टेलीफोन या बिजली ग्रिड के लिए न्यूनतम लागत ढूंढना उपयोगी होता है। प्राइम का एल्गोरिदम या क्रस्कल एल्गोरिदम है। आईएमओ प्राइम के एल्गोरिदम को समझना थोड़ा आसान है।
http://en.wikipedia.org/wiki/Minimum_spanning_tree आप कम से कम फैले पेड़ के बारे में अधिक जानकारी पा सकते हैं, ताकि आप इसे करने के लिए अनुकूलित कर सकते हैं अपनी समस्या हल करें।
डिज्कस्ट्रा एल्गोरिथ्म पर एक नज़र डालें:
डिज्कस्ट्रा एल्गोरिथ्म, 1956 में डच कंप्यूटर वैज्ञानिक Edsger डिज्कस्ट्रा द्वारा नियोजित और 1959 में प्रकाशित, एक ग्राफ खोज एल्गोरिथ्म है कि एक ग्राफ के लिए एकल स्रोत कम से कम पथ समस्या का हल है nonnegative किनारे पथ लागत के साथ, एक सबसे छोटा रास्ता पेड़ का उत्पादन। यह एल्गोरिदम अक्सर रूटिंग में और अन्य ग्राफ एल्गोरिदम में एक सबराउटिन के रूप में प्रयोग किया जाता है।
http://en.wikipedia.org/wiki/Dijkstra 's_algorithm
के रूप में अन्य लोगों ने कहा, minimum spanning tree (MST) आप एक न्यूनतम दूरी उप ग्राफ अपने अंक के सभी जोड़ता है के रूप में करने की अनुमति देगा।
आपको पहले अपने डेटा सेट के लिए ग्राफ बनाने की आवश्यकता होगी। एक अप्रत्यक्ष ग्राफ को कुशलता से बनाने के लिए आप अपने बिंदु सेट के Delaunay triangulation की गणना कर सकते हैं। त्रिभुज से ग्राफ तक रूपांतरण तब काफी शाब्दिक होता है - त्रिभुज में कोई भी किनारा ग्राफ में एक बढ़त है, जो त्रिभुज किनारे की लंबाई से भारित होता है।
एमएसटी (प्राइम/क्रस्कल के O(E*log(V))) और डेलाउने त्रिकोण (विभाजन और O(V*log(V))) चरणों के लिए कुशल एल्गोरिदम हैं, इसलिए प्रभावी समग्र दृष्टिकोण संभव हैं।
उम्मीद है कि इससे मदद मिलती है।
इसे न्यूनतम वजन वाले पेड़ की समस्या के रूप में व्याख्या किया जा सकता है। मुझे यकीन नहीं है कि यह दृष्टिकोण करने का सबसे अच्छा तरीका है लेकिन यह एक तरीका है। – biziclop
यदि दूरी मीट्रिक प्रत्येक तीन बिंदु x, y और z के लिए डी (x, z) <= D (x, y) + D (y, z) का पालन करता है तो मूल रूप से प्रत्येक जोड़ी बिंदुओं को जोड़ने से कुल न्यूनतम दूरी मिलती है। मुझे लगता है कि आपको अपने प्रश्न को थोड़ा सा परिशोधित करने की आवश्यकता है। – ElKamina
दूरी मीट्रिक सभी कनेक्शन की लंबाई का योग हो सकता है। –