توجيه الخريطة، على غرار خرائط جوجل؟

Question

لقد كنت دائمًا مفتونًا بتوجيه الخريطة، لكنني لم أجد أبدًا أي برامج تعليمية جيدة على المستوى التمهيدي (أو حتى المتقدم!) حول هذا الموضوع.هل لدى أي شخص أي مؤشرات أو تلميحات وما إلى ذلك؟

تحديث: أنا أبحث في المقام الأول عن مؤشرات حول كيفية تنفيذ نظام الخرائط (هياكل البيانات، والخوارزميات، وما إلى ذلك).

Answer 1

نلقي نظرة على مشروع خريطة الشارع المفتوح لنرى كيف يتم التعامل مع هذا النوع من الأشياء في مشروع برمجي مجاني حقًا باستخدام البيانات المقدمة والمرخصة من قبل المستخدم فقط والحصول على ويكي يحتوي على أشياء قد تجدها مثيرة للاهتمام.

قبل بضع سنوات، كان الرجال المشاركون يسيرون جدًا وأجابوا على الكثير من الأسئلة التي كانت لدي، لذلك لا أرى أي سبب يمنعهم من عدم كونهم مجموعة لطيفة.

Answer 2

كتب Barry Brumitt، أحد مهندسي ميزة العثور على الطريق في خرائط Google، منشورًا حول الموضوع قد يكون ذا أهمية:

الطريق إلى اكتشاف أفضل للمسار11/06/2007 03:47:00 مساءً

Answer 3

A* هو في الواقع أقرب بكثير إلى خوارزميات تعيين الإنتاج.إنه يتطلب استكشافًا أقل قليلاً مقارنة بخوارزمية Dijikstra الأصلية.

Answer 4

من خلال توجيه الخريطة، هل تقصد العثور على أقصر مسار على طول شبكة الشوارع؟

خوارزمية Dijkstra للمسار الأقصر هي الأكثر شهرة.ويكيبيديا لا تحتوي على مقدمة سيئة: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

يوجد تطبيق Java صغير هنا حيث يمكنك رؤيته أثناء العمل: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html وGoogle تقودك إلى كود المصدر بأي لغة تقريبًا.

سيتضمن أي تنفيذ حقيقي لإنشاء مسارات القيادة قدرًا كبيرًا من البيانات على شبكة الشوارع التي تصف التكاليف المرتبطة بعبور الروابط والعقد - التسلسل الهرمي لشبكة الطرق، ومتوسط ​​السرعة، وأولوية التقاطع، وربط إشارات المرور، والمنعطفات المحظورة وما إلى ذلك.

Answer 5

بدلاً من تعلم واجهات برمجة التطبيقات لكل مزود خدمة خرائط (مثل Gmaps وYmaps api) من الجيد أن تتعلم رسم الخرائط

"Mapstraction هي مكتبة توفر واجهة برمجة تطبيقات مشتركة لمختلف واجهات برمجة تطبيقات تعيين جافا سكريبت"

أود أن أقترح عليك الانتقال إلى عنوان URL والتعرف على واجهة برمجة التطبيقات العامة.هناك قدر لا بأس به من الإرشادات أيضًا.

Answer 6

لم أجد بعد برنامجًا تعليميًا جيدًا حول التوجيه ولكن هناك الكثير من التعليمات البرمجية التي يجب قراءتها:

