मानचित्र रूटिंग, एक ला Google मानचित्र?

मै मैप रूटिंग द्वारा हमेशा चिंतित हूं, लेकिन मुझे कभी भी कोई अच्छा प्रारंभिक (या यहां तक ​​कि उन्नत!) स्तर ट्यूटोरियल नहीं मिला है। क्या किसी के पास कोई पॉइंटर्स, संकेत इत्यादि हैं?

Update: I'm primarily looking for pointers as to how a map system is implemented (data structures, algorithms, etc).

0
जोड़ा संपादित
विचारों: 3

9 उत्तर

एक ट्रूली फ्री सॉफ़्टवेयर में इस प्रकार की चीज़ को कैसे हल किया जा रहा है यह देखने के लिए खुली सड़क मानचित्र परियोजना पर एक नज़र डालें प्रोजेक्ट केवल उपयोगकर्ता द्वारा प्रदान किए गए और लाइसेंस प्राप्त डेटा का उपयोग करके और एक विकी युक्त सामग्री जिसमें आपको दिलचस्प लगे

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

0
जोड़ा

Instead of learning APIs to each map service provider ( like Gmaps, Ymaps api) Its good to learn Mapstraction

"मैडस्ट्रक्शन एक लाइब्रेरी है जो विभिन्न जावास्क्रिप्ट मैपिंग एपीआई के लिए एक सामान्य एपीआई प्रदान करती है"

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

0
जोड़ा

Google मानचित्र मार्ग खोज सुविधा के इंजीनियरों में से एक बैरी ब्रुमिट ने इस विषय पर एक पोस्ट लिखा है जो ब्याज की हो सकती है:

The road to better path-finding 11/06/2007 03:47:00 PM

0
जोड़ा

मानचित्र रूटिंग द्वारा, आप सड़क नेटवर्क के साथ सबसे छोटा रास्ता खोजना चाहते हैं?

Dijkstra shortest-path algorithm is the best known. Wikipedia has not a bad intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

यहां जावा ऐपलेट है जहां आप इसे क्रिया में देख सकते हैं: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html और Google आप किसी भी भाषा में आपको स्रोत कोड पर ले जाते हैं।

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

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

मुझे अभी तक रूटिंग पर एक अच्छा ट्यूटोरियल नहीं मिला है लेकिन पढ़ने के लिए बहुत सारे कोड हैं:

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

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

0
जोड़ा

ए * वास्तव में उत्पादन मैपिंग एल्गोरिदम के करीब है। डिजिक्स्ट्रा के मूल एल्गोरिदम की तुलना में इसे काफी कम खोज की आवश्यकता है।

0
जोड़ा
असल में, संशोधित डी * आमतौर पर जहां तक ​​मुझे पता है, आमतौर पर उपयोग किया जाता है।
जोड़ा लेखक mmcdole, स्रोत

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

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

यदि आप पहले से ही कवर हो चुके हैं और बहुत लंबे समय तक चल रहे पथों को छोड़कर मार्ग पर दोबारा जांच नहीं कर रहे हैं, तो पथ पर दोबारा समर्थन न करके आप प्रदर्शन बढ़ा सकते हैं।

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

संपादित करें @ स्पाइकी

तालाब एल्गोरिदम को कार्यान्वित करने के तरीके के बारे में एक और स्पष्टीकरण के रूप में - संभावित डेटा संरचनाओं को हाइलाइट किया गया है:

आपको मानचित्र को नेटवर्क के रूप में स्टोर करने की आवश्यकता होगी। यह बस उनके बीच नोड्स और edges का एक सेट है। नोड्स का एक सेट मार्ग का गठन करता है। एक किनारा दो नोड्स (संभवतः एक ही नोड दोनों) में शामिल होता है, और किनारे को पार करने के लिए cost या time जैसे संबद्ध लागत होता है। एक किनारा या तो द्वि-दिशात्मक या यूनी-दिशात्मक हो सकता है। संभवतः यूनी-दिशात्मक वाले लोगों के लिए सबसे सरल और नोड्स के बीच दो तरह की यात्रा के लिए दोहराएं (यानी ए से बी के किनारे और बी से ए के लिए एक अलग)।

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

नीचे बाईं ओर से शुरू होने वाले लेबल नोड्स, ए, बी, सी, डी, ई, एफ (शीर्ष पर एफ) के रूप में बाएं से दाएं और ऊपर जा रहे हैं।

मान लें कि किनारों को किसी भी दिशा में घुमाया जा सकता है। प्रत्येक किनारे की लागत 1 किमी है।

ठीक है, इसलिए हम नीचे बाएं ए से शीर्ष स्टेशन एफ तक मार्ग बनाना चाहते हैं। ऐसे कई संभावित मार्ग हैं, जिनमें स्वयं को दोहराएं, उदा। ABCEBDEF।

हमारे पास नियमित रूप से कहना है, NextNode , जो नोड और लागत स्वीकार करता है और प्रत्येक नोड के लिए स्वयं को कॉल करता है, जिस पर वह यात्रा कर सकता है।

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

अगर हम अपने लक्ष्य नोड को दबाते हैं तो हम दिनचर्या से भी बाहर निकलते हैं।

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

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

Node A - (Total) Cost 0 - From Node None
Node B - Cost 1 - From Node A
Node C - Cost 2 - From Node B
Node D - Cost 1 - From Node A
Node E - Cost 2 - From Node D / Cost 2 - From Node B (this is an exception as there is equal cost)
Node F - Cost 2 - From Node D

तो सबसे छोटा रास्ता एडीएफ है।

0
जोड़ा
@ जोनाथन कृपया आप तालाब एल्गोरिदम में पत्थर का विवरण दे सकते हैं और मैं इसे मानचित्र पर कैसे लागू कर सकता हूं। मुझे लगता है कि मैं एक बिंदु पर हूं और मैं अगले बाहरी लहर पर जाने से पहले लहर में चारों ओर खोजना चाहता हूं। और दोस्त मुझे पता है और बातचीत के लिए 2 साल देर हो चुकी है
जोड़ा लेखक Spikie, स्रोत

प्रत्येक ट्रैवर्सल की लागत के संबंध में मेरे लिए एक और विचार होता है, लेकिन गणना करने के लिए आवश्यक समय और प्रसंस्करण शक्ति में वृद्धि होगी।

Example: There are 3 ways I can take (where I live) to go from point A to B, according to the GoogleMaps. Garmin units offer each of these 3 paths in the Quickest route calculation. After traversing each of these routes many times and averaging (obviously there will be errors depending on the time of day, amount of caffeine etc.), I feel the algorithms could take into account the number of bends in the road for high level of accuracy, e.g. straight road of 1 mile will be quicker than a 1 mile road with sharp bends in it. Not a practical suggestion but certainly one I use to improve the result set of my daily commute.

0
जोड़ा

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

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

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

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

0
जोड़ा