कि हमें एक सड़क बनानी चाहिए। भाग 1

हम में से अधिकांश का दैनिक कार्यक्रम घर से काम और वापस यात्रा करने तक सीमित है। और सबसे कठिन बाधा जो हमारे आंदोलन को धीमा कर सकती है वह है ट्रैफिक जाम। लेकिन हमारे देश में बड़ी संख्या में ऐसे स्थान हैं जहां आप केवल विशेष वाहनों पर ही जा सकते हैं।

इस तरह का परिवहन अच्छा है अगर आपको नियमित रूप से बड़ी मात्रा में कार्गो ले जाने या ऐसे दुर्गम क्षेत्रों की यात्रा करने की आवश्यकता नहीं है। तब हमें पहले से ही बुनियादी ढांचे के निर्माण के बारे में सोचना चाहिए, जो कि सामान्य नागरिक परिवहन पर संभव है।

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

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

यह सब कैसे शुरू हुआ

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

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

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

नदी के बाढ़ क्षेत्र में कैसे नहीं? Permafrost मिट्टी पर पथ को कम करने के लिए कैसे? एक दलदल के माध्यम से सड़क बिछाने पर रेत तकिया की मात्रा को कैसे बचाया जाए? इस तकिए के लिए रेत कहां से लाएं?

यह उन सवालों का केवल एक छोटा सा अंश है जो एक इंजीनियर काम के दौरान खुद से पूछता है, और फिर भी आपको विभिन्न GOST और SNiPs को ध्यान में रखना होगा। और ठीक है, अगर आप केवल दो वस्तुओं को जोड़ना चाहते हैं, और अगर दो दर्जन ऑब्जेक्ट हैं?

इसलिए, डिजाइन उद्योग को एक ऐसे उपकरण की सख्त आवश्यकता है जो एक इंजीनियर द्वारा डिजाइन की गई रैखिक वस्तुओं की लागत और उन्हें स्वचालित मोड में बनाने की क्षमता दोनों की गणना कर सके।

डेटा

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

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

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

मनुष्य द्वारा पहले जो बनाया गया था, उसके पुन: उपयोग के अलावा, किसी को किसी भी वस्तु के पास निर्माण पर विभिन्न प्रतिबंधों को भी ध्यान में रखना चाहिए। उदाहरण के लिए, बिजली लाइनों के निर्माण के लिए, आपको बिजली की लाइन पर वोल्टेज के आधार पर मानव निवास के स्थानों से संकेत को ध्यान में रखना होगा।

लेकिन केवल एक विमान पर समस्या की गणना पर विचार करना पूरी तरह से सही नहीं है, क्योंकि फ्लैट इलाके के अलावा, ऊंचाई में बड़े अंतर वाले क्षेत्र हैं, जिस पर निर्माण भी नहीं किया जा सकता है।

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

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

थोड़ा सा गणित

यह ज्ञात है कि प्रत्येक सूत्र पाठकों की संख्या को आधा कर देता है, इसलिए हमने नाटकीय रूप से इस खंड को कम कर दिया ...

डिज़ाइन किए गए रैखिक सुविधा के मार्ग का अनुकूलन करने के लिए, इसकी निर्माण लागत की गणना करने में सक्षम होना आवश्यक है। प्रत्येक रैखिक वस्तु को एक पॉलीलाइन के रूप में दर्शाया जा सकता है $$$L = \ {A_i, B_i \} _ {i = 0} ^ n$ खंडों से मिलकर $$$AB_ {i}$ ।
प्रत्येक सीधे अनुभाग की निर्माण लागत को फ़ंक्शन मान के रूप में दर्शाया जा सकता है $$$C_ {AB_ {i}}$ , जहां प्रत्येक खंड को पैरामीट्रिक रूप से निर्दिष्ट किया गया है:

$$$ $ प्रदर्शन $ $ {\ displaystyle AB_i \ colon \ बाएँ \ {{\ _ शुरू करना {संरेखित} और s = s \ बाएँ (t \ दाएँ) - \ mbox {पैरामीटरकृत वक्र}, \\ & h = h \ left (s) ) \ सही) - \ mbox {ऊंचाई ऊंचाई का कार्य}, \\ & c = c \ left (s (t) \ सही) - \ mbox {एक बिंदु पर निर्माण की इकाई लागत का कार्य}, \\ \ end {गठबंधन}} सही ।} $ $ प्रदर्शन $ $

