उनके साथ काम करने के लिए सड़क नेटवर्क और एल्गोरिदम के ग्राफ़

गणित में, सड़क नेटवर्क (ऑटोमोबाइल और न केवल) को एक भारित ग्राफ द्वारा दर्शाया जाता है। बस्तियों (या चौराहों) ग्राफ के कोने हैं, पसलियां सड़कें हैं, पसलियां वजन इन सड़कों के साथ दूरी हैं।

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

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

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

कुछ महत्वपूर्ण अवधारणाएँ और रूढ़ियाँ

1. हम गैर-नकारात्मक बढ़त भार के साथ भारित अप्रत्यक्ष रेखांकन का उपयोग करेंगे। विशेष रूप से, क्षेत्र (देश) के भीतर की सड़कें बस एक ऐसा ग्राफ हैं।

2. सबसे कम दूरी का मैट्रिक्स (MKR) - इसका छोटा और सरल उदाहरण कई सड़क के atlases में पाया जा सकता है। इस लेबल को आमतौर पर कुछ इस तरह कहा जाता है: "सबसे महत्वपूर्ण शहरों के बीच की दूरी।" यह मुख्य विकर्ण के नीचे या ऊपर मैट्रिक्स के एक भाग की तरह दिखता है (ऊपरी बाएं से निचले दाएं कोने तक), क्योंकि मुख्य विकर्ण के दूसरी तरफ बिल्कुल समान संख्याएं हैं, दूसरे शब्दों में, तत्व M (i, j = M (j, i)। ऐसा इसलिए होता है क्योंकि जैसा कि गणितज्ञ कहते हैं, ग्राफ गैर-उन्मुख है। पंक्तियाँ और स्तंभ शहरों के अनुरूप हैं (ग्राफ़ के कोने)। वास्तव में, ऐसी तालिका बहुत बड़ी है, क्योंकि सभी गांव और चौराहे ग्राफ के शीर्ष पर प्रवेश करते हैं, शहरों को छोड़कर, लेकिन एटलस में इतनी बड़ी तालिका को प्रिंट करना स्वाभाविक रूप से असंभव है।

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

हमारा एमकेआर हो सकता है: ए) अग्रिम में जाना जाता है, क्योंकि हमने एमकेआर की खोज के तरीकों में से एक द्वारा इसकी गणना की है; बी) हम एमकेपी को नहीं जान सकते हैं, लेकिन इसे लाइन द्वारा आवश्यक रूप से निर्धारित करते हैं। लाइन द्वारा लाइन - इसका मतलब यह है कि आवश्यक लाइन के लिए, दूरी की गणना केवल शीर्ष से इसके शेष खांचे तक की जाती है, उदाहरण के लिए, दिज्क्स्त्र विधि द्वारा।

3. कुछ और अवधारणाएँ। किसी दिए गए वर्टेक्स की विलक्षणता इस वर्टेक्स से सबसे दूर की दूरी है। ग्राफ का त्रिज्या सभी लंबों की विलक्षणताओं में सबसे छोटा है। ग्राफ का केंद्र एक शीर्ष है जिसकी विलक्षणता त्रिज्या के बराबर है।

यह व्यवहार में कैसा दिखता है। सड़क नेटवर्क का केंद्र शहर या चौराहा है जो नेटवर्क में अन्य सभी बिंदुओं से सबसे कम दूरी पर है। रेडियस इस केंद्रीय नोड से सबसे दूर की दूरी है।

4. वर्टेक्स की डिग्री - किनारों की संख्या जो वर्टेक्स से जुड़ी होती है।
सड़क नेटवर्क के ग्राफ, सभी चोटियों की औसत डिग्री 2 से 4 के क्षेत्र में है। यह काफी स्वाभाविक है - बड़ी संख्या में आसन्न सड़कों के साथ चौराहों का निर्माण करना कठिन और महंगा है, फिर इस तरह के सड़क नेटवर्क का उपयोग करना कम मुश्किल नहीं है। चोटियों की कम औसत डिग्री वाले ग्राफ़ को विरल कहा जाता है, जैसा कि हम देखते हैं, सड़क नेटवर्क के ग्राफ़ ऐसे हैं।

