algorithm - क्या एल्गोरिदम मानचित्र पर बिंदु ए से बिंदु बी पर दिशानिर्देशों की गणना करते हैं?




routing mapping (12)

डिजस्ट्रा के एल्गोरिदम जैसे ग्राफ़ एल्गोरिदम काम नहीं करेंगे क्योंकि ग्राफ बहुत बड़ा है।

यह तर्क जरूरी नहीं है क्योंकि डिजस्ट्रा आमतौर पर पूरे ग्राफ को नहीं देखेगा बल्कि बल्कि एक बहुत ही छोटा सबसेट (बेहतर ग्राफ से जुड़ा हुआ होगा, यह सबसेट छोटा होगा)।

डिजस्ट्रा वास्तव में अच्छी तरह से व्यवहार किए गए ग्राफ के लिए अच्छा प्रदर्शन कर सकता है। दूसरी तरफ, सावधान parametrization ए * हमेशा अच्छा, या बेहतर प्रदर्शन करेंगे। क्या आपने पहले ही कोशिश की है कि यह आपके डेटा पर कैसा प्रदर्शन करेगा?

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

नक्शा प्रदाता (जैसे Google या याहू! मैप्स) निर्देश कैसे सुझाते हैं?

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

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

अभ्यास में वास्तव में क्या एल्गोरिदम का उपयोग किया जाता है?

पुनश्च। यह प्रश्न ऑनलाइन मैपिंग दिशानिर्देशों में क्विर्क ढूंढकर प्रेरित था। त्रिकोण असमानता के विपरीत, कभी-कभी Google मानचित्र सोचता है कि X-Z अधिक समय लेता है और X-Y-Z में मध्यवर्ती बिंदु का उपयोग करने से कहीं अधिक है। लेकिन हो सकता है कि उनके पैदल चलने के निर्देश भी दूसरे पैरामीटर के लिए अनुकूल हों?

पी पी एस। त्रिकोण असमानता का एक और उल्लंघन है जो बताता है (मेरे लिए) कि वे किसी प्रकार के टियर किए गए दृष्टिकोण का उपयोग करते हैं: X-Z बनाम X-Y-Z । पूर्व में प्रमुख बुल्वार्ड डी सेबस्तोपोल का उपयोग करना प्रतीत होता है, भले ही यह रास्ते से थोड़ा सा हो।

संपादित करें : इनमें से कोई भी उदाहरण अब काम नहीं कर रहा है, लेकिन दोनों मूल पोस्ट के समय में थे।


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


मानचित्र पूरे नक्शे पर विचार नहीं करते हैं। मेरा अनुमान है: - 1. आपके स्थान के अनुसार, वे उस स्थान पर एक स्थान और स्थलचिह्न लोड करते हैं। 2. जब आप गंतव्य खोजते हैं, तब जब वे मानचित्र के दूसरे हिस्से को लोड करते हैं और दो स्थानों से ग्राफ बनाते हैं और फिर सबसे कम पथ एल्गोरिदम लागू करते हैं।

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


मेरे पास इस पर कुछ और विचार थे:

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

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

ध्यान दें कि जोन मेट्रोपॉलिटन क्षेत्र से छोटे हो सकते हैं। भू-भाग वाली सुविधाओं वाला कोई भी शहर जो इसे विभाजित करता है (कहें, एक नदी) कई जोन होंगे।


मैं देखता हूं कि ओपी में नक्शे के साथ क्या चल रहा है:

निर्दिष्ट मध्यवर्ती बिंदु के साथ मार्ग देखें: उस सड़क के कारण मार्ग सीधे पीछे की तरफ जाता है जो सीधे नहीं है।

अगर उनके एल्गोरिदम बैकट्रैक नहीं करेंगे तो यह छोटा रास्ता नहीं देखेगा।


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


मैंने पहले Google या माइक्रोसॉफ्ट या याहू मैप्स पर काम नहीं किया है, इसलिए मैं आपको नहीं बता सकता कि वे कैसे काम करते हैं।

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

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

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


मैंने यह कई बार कई बार किया है, वास्तव में, कई अलग-अलग तरीकों की कोशिश कर रहा है। मानचित्र के आकार (भौगोलिक) के आधार पर, आप हाइपरिन फ़ंक्शन को हेरिस्टिक के रूप में उपयोग करने पर विचार करना चाहेंगे।

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

f(n) = k*h(n) + g(n)

