algorithm - बहुत बड़े ग्राफ़ के लिए ए*एल्गोरिथम, कैशिंग शॉर्टकट पर कोई विचार?




openstreetmap graph-algorithm (6)

Microsoft शोध में इस विषय पर लिखा गया एक बहुत अच्छा लेख है:

http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx

मूल पेपर यहाँ होस्ट किया गया है (पीडीएफ):

http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf

अनिवार्य रूप से कुछ चीजें हैं जो आप आज़मा सकते हैं:

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

https://code.i-harness.com

मैं OpenStreetMap नक्शे पर एक कूरियर / लॉजिस्टिक सिमुलेशन लिख रहा हूं और महसूस किया है कि मूल ए * एल्गोरिथ्म नीचे चित्र के रूप में बड़े मानचित्रों (ग्रेटर लंदन जैसे) के लिए पर्याप्त तेज नहीं होने जा रहा है।

हरे रंग के नोड्स उन लोगों के अनुरूप होते हैं जिन्हें खुले सेट / प्राथमिकता कतार में रखा गया था और विशाल संख्या के कारण (पूरा नक्शा 1-2 मिलियन की तरह कुछ है), यह मार्ग चित्रित करने के लिए 5 सेकंड या ऐसा लगता है। दुर्भाग्य से प्रति रूट 100ms मेरी पूर्ण सीमा के बारे में है।

वर्तमान में, नोड्स को आसन्न सूची में और एक स्थानिक 100x100 2 डी सरणी में संग्रहीत किया जाता है।

मैं उन तरीकों की तलाश कर रहा हूं जहां मैं तेज प्रश्नों के लिए समय, स्थान और यदि मार्ग की अनुकूलता की आवश्यकता हो, तो प्रीप्रोसेसिंग का व्यापार कर सकता हूं। हेयुरिस्टिक कॉस्ट के लिए स्ट्रेट-लाइन हैवेर्सिन फॉर्मूला, प्रोफाइलर के अनुसार सबसे महंगा फंक्शन है - मैंने अपने बेसिक A * को जितना हो सके उतना ऑप्टिमाइज़ किया है।

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

क्या मैंने जो ऊपर वर्णित किया है उसका एक और अधिक परिष्कृत संस्करण या शायद एक अलग विधि है जिसका मुझे पीछा करना चाहिए। बहुत धन्यवाद!

रिकॉर्ड के लिए, यहाँ कुछ बेंचमार्क परिणाम हैं जो मनमाने ढंग से वजन को कम करने और यादृच्छिक रूप से चुने गए नोड्स के 10 जोड़े के बीच पथ की गणना करने के लिए हैं:

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

आश्चर्यजनक रूप से 1.1 के गुणांक में वृद्धि होने से निष्पादन का समय लगभग आधा हो गया और उसी मार्ग को बनाए रखा।


आप इसे अधिक से अधिक व्यापार करने में सक्षम होना चाहिए। विकिपीडिया पर अनुकूलनशीलता और अनुकूलता देखें।

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

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

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


इस समस्या के लिए विशेषज्ञ एल्गोरिदम हैं जो बहुत पूर्व गणना करते हैं। स्मृति से, पूर्व-संगणना ग्राफ़ को जानकारी जोड़ता है जो A * का उपयोग सीधी रेखा की तुलना में बहुत अधिक सटीक अनुमान लगाने में करता है। विकिपीडिया http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks पर कई विधियों के नाम देता है और कहता है कि हब लेबलिंग नेता है। इस पर एक त्वरित खोज http://research.microsoft.com/pubs/142356/HL-TR.pdf । A * का उपयोग करने वाला एक पुराना, http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf

क्या आपको वास्तव में हेवेर्सिन का उपयोग करने की आवश्यकता है? लंदन को कवर करने के लिए, मैंने सोचा होगा कि आप एक सपाट पृथ्वी मान सकते थे और पाइथागोरस का उपयोग कर सकते थे, या ग्राफ में प्रत्येक लिंक की लंबाई संग्रहीत कर सकते थे।


दर्जनों ए * भिन्नताएं हैं जो यहां बिल को फिट कर सकती हैं। आपको अपने उपयोग के मामलों के बारे में सोचना होगा, हालांकि।

  • क्या आप स्मृति हैं- (और कैश भी) विवश हैं?
  • क्या आप खोज को समानांतर कर सकते हैं?
  • क्या आपके एल्गोरिथ्म कार्यान्वयन को केवल एक स्थान पर उपयोग किया जाएगा (जैसे ग्रेटर लंदन और एनवाईसी या मुंबई या जहां भी)?

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

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

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

Precomputing दूसरा है, और बदलते कंपाइलर एक स्पष्ट तीसरा विचार हो सकता है (C या C ++ पर स्विच करें - विवरण के लिए https://benchmarksgame.alioth.debian.org/ देखें)।

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


मुझे लगता है कि यह "क्वाड्रंट्स" के साथ आपके विचार को वर्क-आउट करने लायक है। अधिक सख्ती से, मैं इसे कम-रिज़ॉल्यूशन मार्ग खोज कहूंगा।

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

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

यह केवल उच्च / निम्न नहीं, बल्कि कई प्रस्तावों के लिए भी सामान्यीकृत किया जा सकता है।

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


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

सबसे पहले, ए * पूरी तरह से पुराना है। इसका मुख्य लाभ यह है कि इसे "तकनीकी रूप से" प्रीप्रोसेसिंग की आवश्यकता नहीं है। व्यवहार में, आपको वैसे भी एक OSM मानचित्र को पूर्व-संसाधित करने की आवश्यकता होती है, ताकि व्यर्थ लाभ हो।

आपको एक बड़ी गति बढ़ाने के लिए मुख्य तकनीक चाप झंडे हैं। यदि आप मानचित्र को 5x6 खंडों में विभाजित करते हैं, तो आप प्रत्येक खंड के लिए 32 बिट्स पूर्णांक में 1 बिट स्थिति आवंटित कर सकते हैं। अब आप प्रत्येक किनारे के लिए यह निर्धारित कर सकते हैं कि क्या किसी खंड से {X,Y} अनुभाग में जाते समय यह कभी उपयोगी है। अक्सर, सड़कें अप्रत्यक्ष होती हैं और इसका मतलब है कि दोनों दिशाओं में से केवल एक ही उपयोगी है। तो दो दिशाओं में से एक में वह बिट सेट है, और दूसरे ने इसे मंजूरी दे दी है। यह एक वास्तविक लाभ प्रतीत नहीं हो सकता है, लेकिन इसका मतलब यह है कि कई चौराहों पर आप विकल्पों की संख्या को 2 से 1 तक विचार करने के लिए कम कर देते हैं, और यह सिर्फ एक बिट ऑपरेशन लेता है।





a-star