Contraction hierarchies
कंप्यूटर विज्ञान में, संकुचन पदानुक्रम की विधि एक ग्राफ में सबसे छोटा मार्ग खोजने के लिए एक गति-वृद्धि तकनीक है। सबसे सहज अनुप्रयोग कार-नौवहन प्रणालियाँ हैंः एक उपयोगकर्ता सबसे तेज़ संभव मार्ग का उपयोग करके गाड़ी चलाना चाहता है। यहाँ अनुकूलित मीट्रिक यात्रा का समय है। छेदन को शीर्षों द्वारा दर्शाया जाता है, सड़क खंड उन्हें किनारों से जोड़ते हैं। किनारे का वजन सड़क के इस खंड के साथ गाड़ी चलाने में लगने वाले समय का प्रतिनिधित्व करता है। से एक तक का रास्ता किनारों (सड़क खंडों) का एक क्रम है; सबसे छोटा रास्ता वह है जिसमें सभी संभावित रास्तों के बीच किनारे के वजन का न्यूनतम योग होता है। ग्राफ में सबसे छोटे मार्ग की गणना डिजक्स्ट्रा के एल्गोरिदम का उपयोग करके की जा सकती है, लेकिन यह देखते हुए कि सड़क नेटवर्क में लाखों शीर्ष होते हैं, यह अव्यावहारिक है। संकुचन पदानुक्रम एक गति-वृद्धि विधि है जो सड़क नेटवर्क का प्रतिनिधित्व करने वाले ग्राफ के गुणों का दोहन करने के लिए अनुकूलित है। गति-वृद्धि एक पूर्व-प्रसंस्करण चरण में शॉर्टकट बनाकर प्राप्त की जाती है जिसका उपयोग फिर "महत्वहीन" शीर्षों को छोड़ने के लिए सबसे छोटे-पथ क्वेरी के दौरान किया जाता है। यह इस अवलोकन पर आधारित है कि सड़क नेटवर्क अत्यधिक पदानुक्रमित हैं। कुछ चौराहे, उदाहरण के लिए राजमार्ग जंक्शन, "अधिक महत्वपूर्ण" हैं और पदानुक्रम में ऊपर हैं, उदाहरण के लिए एक जंक्शन जो एक अंतिम छोर की ओर जाता है। दो महत्वपूर्ण जंक्शनों के बीच पूर्व संगणित दूरी को बचाने के लिए शॉर्टकट का उपयोग किया जा सकता है ताकि एल्गोरिथ्म को क्वेरी समय पर इन जंक्शनों के बीच पूर्ण पथ पर विचार न करना पड़े। संकुचन पदानुक्रम यह नहीं जानते कि मनुष्य किन सड़कों को "महत्वपूर्ण" मानते हैं (जैसे। राजमार्ग), लेकिन वे इनपुट के रूप में ग्राफ के साथ प्रदान किए जाते हैं और ह्यूरिस्टिक्स का उपयोग करके शीर्षों को महत्व देने में सक्षम होते हैं। संकुचन पदानुक्रम न केवल कार-नौवहन प्रणालियों में गति-वृद्धि एल्गोरिदम पर लागू होते हैं, बल्कि वेब-आधारित मार्ग योजनाकारों, यातायात अनुकरण और रसद अनुकूलन में भी लागू होते हैं। एल्गोरिदम के कार्यान्वयन सार्वजनिक रूप से ओपन सोर्स सॉफ्टवेयर के रूप में उपलब्ध हैं। एल्गोरिदम संकुचन पदानुक्रम (सीएच) एल्गोरिदम सबसे छोटी पथ समस्या के लिए एक दो-चरणीय दृष्टिकोण है जिसमें एक पूर्व-प्रसंस्करण चरण और एक प्रश्न चरण शामिल है। जैसे-जैसे सड़क नेटवर्क कभी-कभी बदलते हैं, प्रश्नों के उत्तर देने से पहले कुछ गणनाओं की पूर्व गणना करने के लिए अधिक समय (सेकंड से घंटे) का उपयोग किया जा सकता है। इस पूर्व संगणित डेटा का उपयोग करके, कई प्रश्नों का उत्तर बहुत कम समय (माइक्रोसेकंड) में दिया जा सकता है। इस गति को प्राप्त करने के लिए सीएच शॉर्टकट पर निर्भर करते हैं। एक शॉर्टकट दो शीर्षों को जोड़ता है और मूल ग्राफ में आसन्न नहीं है। इसके किनारे का वजन सबसे छोटे पथ पर किनारे के वजन का योग है। राजमार्ग से जुड़े दो बड़े शहरों पर विचार करें। इन दोनों शहरों के बीच, छोटे गाँवों और उपनगरों की ओर जाने वाले कई जंक्शन हैं। अधिकांश चालक एक शहर से दूसरे शहर जाना चाहते हैं-शायद एक बड़े मार्ग के हिस्से के रूप में-और रास्ते में निकास में से एक भी नहीं लेना चाहते हैं। इस सड़क लेआउट का प्रतिनिधित्व करने वाले ग्राफ में, प्रत्येक चौराहे को एक नोड द्वारा दर्शाया जाता है और किनारों को पड़ोसी चौराहों के बीच बनाया जाता है। इन दोनों शहरों के बीच की दूरी की गणना करने के लिए, एल्गोरिथ्म को रास्ते के सभी किनारों को पार करना पड़ता है, जिससे उनकी लंबाई बढ़ जाती है। इस दूरी की एक बार पूर्व गणना करने और इसे दो बड़े शहरों के बीच बनाए गए एक अतिरिक्त किनारे में संग्रहीत करने से हर बार इस राजमार्ग का मूल्यांकन करने के लिए गणना की बचत होगी। इस अतिरिक्त किनारे को "शॉर्टकट" कहा जाता है और वास्तविक दुनिया में इसका कोई समकक्ष नहीं है। संकुचन पदानुक्रम एल्गोरिथ्म को सड़क के प्रकारों के बारे में कोई जानकारी नहीं है, लेकिन यह निर्धारित करने में सक्षम है कि इनपुट के रूप में अकेले ग्राफ का उपयोग करके कौन से शॉर्टकट बनाए जाने हैं। प्रीप्रोसेसिंग चरण सीएच एल्गोरिथ्म खोज स्थान को कम करने के लिए प्रीप्रोसेसिंग चरण में बनाए गए शॉर्टकट पर निर्भर करता है-यह उन शीर्षों की संख्या है जिन्हें सीएच को क्वेरी समय पर देखना होता है। इसे प्राप्त करने के लिए, पुनरावृत्ति शीर्ष संकुचन किए जाते हैं। जब एक शीर्ष को संकुचित किया जाता है तो इसे अस्थायी रूप से ग्राफ से हटा दिया जाता है, और पड़ोसी शीर्षों की प्रत्येक जोड़ी के बीच एक शॉर्टकट बनाया जाता है यदि सबसे छोटा मार्ग शामिल है। यह निर्धारित करने की प्रक्रिया कि क्या और के बीच का सबसे छोटा मार्ग गवाह खोज कहलाता है। इसे उदाहरण के लिए केवल अभी तक अनुबंधित नोड्स का उपयोग करके आगे की खोज का उपयोग करने के लिए एक पथ की गणना करके किया जा सकता है। नोड क्रम इनपुट ग्राफ के शीर्षों को इस तरह से संकुचित किया जाना चाहिए जो संकुचन द्वारा ग्राफ में जोड़े गए किनारों की संख्या को कम करता है। चूँकि इष्टतम नोड क्रम एन. पी.-पूर्ण है, ह्यूरिस्टिक्स का उपयोग किया जाता है। नीचे-ऊपर और ऊपर-नीचे अनुसंधान मौजूद हैं। एक ओर, कम्प्यूटेशनल रूप से सस्ता बॉटम-अप ह्यूरिस्टिक्स उस क्रम को तय करता है जिसमें शीर्षों को लालची तरीके से संकुचित किया जाए; इसका मतलब है कि क्रम पहले से ज्ञात नहीं है, बल्कि पिछले संकुचन के पूरा होने के बाद संकुचन के लिए अगले नोड का चयन किया जाता है। दूसरी ओर टॉप-डाउन ह्यूरिस्टिक्स पहले नोड के अनुबंधित होने से पहले पूरे नोड के क्रम की पूर्व गणना करता है। यह बेहतर परिणाम देता है लेकिन अधिक पूर्व-प्रसंस्करण समय की आवश्यकता होती है। बॉटम-अप ह्यूरिस्टिक्स में, संकुचन के लिए अगले शीर्ष का चयन करने के लिए कारकों के संयोजन का उपयोग किया जाता है। चूंकि शॉर्टकट की संख्या प्राथमिक कारक है जो प्रीप्रोसेसिंग और क्वेरी रनटाइम को निर्धारित करता है, इसलिए हम इसे यथासंभव छोटा रखना चाहते हैं। सबसे महत्वपूर्ण शब्द जिसके द्वारा संकुचन के लिए अगले नोड का चयन किया जाता है, इसलिए एक नोड को संकुचित करते समय जोड़े गए किनारों की शुद्ध संख्या है। इसे इस प्रकार परिभाषित किया गया है कि शॉर्टकटों की संख्या कहाँ है जो अनुबंध किए जाने पर बनाए जाएंगे और किनारों की संख्या कहाँ होगी। अकेले इस मानदंड का उपयोग करते हुए, एक रैखिक पथ के परिणामस्वरूप एक रैखिक पदानुक्रम (कई स्तर) होगा और कोई शॉर्टकट नहीं बनाया जाएगा। पास के शीर्षों की संख्या पर विचार करके जो पहले से ही संकुचित हैं, एक समान संकुचन और एक सपाट पदानुक्रम (कम स्तर) प्राप्त किया जाता है। उदाहरण के लिए, यह प्रत्येक नोड के लिए एक काउंटर बनाए रखते हुए किया जा सकता है जिसे हर बार पड़ोसी शीर्ष को अनुबंधित करने पर बढ़ाया जाता है। फिर निचले काउंटर वाले नोडों को उच्च काउंटर वाले नोडों की तुलना में प्राथमिकता दी जाती है। दूसरी ओर, टॉप-डाउन ह्यूरिस्टिक्स बेहतर परिणाम देता है लेकिन अधिक पूर्व-प्रसंस्करण समय की आवश्यकता होती है। वे उन शीर्षों को वर्गीकृत करते हैं जो कई सबसे छोटे रास्तों का हिस्सा हैं जो केवल कुछ सबसे छोटे रास्तों के लिए आवश्यक रास्तों की तुलना में अधिक महत्वपूर्ण हैं। नेस्टेड विच्छेदन का उपयोग करके इसका अनुमान लगाया जा सकता है। एक नेस्टेड विच्छेदन की गणना करने के लिए, एक आवर्ती रूप से एक ग्राफ को दो भागों में अलग करता है, जिन्हें फिर दो भागों में विभाजित किया जाता है। अर्थात्, नोड्स का एक उपसमुच्चय खोजें जो ग्राफ से हटाए जाने पर लगभग समान आकार के दो विच्छेदित टुकड़ों में अलग हो जाते हैं। सभी नोड्स को नोड क्रम में अंतिम स्थान पर रखें और फिर और के लिए नेस्टेड विच्छेदन की पुनरावर्ती रूप से गणना करें, अंतर्ज्ञान यह है कि ग्राफ के एक आधे से ग्राफ के दूसरे आधे तक सभी प्रश्नों को छोटे विभाजक से गुजरने की आवश्यकता होती है और इसलिए इस विभाजक में नोड्स उच्च महत्व के होते हैं। नेस्टेड विच्छेदन की गणना सड़क नेटवर्क पर उनके छोटे विभाजक के कारण कुशलता से की जा सकती है। प्रश्न चरण प्रश्न चरण में, प्रारंभिक नोड से शुरू करके एक द्विदिशात्मक खोज की जाती है और पूर्व-प्रसंस्करण चरण में बनाए गए शॉर्टकट द्वारा संवर्धित मूल ग्राफ पर लक्ष्य नोड किया जाता है। और के बीच के सबसे छोटे मार्ग पर सबसे महत्वपूर्ण शीर्ष या तो या स्वयं या दोनों और से अधिक महत्वपूर्ण होगा। इसलिए, वर्टेक्स मिनिमाइज़िंग मूल ग्राफ और होल्ड में सबसे छोटे रास्ते पर है। शॉर्टकट कैसे बनाए जाते हैं, इसके संयोजन का मतलब है कि आगे और पीछे की खोज दोनों को केवल पदानुक्रम में अधिक महत्वपूर्ण नोड्स (ऊपर की ओर) की ओर ले जाने वाले किनारों को आराम करने की आवश्यकता होती है जो खोज स्थान को छोटा रखता है। सभी अप-(डाउन-अप)-डाउन पथों में, आंतरिक (डाउन-अप) को छोड़ दिया जा सकता है, क्योंकि प्रीप्रोसेसिंग चरण में एक शॉर्टकट बनाया गया है। पथ पुनर्प्राप्ति ए. सी. एच. क्वेरी, जैसा कि ऊपर वर्णित है, समय या दूरी प्रदान करता है लेकिन वास्तविक पथ से नहीं। सबसे छोटे रास्ते पर किनारों (सड़कों) की सूची प्राप्त करने के लिए, लिए गए शॉर्टकट को खोला जाना चाहिए। प्रत्येक शॉर्टकट दो किनारों का संयोजन हैः या तो मूल ग्राफ के दो किनारे, या दो शॉर्टकट, या एक मूल किनारा और एक शॉर्टकट। संकुचन के दौरान प्रत्येक शॉर्टकट के मध्य शीर्ष को संग्रहीत करने से सबसे छोटे मार्ग की रैखिक-समय पुनरावर्ती अनपैकिंग संभव हो जाती है। अनुकूलित संकुचन पदानुक्रम यदि नेटवर्क टोपोलॉजी की तुलना में किनारे के भार को अधिक बार बदला जाता है, तो सीएच को प्रीप्रोसेसिंग और क्वेरी चरण के बीच एक अनुकूलन चरण को शामिल करके तीन-चरण दृष्टिकोण तक बढ़ाया जा सकता है। इसका उपयोग उदाहरण के लिए कम से कम दूरी और कम से कम समय के बीच स्विच करने के लिए किया जा सकता है या वर्तमान यातायात जानकारी के साथ-साथ कुछ प्रकार की सड़कों (नौकाओं, राजमार्गों) से बचने जैसी उपयोगकर्ता प्राथमिकताओं को शामिल किया जा सकता है। प्रीप्रोसेसिंग चरण में, अधिकांश रनटाइम उस क्रम की गणना करने में खर्च किया जाता है जिसमें नोड्स अनुबंधित होते हैं। पूर्वसंसाधन चरण में संकुचन संचालन के इस अनुक्रम को तब सहेजा जा सकता है जब उन्हें बाद में अनुकूलन चरण में आवश्यकता होती है। हर बार जब मीट्रिक को अनुकूलित किया जाता है, तो संकुचन को कस्टम मीट्रिक का उपयोग करके संग्रहीत क्रम में कुशलता से लागू किया जा सकता है। इसके अतिरिक्त, नए किनारे के वजन के आधार पर कुछ शॉर्टकट की फिर से गणना करना आवश्यक हो सकता है। इसके काम करने के लिए, संकुचन क्रम की गणना मीट्रिक-स्वतंत्र नेस्टेड विच्छेदन का उपयोग करके की जानी चाहिए। ऊपर वर्णित विस्तार और अनुप्रयोग सीएचएस एक प्रारंभिक नोड से एक लक्ष्य नोड तक के सबसे छोटे मार्ग की खोज करते हैं। इसे एक-से-एक सबसे छोटा मार्ग कहा जाता है और उदाहरण के लिए कार-नौवहन प्रणालियों में इसका उपयोग किया जाता है। अन्य अनुप्रयोगों में सड़क खंडों में जी. पी. एस. निशान का मिलान करना और यातायात सिमुलेटर की गति बढ़ाना शामिल है, जिन्हें एक नेटवर्क में सभी चालकों द्वारा लिए गए संभावित मार्गों पर विचार करना होता है। मार्ग की भविष्यवाणी में यह अनुमान लगाने की कोशिश की जाती है कि एक वाहन संभवतः कहाँ जा रहा है, यह गणना करके कि उसकी वर्तमान और पिछली स्थिति उसके प्रारंभिक बिंदु से किसी भी संभावित लक्ष्य तक के सबसे छोटे मार्ग से कितनी अच्छी तरह सहमत है। यह सीएचएस का उपयोग करके कुशलता से किया जा सकता है। एक से कई परिदृश्यों में, एक प्रारंभिक नोड और लक्ष्य नोड का एक सेट दिया जाता है और सभी के लिए दूरी की गणना की जानी चाहिए। एक-से-कई प्रश्नों के लिए सबसे प्रमुख अनुप्रयोग पॉइंट-ऑफ-इंटरेस्ट खोज हैं। विशिष्ट उदाहरणों में मीट्रिक के रूप में भौगोलिक दूरी के बजाय वास्तविक यात्रा समय का उपयोग करके निकटतम गैस स्टेशन, रेस्तरां या डाकघर का पता लगाना शामिल है। कई से कई सबसे छोटे पथ परिदृश्य में, प्रारंभिक नोड्स का एक सेट और लक्ष्य नोड्स का एक सेट दिया जाता है और सभी के लिए दूरी की गणना की जानी चाहिए। इसका उपयोग उदाहरण के लिए लॉजिस्टिक अनुप्रयोगों में किया जाता है। सीएचएस को निम्नलिखित तरीके से कई-से-कई प्रश्नों तक बढ़ाया जा सकता है। सबसे पहले, प्रत्येक से ऊपर की ओर पीछे की ओर खोज करें। इस खोज के दौरान स्कैन किए गए प्रत्येक शीर्ष के लिए, एक बाल्टी में एक स्टोर करें। फिर, प्रत्येक खाली बाल्टी के लिए जाँच करते हुए, प्रत्येक से आगे की ओर खोज की जाती है, कि क्या संबंधित शीर्ष पर मार्ग किसी भी सर्वोत्तम दूरी में सुधार करता है। अर्थात्, यदि किसी के लिए भी। कुछ अनुप्रयोगों में एक-से-सभी गणनाओं की भी आवश्यकता होती है, यानी, ग्राफ में स्रोत शीर्ष से अन्य सभी शीर्षों तक की दूरी का पता लगाना। जैसा कि डिज्क्स्ट्रा का एल्गोरिथ्म प्रत्येक किनारे पर ठीक एक बार जाता है और इसलिए रैखिक समय में चलता है, यह सैद्धांतिक रूप से इष्टतम है। हालांकि, डिज्क्स्ट्रा के एल्गोरिदम को समानांतर करना मुश्किल है और इसके खराब स्थान के कारण कैश-इष्टतम नहीं है। सीएचएस का उपयोग अधिक कैश-इष्टतम कार्यान्वयन के लिए किया जा सकता है। इसके लिए, शॉर्टकट-समृद्ध ग्राफ में सभी नोड्स पर नीचे की ओर स्कैन करने के बाद आगे की ओर खोज की जाती है। बाद का ऑपरेशन एक रैखिक तरीके से स्मृति के माध्यम से स्कैन करता है, क्योंकि नोड्स को महत्व के घटते क्रम में संसाधित किया जाता है और इसलिए तदनुसार स्मृति में रखा जा सकता है। ध्यान दें कि यह संभव है क्योंकि जिस क्रम में दूसरे चरण में नोड्स को संसाधित किया जाता है वह स्रोत नोड से स्वतंत्र है। उत्पादन में, कार-नौवहन प्रणालियों को अनुमानित यातायात जानकारी का उपयोग करके सबसे तेज़ यात्रा मार्गों की गणना करने और वैकल्पिक मार्गों को प्रदर्शित करने में सक्षम होना चाहिए। दोनों को सीएचएस का उपयोग करके किया जा सकता है। पूर्व को समय-निर्भर नेटवर्क के साथ रूटिंग कहा जाता है जहां किसी दिए गए किनारे का यात्रा समय अब स्थिर नहीं रहता है, बल्कि किनारे में प्रवेश करते समय दिन के समय का एक कार्य होता है। वैकल्पिक मार्गों को सुगम दिखने की आवश्यकता है, जो सबसे छोटे मार्ग से काफी अलग होना चाहिए, लेकिन काफी लंबा नहीं होना चाहिए। सीएचएस को एक ही समय में कई मेट्रिक्स को अनुकूलित करने के लिए बढ़ाया जा सकता है; इसे बहु-मानदंड मार्ग योजना कहा जाता है। उदाहरण के लिए, यात्रा की लागत और समय दोनों को कम किया जा सकता है। एक अन्य उदाहरण विद्युत वाहन हैं जिनके लिए उपलब्ध बैटरी चार्ज वैध मार्गों को बाधित करता है क्योंकि बैटरी खाली नहीं चल सकती है। सिद्धांत संकुचन पदानुक्रम के पूर्व प्रसंस्करण और प्रश्न प्रदर्शन पर कई सीमाएँ स्थापित की गई हैं। निम्नलिखित में ग्राफ में शीर्षों की संख्या, किनारों की संख्या, राजमार्ग आयाम, ग्राफ व्यास, वृक्ष-गहराई है और वृक्ष-चौड़ाई है। संकुचन पदानुक्रम प्रदर्शन का पहला विश्लेषण आंशिक रूप से राजमार्ग आयाम के रूप में जानी जाने वाली मात्रा पर निर्भर करता है। जबकि इस मात्रा की परिभाषा तकनीकी है, सहज रूप से एक ग्राफ में एक छोटा राजमार्ग आयाम होता है यदि प्रत्येक के लिए शीर्षों का एक विरल सेट होता है जैसे कि लंबाई के प्रत्येक सबसे छोटे पथ में एक शीर्ष शामिल होता है। राजमार्ग आयाम के सटीक मूल्य की गणना करना एनपी-हार्ड और डब्ल्यू [1]-हार्ड है, लेकिन ग्रिड के लिए यह ज्ञात है कि राजमार्ग आयाम है। अनुकूलन योग्य संकुचन पदानुक्रम कार्य में एक वैकल्पिक विश्लेषण प्रस्तुत किया गया था। पूछताछ के चलने के समय को इसके द्वारा सीमित किया जा सकता है। चूंकि वृक्ष की गहराई को वृक्ष की चौड़ाई के संदर्भ में सीमित किया जा सकता है, इसलिए यह एक वैध ऊपरी सीमा भी है। मुख्य स्रोत यह है कि सबसे खराब स्थिति के चलने के समय के परिणाम बेहतर तरीके से विस्तृत हैं। पूर्वप्रक्रिया प्रदर्शन प्रश्न प्रदर्शन संदर्भ बाहरी लिंक खुला स्रोत कार्यान्वयन https://www.graphhopper.com https://github.com/ifsttar/Tempus https://github.com/RoutingKit/RoutingKit http://project-osrm.org http://www.opentripplanner.org ग्राफ एल्गोरिदम खोज एल्गोरिदम रूटिंग एल्गोरिदम