डिजस्ट्रा के एल्गोरिदम: मेमोरी खपत

Question

मेरे पास this website पर कोड के आधार पर डिजस्ट्रा के एल्गोरिदम का कार्यान्वयन है। असल में, मेरे पास कई नोड्स हैं (10000 कहें), और प्रत्येक नोड में अन्य नोड्स के लिए 1 से 3 कनेक्शन हो सकते हैं।

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

इस मामले में, एल्गोरिदम का उपयोग शुरुआती बिंदु से अन्य सभी नोड्स तक होप्स की सबसे छोटी संख्या को खोजने के लिए किया जा रहा है। और यह 10,000 नोड्स के लिए अच्छी तरह से काम करता है। मेरी समस्या यह है कि, जैसे कि नोड्स की संख्या बढ़ जाती है, 2 मिलियन की ओर कहते हैं, मैं ग्राफ बनाने की कोशिश करते समय अपने सभी कंप्यूटर मेमोरी का उपयोग करता हूं।

क्या किसी को मेमोरी पदचिह्न को कम करने के लिए एल्गोरिदम को लागू करने का वैकल्पिक तरीका पता है, या वहां कोई और एल्गोरिदम है जो कम स्मृति का उपयोग करता है?

Answer 1

उपरोक्त आपकी टिप्पणी के अनुसार, आप distance matrixlong dist[GRAPHSIZE][GRAPHSIZE] के साथ ग्राफ के किनारों का प्रतिनिधित्व कर रहे हैं। इसमें O(n^2) मेमोरी लगेगी, जो n के बड़े मूल्यों के लिए बहुत अधिक है। यह निष्पादन समय के मामले में भी एक अच्छा प्रतिनिधित्व नहीं है जब आपके पास केवल किनारों की एक छोटी संख्या होती है: इससे डिजस्ट्रा के एल्गोरिदम O(n^2) समय ले सकते हैं (जहां n नोड्स की संख्या है) जब यह संभावित रूप से तेज़ हो सकता है, डेटा संरचनाओं का इस्तेमाल किया।

चूंकि आपके मामले में आपने कहा था कि प्रत्येक नोड केवल 3 अन्य नोड्स से जुड़ा हुआ है, तो आपको इस मैट्रिक्स का उपयोग नहीं करना चाहिए: इसके बजाय, प्रत्येक नोड के लिए आपको नोड्स की एक सूची को स्टोर करना चाहिए, यह उससे जुड़ा हुआ है। फिर जब आप नोड के पड़ोसियों पर जाना चाहते हैं, तो आपको बस इस सूची में फिर से भरना होगा।

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

Answer 2

तुम सच में भी अपने ग्राफ प्रतिनिधित्व पर minimizations के साथ स्मृति खर्च नहीं उठा सकते हैं, तो, आप, डिज्कस्ट्रा के एल्गोरिथ्म के एक भिन्नता का विकास एक विभाजन पर विचार और विधि को जीत सकते हैं।

विचार विभाजित डेटा को छोटे टुकड़ों में विभाजित करना है, ताकि आप प्रत्येक खंड में डिजस्ट्रा के एल्गोरिदम को इसके प्रत्येक बिंदु के लिए निष्पादित कर सकें।

इन मामूली हिस्सों में उत्पन्न प्रत्येक समाधान के लिए, इसे किसी अन्य डेटा खंड में एक अद्वितीय नोड के रूप में मानें, जिससे आप डिजस्ट्रा का एक और निष्पादन शुरू करेंगे।

उदाहरण के लिए, पर विचार अंक नीचे:

.B  .C 
        .E 
.A   .D 
     .F     .G 

आप किसी एक नोड, कहते हैं, दो हॉप्स के भीतर के सबसे करीब अंक का चयन कर सकते हैं, और फिर, ग्राफ बढ़ाया के हिस्से के रूप समाधान का उपयोग पर विचार पूर्व अंक बिंदुओं के केवल एक सेट के रूप में, डिजस्ट्रा समाधान की परिणामी दूरी के बराबर दूरी के साथ।

आप D से शुरू कहते हैं:

• D भीतर करने के लिए closest points चयन एक number of hops दिया;
• चयनित प्रविष्टियों पर डिजस्ट्रा के एल्गोरिदम का उपयोग करें, D से शुरू हो रहा है;
• केंद्रीय नोड D के साथ ग्राफ़ के रूप में समाधान का उपयोग करें और सबसे कम पथों में अंतिम नोड्स के रूप में सीधे D से जुड़े नोड्स के रूप में;
• ग्राफ़ का विस्तार करें, जब तक सभी नोड्स पर विचार नहीं किया जाता है तब तक एल्गोरिदम दोहराएं।

एक महंगा अतिरिक्त संसाधन वहाँ हालांकि यहां, आप कर पाएंगे, स्मृति सीमा पार, और, अगर आप कुछ अन्य मशीनों है, तो आप भी प्रक्रियाओं वितरित कर सकते हैं।

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

Answer 3

मुझे बढ़ावा :: ग्राफ बहुत पसंद है। यह स्मृति खपत बहुत सभ्य है (मैंने इसे 10 मिलियन नोड्स और 2 जीबी रैम के साथ सड़क नेटवर्क पर उपयोग किया है)।

इसमें डिजस्ट्रा कार्यान्वयन है, लेकिन यदि लक्ष्य इसे लागू करना और समझना है, तो आप अभी भी अपने ग्राफ प्रतिनिधित्व (मैं आसन्नता सूची का सुझाव देते हैं) का उपयोग कर सकते हैं और अपने परिणाम की तुलना सुनिश्चित कर सकते हैं कि आपका परिणाम सही है।

कुछ लोगों ने अन्य एल्गोरिदम का उल्लेख किया। मुझे नहीं लगता कि यह स्मृति उपयोग पर एक बड़ी भूमिका निभाएगा, लेकिन गति में अधिक संभावना है। 2 एम नोड्स, यदि टोपोलॉजी सड़क-नेटवर्क के नजदीक है, तो चलने का समय एक नोड से दूसरे तक एक सेकंड से भी कम होगा।

http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/index.html