टास्क 1. सबसे कम दूरी के मैट्रिक्स में त्रिज्या और ग्राफ के केंद्र के लिए खोजें

ध्यान दें कि एक ग्राफ़ में कई केंद्र हो सकते हैं, लेकिन हम उनमें से किसी को ढूंढना चाहते हैं।

सामान्य मामले में समस्या का समाधान कैसे किया जाता है? FIBC का पूरा दृश्य। पंक्ति में अधिकतम तत्व (प्रत्येक शीर्ष की विलक्षणता) के लिए खोज की जाती है, और फिर इन अधिकतम तत्वों से न्यूनतम पाया जाता है।

यह सबसे तेज़ रास्ते से दूर है। क्या तेजी से जरूरत है अगर, यह प्रतीत होता है, ग्राफ का त्रिज्या और केंद्र एक बार मिल सकता है? उदाहरण के लिए, उन पर कार्य और एल्गोरिदम हैं, जहां, गणना के दौरान, कोने में समूहों को लगातार "पुनर्मिलन" किया जाता है, और प्रत्येक समूह के लिए मानदंड इसकी त्रिज्या है। इस मामले में, त्रिज्या कई बार निकाली जाती है, और इसकी खोज की गति एक महत्वपूर्ण पैरामीटर बन जाती है। कैसे तेजी से त्रिज्या खोजने के लिए?

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

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

मान लीजिए कि हमने केवल दो पंक्तियों A और B में मान पाया। इसके अलावा, पंक्ति A में अधिकतम मान पंक्ति B में न्यूनतम मान के बराबर है (यह मान स्तंभ A और पंक्ति B के प्रतिच्छेदन पर होगा)। यह साबित करना आसान है कि ए ग्राफ का केंद्र है, और पाया गया मूल्य इसकी त्रिज्या है। समस्या हल हो गई है।

