डिजस्ट्रा का एल्गोरिदम क्यों कम-कुंजी का उपयोग करता है?

Question

डिज्कस्ट्रा एल्गोरिथ्म के लिए मैं था के रूप में

while pqueue is not empty: 
    distance, node = pqueue.delete_min() 
    if node has been visited: 
     continue 
    else: 
     mark node as visited 
    if node == target: 
     break 
    for each neighbor of node: 
     pqueue.insert(distance + distance_to_neighbor, neighbor) 

इस प्रकार सिखाया गया था लेकिन मैं एल्गोरिथ्म के बारे में कुछ पढ़ने कर रहा हूँ, और संस्करणों की एक बहुत कुछ मैं देख रहा हूँ उपयोग कमी-कुंजी के रूप में सम्मिलित करने के लिए विरोध किया।

यह क्यों है, और दोनों दृष्टिकोणों के बीच अंतर क्या हैं?

Answer 1

नोड्स को पुन: सम्मिलित करने के बजाए कमी-कुंजी का उपयोग करने का कारण प्राथमिकता कतार में नोड्स की संख्या को छोटा रखना है, इस प्रकार प्राथमिकता कतार की कुल संख्या कम हो जाती है और प्रत्येक प्राथमिकता कतार शेष की लागत कम हो जाती है।

डिजस्ट्रा के एल्गोरिदम के कार्यान्वयन में जो अपनी नई प्राथमिकताओं के साथ प्राथमिकता कतार में नोड्स को फिर से जोड़ता है, ग्राफ में प्रत्येक एम किनारों के लिए प्राथमिकता कतार में एक नोड जोड़ा जाता है। इसका मतलब यह है वहाँ हे की कुल क्रम देने मीटर को कतारबद्ध संचालन और प्राथमिकता कतार पर मीटर विपंक्ति संचालन कर रहे हैं कि, (एम टी _ई + m टी _घ), जहां टी _ई समय में enqueue करने के लिए आवश्यक है प्राथमिकता कतार और टी _डी प्राथमिकता कतार से निकालने के लिए आवश्यक समय है।

डिजस्ट्रा के एल्गोरिदम के कार्यान्वयन में जो कमी-कुंजी का समर्थन करता है, नोड्स धारण करने वाली प्राथमिकता कतार में एन नोड्स के साथ शुरू होता है और एल्गोरिदम के प्रत्येक चरण पर एक नोड हटा देता है। इसका मतलब है कि ढेर डेक्यू की कुल संख्या एन है। प्रत्येक नोड में प्रत्येक किनारे के लिए संभावित रूप से इसे एक बार कम करने के लिए कहा जाता है, इसलिए कम से कम कमी की चाबियां अधिकतम मीटर पर होती हैं। इस का एक क्रम (एन टी _ई + n टी _घ + m टी _{कश्मीर}) देता है, जहां टी _{कश्मीर} समय को कम महत्वपूर्ण कॉल करने के लिए आवश्यक है।

तो रनटाइम पर इसका क्या प्रभाव पड़ता है? यह इस बात पर निर्भर करता है कि आप किस प्राथमिकता कतार का उपयोग करते हैं।

Queue   | T_e | T_d | T_k | w/o Dec-Key | w/Dec-Key 
---------------+--------+--------+--------+-------------+--------------- 
Binary Heap |O(log N)|O(log N)|O(log N)| O(M log N) | O(M log N) 
Binomial Heap |O(log N)|O(log N)|O(log N)| O(M log N) | O(M log N) 
Fibonacci Heap | O(1) |O(log N)| O(1) | O(M log N) | O(M + N log N) 

आप देख सकते हैं, प्राथमिकता कतारों के सबसे प्रकार के साथ, वहाँ वास्तव में नहीं asymptotic में एक फर्क है: यहाँ एक त्वरित तालिका जो यह दिखाती अलग प्राथमिकता कतारों और विभिन्न डिज्कस्ट्रा एल्गोरिथ्म कार्यान्वयन की समग्र runtimes है रनटाइम, और कमी-कुंजी संस्करण बहुत बेहतर करने की संभावना नहीं है। हालांकि, यदि आप प्राथमिकता कतार के Fibonacci heap कार्यान्वयन का उपयोग करते हैं, तो वास्तव में कमी-कुंजी का उपयोग करते समय डिजस्ट्रा का एल्गोरिदम असम्बद्ध रूप से अधिक कुशल होगा।

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

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

आशा है कि इससे मदद मिलती है!

Answer 2

2007 में, एक पेपर था जो कमी-कुंजी संस्करण और सम्मिलित संस्करण का उपयोग करने के बीच निष्पादन समय में मतभेदों का अध्ययन करता था।देखें http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

उनका मूल निष्कर्ष अधिकांश ग्राफों के लिए कमी-कुंजी का उपयोग नहीं करना था। विशेष रूप से स्पैस ग्राफ के लिए, गैर-कमी कुंजी कम-कुंजी संस्करण की तुलना में काफी तेज है। अधिक जानकारी के लिए पेपर देखें।