जहां के 0 0 से अधिक स्थिर है।


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

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

लेख इंजीनियरिंग फास्ट रूट योजना एल्गोरिदम उस क्षेत्र में अनुसंधान की प्रगति का एक सिंहावलोकन देता है। अधिक जानकारी के लिए उस पेपर के संदर्भ देखें।

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

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

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


यहां दुनिया की सबसे तेज़ रूटिंग एल्गोरिदम की तुलना और शुद्धता के लिए सिद्ध किया गया है:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

इस विषय पर एक Google तकनीक बात है:

youtube.com/watch?v=-0ErpE8tQbw

यहां राजमार्गों द्वारा चर्चा की गई राजमार्ग-पदानुक्रम एल्गोरिदम का कार्यान्वयन है (वर्तमान में केवल बर्लिन में, मैं इंटरफ़ेस लिख रहा हूं और एक मोबाइल संस्करण भी विकसित किया जा रहा है):

http://tom.mapsforge.org/


स्थैतिक सड़क नेटवर्क के लिए पूछताछ के समय कला की वर्तमान स्थिति अब्राहम एट अल द्वारा प्रस्तावित हब लेबलिंग एल्गोरिदम है। http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 । क्षेत्र के माध्यम से और उत्कृष्ट रूप से लिखित सर्वेक्षण को हाल ही में एक Microsoft तकनीकी रिपोर्ट http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf रूप में प्रकाशित किया गया था।

लघु संस्करण है ...

हब लेबलिंग एल्गोरिदम स्थिर सड़क नेटवर्क के लिए सबसे तेज़ प्रश्न प्रदान करता है लेकिन रैम चलाने के लिए बड़ी मात्रा में रैम की आवश्यकता होती है (18 जीबीबी)।

ट्रांजिट नोड रूटिंग थोड़ा धीमा है, हालांकि, इसे केवल 2 जीबी मेमोरी की आवश्यकता होती है और इसमें एक तेज प्रीप्रोकैसिंग समय होता है।

कंट्राक्शन पदानुक्रम त्वरित प्रीप्रोकैसिंग समय, कम स्पेस आवश्यकताएं (0.4 जीबीबी) और तेज क्वेरी समय के बीच एक अच्छा व्यापार प्रदान करते हैं।

कोई भी एल्गोरिदम पूरी तरह से हावी नहीं है ...

पीटर सैंडर्स द्वारा यह Google तकनीक की बात ब्याज की हो सकती है

https://www.youtube.com/watch?v=-0ErpE8tQbw

एंड्रयू गोल्डबर्ग द्वारा भी यह बात

https://www.youtube.com/watch?v=WPrkc78XLhw

संकुचन पदानुक्रमों का एक खुला स्रोत कार्यान्वयन किट में पीटर सैंडर्स अनुसंधान समूह वेबसाइट से उपलब्ध है। http://algo2.iti.kit.edu/english/routeplanning.php

माइक्रोसॉफ्ट द्वारा सीआरपी एल्गोरिदम के उपयोग पर भी आसानी से सुलभ ब्लॉग पोस्ट ... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/


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

मैंने here बिडरेक्शनल डिजस्ट्रा के साथ वास्तविक पथ खोज का एनिमेटेड gif बनाया here । इसके अलावा डिजस्ट्रा को ए * करने की तरह तेज़ी से बनाने के लिए कुछ और विचार हैं, जो एक "लक्ष्य उन्मुख डिजस्ट्रा" है। इसके अलावा मैंने इसके लिए एक gif-animation बनाया है।

लेकिन यह कैसे करें (बहुत) तेज़?

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

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

ग्राफ़होपर के लिए मैंने कंट्राक्शन पदानुक्रमों का उपयोग करने का निर्णय लिया क्योंकि यह लागू करने के लिए सापेक्ष 'आसान' है और ग्राफ की तैयारी के लिए उम्र नहीं लेता है। यह अभी भी बहुत तेज़ प्रतिक्रिया समय में परिणाम देता है जैसे आप हमारे ऑनलाइन इंस्टेंस ग्राफ़होपर मैप्स पर परीक्षण कर सकते हैं। दक्षिण अफ्रीका से पूर्व चीन तक, जिसके परिणामस्वरूप 23000 किमी दूरी और कार के लिए लगभग 14 दिन ड्राइविंग का समय होता है और सर्वर पर केवल ~ 0.1s लिया जाता है।







mapping