هناك تطبيقات توجيه GPL تستخدم بيانات Openstreetmap، على سبيل المثال. جوسمور الذي يعمل على نظامي التشغيل Windows (+ mobile) و Linux.هناك عدد من [التطبيقات المثيرة للاهتمام التي تستخدم نفس البيانات، ولكن لدى gosmore بعض الاستخدامات الرائعة على سبيل المثالواجهة مع المواقع.

أكبر مشكلة في التوجيه هي البيانات السيئة، ولن تحصل أبدًا على بيانات جيدة كافية.لذا، إذا كنت ترغب في تجربته، فاحتفظ باختبارك محليًا للغاية حتى تتمكن من التحكم في البيانات بشكل أفضل.

Answer 7

من وجهة نظر مفاهيمية، تخيل إسقاط حجر في بركة ومشاهدة التموجات.ستمثل المسارات البركة والحجر موضع البداية.

بالطبع سيتعين على الخوارزمية البحث في نسبة معينة من مسارات n^2 مع زيادة المسافة n.ستأخذك إلى موضع البداية وتتحقق من جميع المسارات المتاحة من تلك النقطة.ثم قم باستدعاء النقاط الموجودة في نهاية تلك المسارات بشكل متكرر، وهكذا.

يمكنك زيادة الأداء، من خلال عدم النسخ المزدوج للمسار، وعدم إعادة التحقق من المسارات عند نقطة ما إذا كانت قد تمت تغطيتها بالفعل، والتخلي عن المسارات التي تستغرق وقتًا طويلاً.

هناك طريقة بديلة تتمثل في استخدام نهج فرمون النمل، حيث يزحف النمل بشكل عشوائي من نقطة البداية ويترك أثرًا للرائحة، مما يؤدي إلى زيادة عدد النمل الذي يعبر مسارًا معينًا.إذا أرسلت (ما يكفي) من النمل من نقطة البداية ونقطة النهاية، ففي النهاية سيكون المسار ذو الرائحة الأقوى هو الأقصر.وذلك لأن أقصر طريق سيتم زيارته مرات أكثر في فترة زمنية معينة، نظرًا لأن النمل يسير بخطى موحدة.

تحرير @ سبايكي

كشرح إضافي لكيفية تنفيذ خوارزمية البركة - تم تسليط الضوء على هياكل البيانات المحتملة المطلوبة:

ستحتاج إلى تخزين الخريطة كشبكة.هذه مجرد مجموعة من nodes و edges بينهم.مجموعه من nodes تشكل أ route.تربط الحافة عقدتين (من المحتمل أن تكونا نفس العقدة)، ولها عقدة مرتبطة بها cost مثل distance أو time لاجتياز الحافة.يمكن أن تكون الحافة إما ثنائية الاتجاه أو أحادية الاتجاه.ربما يكون من الأسهل أن يكون لديك نقاط أحادية الاتجاه ومضاعفة السفر في اتجاهين بين العقد (أي.حافة واحدة من A إلى B وأخرى مختلفة من B إلى A).

على سبيل المثال، تخيل ثلاث محطات للسكك الحديدية مرتبة في مثلث متساوي الأضلاع يشير إلى الأعلى.هناك أيضًا ثلاث محطات أخرى في منتصف الطريق بينهما.تربط الحواف جميع المحطات المجاورة معًا، وسيحتوي المخطط النهائي على مثلث مقلوب يقع داخل المثلث الأكبر.

تبدأ عقد التسمية من أسفل اليسار، ومن اليسار إلى اليمين وما فوق، مثل A، B، C، D، E، F (F في الأعلى).

افترض أنه يمكن اجتياز الحواف في أي من الاتجاهين.تبلغ تكلفة كل حافة 1 كم.

حسنًا، نريد التوجيه من أسفل اليسار A إلى المحطة العليا F.هناك العديد من الطرق المحتملة، بما في ذلك تلك التي تتضاعف على نفسها، على سبيل المثال.ABCEBDEF.

لدينا روتين يقول، NextNode, ، الذي يقبل أ node و أ cost ويطلق على نفسه اسم كل عقدة يمكنه السفر إليها.

من الواضح أنه إذا سمحنا بتشغيل هذا الروتين، فإنه سيكتشف في النهاية جميع المسارات، بما في ذلك المسارات التي من المحتمل أن تكون لا نهائية الطول (مثل ABABABAB وما إلى ذلك).نحن نمنع حدوث ذلك عن طريق التحقق من cost.عندما نقوم بزيارة عقدة لم تتم زيارتها من قبل، فإننا نضع التكلفة والعقدة التي أتينا منها مقابل تلك العقدة.إذا تمت زيارة العقدة قبل التحقق من التكلفة الحالية وإذا كنا أرخص، فإننا نقوم بتحديث العقدة ونواصل (التكرار).إذا كنا أكثر تكلفة، فإننا نتخطى العقدة.إذا تم تخطي كافة العقد فإننا نخرج من الروتين.

إذا وصلنا إلى العقدة المستهدفة فإننا نخرج من الروتين أيضًا.

بهذه الطريقة يتم فحص جميع الطرق القابلة للتطبيق، ولكن الأهم هو فقط تلك الطرق ذات التكلفة الأقل.بحلول نهاية العملية، سيكون لكل عقدة أقل تكلفة للوصول إلى تلك العقدة، بما في ذلك العقدة المستهدفة.

للحصول على المسار، نعمل بشكل عكسي من العقدة المستهدفة.نظرًا لأننا قمنا بتخزين العقدة التي أتينا منها مع التكلفة، فإننا نقفز للخلف لبناء المسار.في مثالنا، سننتهي بشيء مثل:

العقدة أ - التكلفة (الإجمالية) 0 - من العقدة لا شيء
العقدة ب - التكلفة 1 - من العقدة أ
العقدة C - التكلفة 2 - من العقدة B
العقدة د - التكلفة 1 - من العقدة أ
العقدة E - التكلفة 2 - من العقدة D / التكلفة 2 - من العقدة B (هذا استثناء حيث أن هناك تكلفة متساوية)
العقدة F - التكلفة 2 - من العقدة D

وبالتالي فإن أقصر طريق هو ADF.

Answer 8

من خلال خبرتي في العمل في هذا المجال، يقوم A* بهذه المهمة بشكل جيد جدًا.إنها (كما ذكرنا أعلاه) أسرع من خوارزمية ديكسترا، لكنها لا تزال بسيطة بما يكفي ليتمكن المبرمج المختص عادةً من تنفيذها وفهمها.

يعد إنشاء شبكة الطرق هو الجزء الأصعب، ولكن يمكن تقسيم ذلك إلى سلسلة من الخطوات البسيطة:الحصول على كل الطرق.فرز النقاط بالترتيب؛إنشاء مجموعات من النقاط المتماثلة على طرق مختلفة في تقاطعات (عقد)؛أضف أقواسًا في كلا الاتجاهين حيث تتصل العقد (أو في اتجاه واحد فقط لطريق ذو اتجاه واحد).

خوارزمية A * نفسها موثقة بشكل جيد على ويكيبيديا.المكان الرئيسي للتحسين هو اختيار أفضل عقدة من القائمة المفتوحة، والتي تحتاج إلى قائمة انتظار ذات أولوية عالية الأداء.إذا كنت تستخدم C++، فيمكنك استخدام محول STL Priority_queue.

يعد تخصيص الخوارزمية للتوجيه عبر أجزاء مختلفة من الشبكة (على سبيل المثال، المشاة، السيارة، وسائل النقل العام، وما إلى ذلك) حسب السرعة أو المسافة أو معايير أخرى أمرًا سهلاً للغاية.يمكنك القيام بذلك عن طريق كتابة عوامل التصفية للتحكم في مقاطع المسار المتوفرة، عند إنشاء الشبكة، والوزن المخصص لكل منها.

Answer 9

خطرت لي فكرة أخرى فيما يتعلق بتكلفة كل اجتياز، ولكنها ستزيد من الوقت وقوة المعالجة المطلوبة للحساب.

مثال: هناك 3 طرق يمكنني اتباعها (في المكان الذي أعيش فيه) للانتقال من النقطة أ إلى النقطة ب، وفقًا لخرائط Google.تقدم وحدات Garmin كلاً من هذه المسارات الثلاثة في Quickest حساب الطريق.بعد اجتياز كل من هذه الطرق عدة مرات وحساب المتوسط ​​(من الواضح أنه ستكون هناك أخطاء اعتمادًا على الوقت من اليوم وكمية الكافيين وما إلى ذلك)، أشعر أن الخوارزميات يمكن أن تأخذ في الاعتبار عدد الانحناءات في الطريق للحصول على مستوى عالٍ من الدقة , على سبيل المثال سيكون الطريق المستقيم الذي يبلغ طوله ميلًا واحدًا أسرع من الطريق الذي يبلغ طوله ميلًا واحدًا والذي يحتوي على انحناءات حادة.ليس اقتراحًا عمليًا ولكنه بالتأكيد اقتراح أستخدمه لتحسين مجموعة نتائج تنقلاتي اليومية.