रैखिक समय के लिए दिक्जस्त्र

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

प्रागितिहास

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

और इसलिए यह पता चला कि कॉम्बिनेटरिक्स समस्या में प्रदर्शन समस्या को हल करना संभव था, लेकिन अनुरोध को संसाधित करने के लिए अधिकांश समय गैर-कैश्ड रास्तों की खोज पर खर्च किया गया था। समस्या इस तथ्य से जटिल थी कि मॉस्को में ओस्म रोड का ग्राफ काफी बड़ा है (आधा मिलियन नोड्स और 1.1 मिलियन आर्क)।

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

लघुगणक समय के लिए दिक्जस्त्र

हर कोई जानता है, लेकिन जो जानता है, पढ़ते हैं कि डायजेस्ट्रा के एल्गोरिथ्म को सम्मिलित करने और हटाने की लघुगणक जटिलता के साथ एक कतार का उपयोग करके फॉर्म ओ (एन लॉग (एन) + एम लॉग (एन)) की जटिलता हो सकती है। फाइबोनैचि हीप का उपयोग करते समय, जटिलता को O (n * log (n) + m) तक कम किया जा सकता है, लेकिन फिर भी रैखिक नहीं है, लेकिन मैं चाहूंगा।

सामान्य स्थिति में, कतार एल्गोरिथ्म का वर्णन इस प्रकार है:

करते हैं:

• V ग्राफ के सिरों का समूह है
• ई ग्राफ के किनारों का समूह है
• w [i, j] नोड I से नोड j तक के किनारे का वजन है
• a - खोज की शुरुआत करें
• क्यू-वर्टेक्स कतार
• d [i] - i-th नोड से दूरी
• d [a] = 0, अन्य सभी के लिए d [i] = + inf

जबकि q खाली नहीं है:

• v, q के न्यूनतम d [v] के साथ शीर्ष है
• सभी वर्टीकल यू के लिए जिसके लिए वर्टेक्स v से E का संक्रमण है
  
  • अगर d [u]> w [vu] + d [v]
    
    • दूर क्यू से यू को दूर करें [यू]
    • d [u] = w [vu] + d [v]
    • दूरी d [u] के साथ u को q जोड़ें
• q से v निकालें

यदि हम एक कतार के रूप में लाल-काले पेड़ का उपयोग करते हैं, जहां प्रवेश (n) में सम्मिलन और विलोपन होता है, और न्यूनतम तत्व की खोज लॉग (n) में समान है, तो एल्गोरिथ्म की जटिलता हे (n लॉग + (n + + लॉग) (n)) ।

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

हैश टेबल को सॉर्ट करें

दिक्ज़स्ट्रा एल्गोरिथ्म के रैखिक समय को कम करने के लिए, एक डेटा संरचना प्रस्तावित है, जो मान के रूप में नोड संख्या (नोड_आईडी) के साथ एक हैश तालिका है। मैं ध्यान देता हूं कि डी सरणी की आवश्यकता गायब नहीं होती है, इसे निरंतर समय में ith नोड की दूरी प्राप्त करने के लिए अभी भी आवश्यक है।

नीचे दिया गया आंकड़ा प्रस्तावित संरचना का एक उदाहरण दिखाता है।

चलिए प्रस्तावित डेटा संरचना के चरणों में वर्णन करते हैं:

• नोड यू को सेल में d [u] // बकेट_साइज़ के बराबर संख्या के साथ लिखा जाता है, जहाँ बकेट_साइज़ सेल की शक्ति है (उदाहरण के लिए, 20 मीटर, यानी 0 पर सेल में नोड्स की दूरी होगी जिसमें दूरी होगी [0, 20] मीटर) )
• पहले गैर-खाली सेल के अंतिम नोड, अर्थात न्यूनतम तत्व निकालने का संचालन ओ (1) में किया जाएगा। पहले गैर-खाली सेल (min_el) की संख्या की पहचानकर्ता की वर्तमान स्थिति को बनाए रखना आवश्यक है।
• सम्मिलन ऑपरेशन को सेल के अंत में एक नया नोड संख्या जोड़कर और ओ (1) निष्पादित करके भी किया जाता है, क्योंकि सेल नंबर की गणना एक स्थिर समय में होती है।
• डिलीट ऑपरेशन, जैसा कि हैश टेबल के मामले में, सामान्य गणन संभव है, और कोई एक धारणा बना सकता है और कह सकता है कि एक छोटे सेल आकार के साथ यह भी ओ (1) है। यदि आप मेमोरी को याद नहीं करते हैं (सिद्धांत रूप में, और बहुत अधिक की आवश्यकता नहीं है, तो n द्वारा एक और सरणी), तो आप सेल में पदों की एक सरणी बना सकते हैं। इस स्थिति में, यदि तत्व को सेल के बीच में हटा दिया जाता है, तो सेल में अंतिम मान को हटाए गए स्थान पर ले जाना आवश्यक है।
• न्यूनतम तत्व चुनते समय एक महत्वपूर्ण बिंदु: यह केवल कुछ संभाव्यता के साथ न्यूनतम है, लेकिन, एल्गोरिथ्म min_el सेल पर तब तक दिखेगा जब तक कि यह खाली न हो जाए और बाद में वास्तविक न्यूनतम तत्व पर विचार किया जाएगा, और अगर हमने गलती से नोड से दूरी के मान को अपडेट किया है, तो न्यूनतम, फिर न्यूनतम से सटे नोड्स फिर से कतार में हो सकते हैं और उनके लिए दूरी सही होगी, आदि।
• आप खाली सेल को min_el तक हटा सकते हैं, जिससे मेमोरी की बचत होगी। इस स्थिति में, क्यू क्यू से नोड v को हटाने के लिए सभी आसन्न नोड्स पर विचार करने के बाद ही किया जाना चाहिए।
• और आप सेल पावर, सेल साइज़ और सेल की संख्या बढ़ाने के पैरामीटर भी बदल सकते हैं, जब आपको हैडर टेबल के आकार को बढ़ाने की आवश्यकता होती है।

माप के परिणाम

मास्को के ओएसएम मानचित्र पर चेक पोस्ट किए गए थे, पोस्टग्रेज में osm2po के माध्यम से उतार दिया, और फिर स्मृति में लोड किया गया। टेस्ट जावा में लिखे गए थे। ग्राफ के 3 संस्करण थे:

• स्रोत ग्राफ - 0.43 मिलियन नोड्स, 1.14 मिलियन आर्क्स
• 173k नोड्स और 750k आर्क्स के साथ ग्राफ के संकुचित संस्करण
• ग्राफ के संकुचित संस्करण के पैदल यात्री संस्करण, 450k आर्क्स, 100k नोड्स।

नीचे ग्राफ़ के विभिन्न संस्करणों पर माप के साथ एक तस्वीर है:

वर्टेक्स और ग्राफ़ के आकार को फिर से देखने की संभावना की निर्भरता पर विचार करें:

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

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

प्रस्तावित डेटा संरचना का स्रोत कोड लिंक पर स्थित है

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