हम शहर के चारों ओर बुद्धिमानी से चलते हैं - 2: आनुवंशिक एल्गोरिथ्म का उपयोग करके शहर के चारों ओर घूमते हैं

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

शहर की तस्वीरें - एलेक्स 'फ्लोरस्टीन' फेडोरोव

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

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

इसलिए, उपयोगकर्ता आसपास के क्षेत्र का एक छोटा दौरा करना चाहते हैं और निर्दिष्ट समय (आमतौर पर 1-2 घंटे) में वापस प्रारंभिक बिंदु पर वापस आ सकते हैं। जैसा कि यह निकला, इस प्रकार की सैर काफी मांग में है। उदाहरण के लिए, लेख "एक गंतव्य के भीतर पर्यटकों के आंदोलन पैटर्न" हांगकांग में 250 पर्यटकों के पटरियों के अध्ययन का वर्णन करता है, जबकि 40% पर्यटकों ने होटल से 500 मीटर के दायरे में एक परिपत्र मार्ग से शहर की खोज शुरू की। हालांकि, अक्सर लोग बस घूमते रहते हैं, न जाने क्या-क्या दिलचस्प है जो आस-पास देखा जा सकता है।

यह कार्य जटिल है यदि यह पर्यटन केंद्र में नहीं है (आप कहीं भी जाते हैं, तो आपको हर जगह कुछ दिलचस्प मिलेगा), लेकिन कहीं-कहीं सरहद पर जहां आपको दर्शनीय स्थलों की तलाश है।

त्रिज्या और आकर्षण का चयन

मार्ग बनाने के लिए, हमें पहले उन आकर्षणों का चयन करना होगा, जिन्हें हम देखना चाहते हैं। और इसके लिए आपको शुरुआती बिंदु के आसपास उनकी खोज के क्षेत्र को निर्धारित करने की आवश्यकता है। यदि उपयोगकर्ता एम मिनटों में अधिकतम चलने का समय निर्धारित करता है, तो सबसे दूर का बिंदु जिस पर आप पहुंच सकते हैं और लौटने का समय एक दूरी (वी * एम / 2) पर बिंदु है, जहां वी पैदल यात्री की गति है।

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

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

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

यहां हम या तो दूर पार्क में जा सकते हैं, या एक बार करीब से कई बिंदुओं पर जा सकते हैं

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

ललाट दृष्टिकोण मुद्दों

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

सबसे पहले, मैंने एक सरल अनुक्रमिक एल्गोरिथ्म बनाने और बनाने की कोशिश की। हालाँकि, मैं जल्दी से कई समस्याओं को लेकर आया था।

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

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

कुछ बिंदु पर, यह मेरे लिए स्पष्ट हो गया कि मैं व्यावहारिक रूप से आनुवंशिक एल्गोरिथ्म का काम कर रहा था: मैं मानचित्र पर विभिन्न मार्गों को आकर्षित करता हूं और यह निर्धारित करने का प्रयास करता हूं कि मैं व्यक्तिगत रूप से उन्हें कितना पसंद करूंगा।

आनुवंशिक एल्गोरिथ्म

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

N से k तक नियुक्तियों की संख्या के सूत्र को जानकर, हम संभावित विकल्पों की संख्या का अनुमान लगा सकते हैं। यदि हम सेंट पीटर्सबर्ग में पैलेस स्क्वायर के आसपास घंटे भर के मार्ग पर विचार करते हैं, तो 1320 मीटर (जो ऊपर वर्णित है) के दायरे में फ़िल्टरिंग और क्लस्टरिंग के बाद प्रमुख आकर्षण के लिए 54 उम्मीदवार होंगे।

केंद्र में दर्शनीय स्थलों के ढेर से बांझ दलिया, पिछले लेख के एल्गोरिथ्म के अनुसार गणना किए गए दृश्यता क्षेत्रों का डिबग आउटपुट

चयन और सॉर्टिंग के सिद्धांत को एक पिछले लेख में वर्णित किया गया है, इसके अलावा हम 3 से कम के ब्याज के साथ वस्तुओं को हटाते हैं (ऐसी तुच्छ वस्तुओं के लिए, एक व्यक्ति को दूर जाने के लिए तैयार होने की संभावना नहीं है, जब तक कि पास में और कुछ भी न हो)। इस प्रकार, मार्गों की संभावित संख्या की गणना 54 से 5 तक प्लेसमेंट की संख्या के सूत्र से की जा सकती है, यह 379501200 है। 2 घंटे के मार्ग के लिए, जिसमें 151 अंक पहले से ही गिर जाते हैं, यह संख्या 73423236600 के बराबर होगी। खैर, एक साधारण खोज के लिए थोड़ा बहुत।

गुणसूत्र और आनुवंशिक संचालक

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

• आंशिक रूप से मैप्ड क्रॉसओवर (PMX) का उपयोग क्रॉसिंग के लिए किया जाता है।
• उत्परिवर्तन के लिए, दो यादृच्छिक जीन (स्वैप म्यूटेटर) के स्थानों का आदान-प्रदान किया जाता है।

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

स्वास्थ्य समारोह

एक दिलचस्प परिपत्र मार्ग बनाने के लिए फिटनेस फ़ंक्शन को निम्नलिखित कारकों को ध्यान में रखना चाहिए:

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

यहाँ एक अच्छी दौर यात्रा का एक उदाहरण है। यह दो पार्कों से होकर गुजरता है और कभी भी एक ही स्थान पर दो बार नहीं जाता है

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

खराब मार्ग वास्तव में आनुवंशिकी द्वारा प्राप्त किया गया था, जिसमें 3 और 4 को फिटनेस फ़ंक्शन (स्व-क्रॉसिंग के लिए जुर्माना और एक छोटे से क्षेत्र के लिए) अक्षम किया गया था

बारीकियों

परीक्षण के दौरान, कुछ और बारीकियां सामने आईं।

समय सीमा पार हो गई

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

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

एक सीधी रेखा में 50 मीटर के बिंदुओं के बीच, लेकिन डेढ़ किलोमीटर के साथ-साथ फुटपाथ और दरकिनार।

हालाँकि, सभी समान, एल्गोरिथ्म कभी-कभी उपयोगकर्ता द्वारा निर्धारित समय से अधिक होता है, लेकिन फिर हर कोई खुद के लिए निर्णय ले सकता है कि क्या उसके पास 10-15 अतिरिक्त मिनट हैं या यदि उसे जल्दी चलना है।

वेनिस

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

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

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

कभी-कभी आपको उसी तरह वापस आना पड़ता है

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

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

परिणाम

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

यहां तक ​​कि सेंट पीटर्सबर्ग के दक्षिण-पश्चिम के स्लीपिंग बैग में, आप दो घंटे की पैदल दूरी पर पर्याप्त स्मारक पा सकते हैं

आप हमारे Sight Safari वेबसाइट पर या हमारे Android एप्लिकेशन में 77 समर्थित शहरों में से एक में एल्गोरिथम आज़मा सकते हैं (हाँ, हमने अंत में इसे पूरा कर लिया है)।

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

सामान्य तौर पर, कोशिश करें, समीक्षा लिखें, क्या मार्ग सही तरीके से बनाए जा रहे हैं। आप नए शहरों को जोड़ने के लिए तुरंत आवेदन कर सकते हैं।