यह बहुत अच्छा है, लेकिन सड़क नेटवर्क के ग्राफ पर ऐसी स्थिति की संभावना नहीं है और इस तरह से समस्या को हल करने से काम नहीं चलेगा। हम चकरा जाएंगे।
बी 1 और बी 2 की कुछ पंक्तियाँ लें। उनसे हम वेक्टर एम को इस तरह बनाते हैं: एम (आई) = अधिकतम [बी 1 (आई), बी 2 (आई)]। यह साबित करना आसान है कि यदि सभी पंक्तियों के लिए I मान मिनट (M (i) स्तंभ A में अधिकतम मान के बराबर है, तो, फिर से, A केंद्र है, और पाया गया M (i) त्रिज्या है।
यदि लाइनों की एक जोड़ी पर्याप्त नहीं है, तो आप कई लाइनें ले सकते हैं, उदाहरण के लिए तीन: बी 1, बी 2 और बी 3, फिर एम (आई) = अधिकतम [बी 1 (आई), बी 2 (आई), बी 3 (आई)]। सड़क नेटवर्क के रेखांकन की ख़ासियत यह है कि कई लाइनों की आवश्यकता नहीं है (यह एक दर्जन के भीतर रखना संभव होगा)। यह मौजूदा नेटवर्क ग्राफ़ पर प्रयोग करके सत्यापित करना आसान है, उन्हें इंटरनेट से डाउनलोड करना: लिंक ।

सामान्य मामले में, और गणित के दृष्टिकोण से, यह, ज़ाहिर है, ऐसा नहीं है। एक सैद्धांतिक ग्राफ का निर्माण करना काफी संभव है जिसमें आपको बहुत सी लाइनों का उपयोग करना होगा (लगभग सभी को छोड़कर ए)। यह सिर्फ इतना है कि इस तरह का एक वास्तविक सड़क नेटवर्क बनाना असंभव है - पर्याप्त पैसा नहीं होगा।

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

हमें बी 1 और बी 2 की एक जोड़ी मिली। जैसा कि ऊपर वर्णित है, हम जोड़ी एम वेक्टर को खोजते हैं। जिस पंक्ति में हमें मिनट (M (i)) मिला, वह केंद्र का एक दावेदार है, हम इसे ए से दर्शाते हैं। यदि कॉलम A में मान मिनट (i) अधिकतम है, तो केंद्र और त्रिज्या पहले से ही पाए जाते हैं। यदि नहीं, तो कॉलम ए में अधिकतम मूल्य एक और शीर्ष पर दूरी से संबंधित है (बी 1 नहीं और बी 2 नहीं)। तो, हमने वेक्टर एम के लिए खोज करने के लिए सूची में एक नया वर्टेक्स बी 3 प्राप्त किया। वैकल्पिक रूप से, आप बी 3 के लिए सबसे दूर के वर्टेक्स को भी खोज सकते हैं, और यदि यह बी 1 या बी 2 नहीं है, तो इसे बी 4 के रूप में जोड़ें। इस प्रकार, हम केंद्र और त्रिज्या पाए जाने तक कोने बी की सूची बढ़ाते हैं।

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

समस्या 2. सबसे कम दूरी के मैट्रिक्स की खोज करें

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

हम उन्हें एक पूरी तरह से अलग एल्गोरिथ्म पर उपयोग करेंगे और मौजूदा ग्राफ़ पर हमें दीज़कस्ट्रा के एल्गोरिथ्म की तुलना में दसियों बार त्वरण मिलेगा। हम तुरंत ध्यान देते हैं कि इस एल्गोरिथ्म की ख़ासियत यह है कि यह एमकेपी की खोज करता है, और एक बार में सब कुछ सटीक होता है (यानी, लगभग नहीं, हेयुरिस्टिकली नहीं)।

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

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

A को डिग्री 2 के साथ एक शीर्ष रेखा होने दें और इसे B1 और B2 के शीर्षों से जोड़ दें। यदि मार्ग B1-A-B2 किनारे B1-B2 से अधिक लंबा या बराबर है, तो कोई भी मार्ग बिंदु A से होकर नहीं गुजरता है, केवल बिंदु A के मार्गों को छोड़कर (सभी अन्य B1-B2 से होकर गुजरते हैं)। तो बिंदु A को हटाया जा सकता है। नहीं तो, यदि B1-A-B2 B1-B2 से कम है या B1-B2 के कोई किनारे नहीं हैं, तो शीर्ष A को वजन B1-B2 के वजन के बराबर सेट करके हटाया जा सकता है: B1-A + + A-B2 ए से अन्य बिंदुओं का मार्ग बी 1 या बी 2 से होकर गुजरता है, यदि बी 1 और बी 2 के लिए दूरी ज्ञात है, तो ए से दूरी की गणना करना भी आसान है।

उसी सिद्धांत से, आप किसी भी डिग्री के साथ एक शीर्ष को हटा सकते हैं, आवश्यकतानुसार, द्वि-बी-बीजे के साथ द्वि-ए-बीजे। सच है, आपको यह समझने की ज़रूरत है कि शीर्ष की डिग्री जितनी अधिक होगी, उतने अधिक संभव किनारों की जांच होनी चाहिए। डिग्री n के शीर्ष के लिए, यह संख्या n (n-1) / 2 है।

सैद्धांतिक रूप से, इस तरह से आप किसी भी ग्राफ़ में सभी लंबों को हटा सकते हैं, हालांकि, सामान्य स्थिति में, हम किनारों की संख्या में वृद्धि के साथ परेशानी में हैं। डिग्री n के साथ कोने हटाते समय, हटाए गए कोने से सटे कोने की डिग्री: -1 से घट सकती है, बदल नहीं सकती, n-2 तक बढ़ सकती है। यह निम्नानुसार है कि जब डिग्री 3 या उससे अधिक के कोने को हटाते हैं, तो शेष कोने की डिग्री आम तौर पर बढ़ती है, ग्राफ़ कम और कम विरल हो जाता है, और अंत में, कोने को हटाने से एक समय लेने वाले कार्य में बदल जाएगा। एल्गोरिथ्म, सामान्य मामले में, अत्यंत श्रमसाध्य और व्यावहारिक रूप से बेकार है, लेकिन सामान्य मामले में यह ठीक है।

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

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

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

यूएस रोड नेटवर्क के ग्राफ़ पर एल्गोरिदम का उपयोग करने के परिणाम भी दिए गए हैं।

निष्कर्ष

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