जहाँ $$$t \ in [बायां [0, 1 \ right]$ - खंड परिमाणीकरण।

$$$C_ {AB_i} = \ int \ limit_ {AB_i} c \ left (s (t) \ right) \ sqrt {\ बाएँ [g_ {xy} (s) (t) + \ frac {\ _ आंशिक रूप से {} आंशिक s_x} \ cdot \ frac {\ आंशिक h} {\ आंशिक s_y} \ right] \ dot {s} _ {x} \ dot {s} _ {y}} dt$ जहाँ $$$जी$ - पृथ्वी की सतह के मेट्रिक टेंसर राहत को ध्यान में रखे बिना, अर्थात, सरल शब्दों में, पृथ्वी की सतह पर दूरी को मापने का कार्य।

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

सबसे अच्छा तरीका खोजने के लिए दृष्टिकोण

लेकिन वस्तुओं के एक समूह में शामिल होने के लिए आगे बढ़ने से पहले, आपको यह सीखने की जरूरत है कि दोनों के बीच इष्टतम मार्ग कैसे खोजा जाए। ऐसा करने के दो तरीके तुरंत दिमाग में आते हैं:

1. एक ग्राफ़ बनाएँ, और फिर सबसे छोटी पथ खोज विधियाँ लागू करें;
2. अनुकूलन विधियों के आधार पर एक समाधान का उपयोग करें।

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

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

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

लेख के इस भाग में, हम ग्राफ़ पर इस समस्या के प्रस्तावित समाधान पर विचार करेंगे।

उपकरण चयन

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

आवेदन में, हमने एक प्रभावशाली तकनीकी स्टैक का उपयोग किया, जो निम्नलिखित तक सीमित नहीं है:

• पॉलीगोन और पॉलीइलीन जैसे ज्यामितीय डेटा के साथ काम करने के लिए सुडौल ;
• सुडौल के साथ सुविधाजनक काम के लिए जियोफ़ोन ;
• गणना किए गए ग्राफ़ को संग्रहीत करने और उस पर सबसे छोटा रास्ता ढूंढने के साथ-साथ न्यूनतम फैले हुए पेड़ों को खोजने के लिए डरपोक;
• लागत समारोह के साथ काम करने के लिए PyTorch ;
• छवियों के साथ काम करने के लिए तकिया ।

कार्यान्वयन

मॉड्यूल को कई चरणों में विभाजित किया जा सकता है:

• लागत समारोह पीढ़ी;
• कम्प्यूटेशनल ग्रिड पीढ़ी;
• ग्रिड पर आधारित एक ग्राफ का निर्माण;
• ग्राफ भार;
• एक ग्राफ पर सबसे छोटे रास्तों की गणना।

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

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

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

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

वर्दी ग्रिड मॉडल व्यक्तिगत बिंदुओं के निर्देशांक का वर्णन करता है, ताकि ग्रिड नोड्स के बीच की दूरी समान हो। एक असमान ग्रिड व्यक्तिगत बिंदुओं के यादृच्छिक सेट के रूप में प्रकट होता है।

एक समान ग्रिड का उपयोग हमेशा सबसे छोटा रास्ता खोजने के लिए उच्च-गुणवत्ता वाला परिणाम नहीं देगा, इसलिए, असमान ग्रिड पर इस दृष्टिकोण का परीक्षण करना आवश्यक है। सबसे बहुमुखी त्रिकोणीय जाल है।

ग्रिड को एक समान आयताकार ग्रिड में एक निश्चित गुणांक के साथ शोर का परिचय देकर उत्पन्न किया गया था, और फिर इस सेट के लिए Delaunay त्रिकोण बिंदुओं को लागू किया गया।

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

प्रमुख मुद्दे

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

समस्या, हमेशा की तरह, कम्प्यूटेशनल ग्रिड के साथ थी। हमने ग्रिडों की उपस्थिति के साथ अपने प्रयोगों को जारी रखा और इस निष्कर्ष पर पहुंचे कि कोने को ग्राफ से जोड़ना, जहां प्रत्येक शीर्ष n- निकटतम पड़ोसियों से जुड़ा है, हमारी समस्याओं का समाधान है।

नेटवर्क निर्माण

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

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

असली मामला

तो, अब हम एल्गोरिदम के परिणामों की ओर मुड़ते हैं। हमारा काम किसी दिए गए सेट को संचार नेटवर्क से जोड़ना है। एल्गोरिथ्म के परिणामों की तुलना पहले से निर्मित सड़क नेटवर्क के साथ हुई। गणना के लिए मौजूदा नेटवर्क की कुल लंबाई 153.5 किमी बनाम 122.6 किमी है। यह सड़क नेटवर्क की लंबाई में लगभग 25% की कमी देता है, जो अंततः पूंजी निर्माण लागत पर लगभग 5-15% की बचत करेगा।

आप यहां गणना परिणामों पर अधिक बारीकी से देख सकते हैं ।

उपयोग की जाने वाली अनुकूलन विधियों का एक विवरण लेख के अगले भाग में होगा।