मैंने हाल ही में अपनी परियोजना में एकल स्रोत के सबसे कम पथ के लिए डिजस्ट्रा एल्गोरिदम का तीसरा संस्करण संलग्न किया था।सबसे तेज़ डिजस्ट्रा कार्यान्वयन क्या है जिसे आप जानते हैं (सी ++ में)?
मुझे एहसास है कि कई अलग-अलग कार्यान्वयन हैं जो प्रदर्शन में दृढ़ता से भिन्न होते हैं और बड़े ग्राफ में परिणाम की गुणवत्ता में भिन्न होते हैं। मेरे डेटा सेट (> 100.000 शिखर) के साथ रनटाइम 20 मिनट से कुछ सेकंड तक भिन्न होता है। सबसे कम पथ भी 1-2% से भिन्न होते हैं।
आपको सबसे अच्छा कार्यान्वयन कौन सा पता है?
संपादित करें: मेरे डेटा एक हाइड्रोलिक नेटवर्क, प्रति नोड 1 से 5 कोने के साथ है। यह एक सड़क मानचित्र के तुलनीय है। मैंने पहले से ही त्वरित एल्गोरिदम (सभी शेष नोड्स के लिए क्रमबद्ध सूची का उपयोग करके) में कुछ संशोधन किए हैं और अब एक ही समय में एक ही परिणाम में मिलते हैं। मैंने थोड़ी देर के लिए ऐसी चीज की खोज की है। मुझे आश्चर्य है कि ऐसा कार्यान्वयन पहले से मौजूद है या नहीं।
मैं परिणामों में मामूली मतभेदों की व्याख्या नहीं कर सकता। मुझे पता है कि डिजस्ट्रा ह्युरिस्टिक नहीं है, लेकिन सभी कार्यान्वयन सही प्रतीत होते हैं। तेज समाधानों के परिणाम कम पथ के साथ होते हैं। मैं विशेष रूप से डबल परिशुद्धता गणित का उपयोग करता हूं।
संपादित 2: मुझे पता चला कि पाए गए पथ में अंतर वास्तव में मेरी गलती है। मैंने कुछ शिखर (केवल एक दिशा में मान्य) के लिए विशेष हैंडलिंग डाली थी और इसके बारे में अन्य कार्यान्वयन में भूल गए थे।
लेकिन im अभी भी आश्चर्य की तुलना में अधिक है कि डिज्कस्ट्रा निम्नलिखित परिवर्तन से नाटकीय रूप से त्वरित किया जा सकता है:, यह आप इस एक छोटा सा बदल लेते हैं
MyListType toDoList; // List sorted by smallest distance
InsertAllNodes(toDoList);
while(! toDoList.empty())
{
MyNodeType *node = *toDoList.first();
toDoList.erase(toDoList.first());
...
}
: सामान्य एक डिज्कस्ट्रा एल्गोरिथ्म में की तरह एक पाश में शामिल है बेहतर ही काम करता है, लेकिन करता है:
MyListType toDoList; // List sorted by smallest distance
toDoList.insert(startNode);
while(! toDoList.empty())
{
MyNodeType *node = *toDoList.first();
toDoList.erase(toDoList.first());
for(MyNeigborType *x = node.Neigbors; x != NULL; x++)
{
...
toDoList.insert(x->Node);
}
}
ऐसा लगता है, कि इस संशोधन परिमाण के एक आदेश से क्रम, लेकिन प्रतिपादक के एक आदेश कम करता है। इसने मेरे रनटाइम फॉर्म 30 सेकेंड से 2 से कम कर दिया। मुझे किसी भी साहित्य में यह संशोधन नहीं मिल रहा है। यह भी स्पष्ट है कि कारण क्रमबद्ध सूची में निहित है। सम्मिलित/मिटाने से 100,000 तत्वों के साथ बहुत खराब प्रदर्शन होता है।
उत्तर:
मैं यह पाया googling अपने आप का एक बहुत कुछ करने के बाद। उत्तर स्पष्ट रूप से है: boost graph lib। आश्चर्यजनक - मुझे यह थोड़ी देर के लिए नहीं मिला था। यदि आपको लगता है कि डिजस्ट्रा कार्यान्वयन के बीच कोई प्रदर्शन भिन्नता नहीं है, तो wikipedia देखें।
मेरा एक दोस्त लगभग 3 मिनट में सी ++ में डिजस्ट्रा को कार्यान्वित कर सकता है। मैंने किसी भी तेजी से कार्यान्वयन के बारे में नहीं सुना है। – jbasko
मैं सुझाव दूंगा कि आप उन कार्यान्वयनों को जांचना चाहेंगे ... यदि वे सही हैं तो उन्हें सभी को एक ही सबसे छोटा रास्ता वापस करना चाहिए ... डिजस्ट्रा का एल्गोरिदम हेरिस्टिक नहीं है ... – jerryjvl
सबसे कम पथों में अंतर का परिणाम हो सकता है डबल परिशुद्धता गणित का उपयोग करते हुए, युगल के लंबे अनुक्रमों को संक्षेप में त्रुटियों को गोल करने के कारण। संक्षेप में एक अलग क्रम विभिन्न त्रुटियों का उत्पादन कर सकता है। क्या आप पूर्णांक पर अपने कार्यान्वयन का परीक्षण कर सकते हैं? –