ما خوارزميات حساب الاتجاهات من نقطة أ إلى نقطة ب على الخريطة ؟
https://stackoverflow.com/questions/430142
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
كيف مقدمي خريطة (مثل جوجل أو ياهو!خرائط) تشير إلى الاتجاهات ؟
أعني, ربما لديهم البيانات في العالم الحقيقي في شكل ما ، بالتأكيد بما في ذلك المسافات ولكن أيضا ربما أشياء مثل القيادة بسرعة ، وجود الأرصفة ، جداول القطار ، إلخ.ولكن لنفترض البيانات في أبسط شكل ، ويقول كبيرة جدا توجه الرسم البياني مع حافة الأوزان يعكس المسافات.كنت تريد أن تكون قادرة على بسرعة حساب الاتجاهات من واحد التعسفي نقطة إلى أخرى.في بعض الأحيان هذه النقاط سوف تكون قريبة من بعضها البعض (داخل المدينة) بينما في بعض الأحيان أنها سوف تكون متباعدة (عبر البلاد).
الرسم البياني الخوارزميات مثل الخاص ديكسترا خوارزمية لن تعمل لأن الرسم البياني هائلة.لحسن الحظ, خوارزميات الكشف عن مجريات الأمور مثل* سوف تعمل على الأرجح.ومع ذلك ، فإن البيانات هو منظم جدا ، وربما نوع من النهج المتدرج قد العمل ؟ (على سبيل المثال, تخزين precomputed الاتجاهات بين بعض "مفتاح" نقاط متباعدة ، وكذلك بعض الاتجاهات المحلية.ثم الاتجاهات لمدة سنتين بعيدة نقطة سيشمل المحلية الاتجاهات إلى النقاط الرئيسية العالمية الاتجاهات إلى نقطة رئيسية أخرى ، ومن ثم المحلية الاتجاهات مرة أخرى.)
ما الخوارزميات المستخدمة فعلا في الممارسة ؟
PS.هذا السؤال كان بدافع إيجاد المراوغات في رسم الخرائط على شبكة الإنترنت الاتجاهات.على عكس المثلث عدم المساواة في بعض الأحيان خرائط جوجل يعتقد أن X-Z يستغرق وقتا أطول و هو أبعد من استخدام وسيطة نقطة كما في X-Y-Z.ولكن ربما اتجاهات المشي تحسين معلمة أخرى أيضا ؟
PPS.هنا آخر انتهاك المساواة في المثلث الذي يشير إلى (لي) التي تستخدم نوعا من النهج المتدرج: X-Z مقابل X-Y-Z.السابق يبدو أن استخدام بارزة Boulevard de Sebastopol على الرغم من انها قليلا للخروج من الطريق.
تحرير:أيا من هذه الأمثلة يبدو أن العمل بعد الآن, ولكن على حد سواء في الوقت الأصلي بعد.
المحلول
يتحدث كشخص أمضى 18 شهرا في العمل في رسم الخرائط الشركة ، والتي تضمنت العمل على خوارزمية التوجيه...نعم ، الخاص ديكسترا لا تعمل مع بعض التعديلات:
- بدلا من القيام الخاص ديكسترا مرة من المصدر إلى دست ، عليك أن تبدأ في كل نهاية ، وتوسيع كلا الجانبين حتى يلتقيان في منتصف.هذا يلغي ما يقرب من نصف العمل (2*pi*(ص/2)^2 vs pi*r^2).
- لتجنب استكشاف الأزقة الخلفية من كل مدينة بين المصدر والوجهة ، يمكن أن يكون لديك عدة طبقات من بيانات الخريطة:A 'السريعة' الطبقة التي تحتوي فقط على الطرق السريعة ، 'الثانوية' الطبقة التي تحتوي على الثانوي فقط الشوارع ، وهكذا دواليك.ثم يمكنك استكشاف فقط أصغر أقسام أكثر تفصيلا طبقات ، وتوسيع عند الضرورة.ومن الواضح أن هذا الوصف يترك الكثير من التفاصيل, ولكن تحصل على هذه الفكرة.
مع تعديلات على طول تلك الخطوط ، يمكنك القيام به حتى عبر البلاد التوجيه في زمني معقول.
نصائح أخرى
هذا السؤال قد نشط في مجال البحوث في السنوات الأخيرة.الفكرة الرئيسية هي أن تفعل تجهيزها على الرسم البياني مرة واحدة, ، تسريع كل الاستعلامات التالية.مع هذه المعلومات الإضافية مسارات يمكن حسابه سريع جدا.لا يزال ، الخاص ديكسترا الخوارزمية هو أساس كل أمثلية.
عنكب ووصف استخدام ثنائي الاتجاه البحث حافة التقليم على أساس المعلومات الهرمية.هذه تسريع تقنيات تعمل بشكل جيد جدا, ولكن أحدث خوارزميات يتفوق هذه التقنيات بكل الوسائل.مع خوارزميات أقصر المسارات التي يمكن حسابها كبيرة في وقت أقل من ميلي ثانية واحدة على القاري شبكة الطرق.بسرعة تنفيذ معدلة خوارزمية الخاص ديكسترا يحتاج إلى حوالي 10 ثوان.
المادة الهندسة سريع تخطيط الطريق الخوارزميات يعطي لمحة عامة عن التقدم المحرز في البحوث في هذا المجال.راجع مراجع هذه الورقة للحصول على مزيد من المعلومات.
أسرع المعروف خوارزميات لا تستخدم معلومات حول الهرمية حالة الطرق في البيانات ، أيإذا كان الطريق أو الطرق المحلية.لكنهم بدلا من حساب في تجهيزها الخطوة الخاصة التسلسل الهرمي الذي الأمثل لتسريع تخطيط الطريق.هذا precomputation يمكن بعد ذلك أن تستخدم لتقليم البحث:بعيدا من البداية والوجهة بطيئة الطرق لا حاجة إلى النظر في خلال الخاص ديكسترا الخوارزمية.فوائد جيدة جدا الأداء و صحة ضمان النتيجة.
أول الأمثل تخطيط الطريق خوارزميات التعامل فقط مع ساكنة شبكات الطرق ، وهذا يعني ميزة في الرسم البياني تكلفة ثابتة القيمة.هذا ليس صحيحا في الواقع ، منذ كنا نريد أن نأخذ المعلومات الحيوية مثل الاختناقات المرورية أو مركبة تعتمد restrictrions في الاعتبار.أحدث خوارزميات يمكن أيضا التعامل مع مثل هذه القضايا ، ولكن لا تزال هناك مشاكل لحل البحث يجري.
إذا كنت بحاجة إلى مسار أقصر المسافات لحساب حل ملعقة صغيرة, ثم ربما كنت ترغب في المصفوفات التي تحتوي على جميع المسافات بين المصادر والوجهات.لهذا يمكن النظر في الحوسبة كثير إلى كثير من أقصر الطرق باستخدام الطريق السريع الهرمية.نلاحظ أن هذا قد تحسنت من خلال أحدث المناهج في الماضي 2 سنوات.
وفقط معالجة انتهاكات مثلث عدم المساواة، ونأمل عامل إضافي انهم الأمثل لهو الحس السليم. كنت لا تريد بالضرورة أقصر أو أسرع الطرق، لأنها يمكن أن تؤدي إلى الفوضى و <لأ href = "HTTP: // www.theregister.co.uk/2007/02/20/hampshire_satnav/ "يختلط =" noreferrer "> تدمير . إذا كنت تريد الاتجاهات لأفضل الطرق الرئيسية التي هي صديقة للشاحنة، ويمكن التعامل مع وجود كل سبت-الملاحة التالية سائق أنزل عليهم، لك بسرعة تجاهل متباينة المثلث [1].
إذا Y هو شارع سكني ضيق بين X و Z، وربما كنت ترغب فقط في استخدام الاختصار عبر Y إذا كان المستخدم يطلب صراحة X-Y-Z. اذا طلبوا X-Z، ينبغي أن التمسك الطرق الرئيسية حتى لو كان أبعد قليلا وقتا أطول قليلا. انها مماثلة ل مفارقة Braess في - إذا كان الجميع يحاول أن يأخذ أقصر، الطريق الأسرع، مما أسفر عن وسائل الازدحام انها ليست الطريق الأسرع لأحد أي أكثر من ذلك. من هنا نحن تبتعد عن نظرية الرسم البياني إلى نظرية اللعبة.
[1] في الواقع، أي نأمل أن المسافات المنتجة سوف تكون وظيفة المسافة بالمعنى الرياضي تموت عندما تسمح الطرق في اتجاه واحد وفقدان شرط التماثل. فقدان متباينة المثلث جدا هو مجرد فرك الملح في الجرح.
هنا هو الأسرع في العالم خوارزميات التوجيه مقارنة وثبت على الصواب:
http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf
وهنا google tech talk على هذا الموضوع:
http://www.youtube.com/watch?v=-0ErpE8tQbw
وهنا تنفيذ الطريق السريع-الهرمية خوارزمية كما نوقش من قبل schultes (حاليا في برلين فقط أكتب واجهة النسخة المحمولة ويجري كذلك):
وأنا لم يعمل على جوجل أو مايكروسوفت أو خرائط ياهو قبل، لذلك لا استطيع ان اقول لكم كيفية عملها.
ولكن، لم أكن مهندس نظام سلسلة التوريد الأمثل مخصصة لشركة الطاقة التي تضمنت جدولة وتطبيق التوجيه لأسطولها من الشاحنات. ومع ذلك، كانت معاييرنا على التوجيه أكثر بكثير للأعمال تحديدا من حيث هو البناء أو الحركة تبطئ أو إغلاق الممر.
واستخدمنا تقنية تسمى ACO (النمل الأمثل مستعمرة) لتحديد موعد والشاحنات الطريق. هذه التقنية هي تقنية AI التي تم تطبيقها لمشكلة السفر بائع لحل مشاكل التوجيه. خدعة مع ACO هي بناء حساب الخطأ استنادا إلى الحقائق المعروفة من التوجيه بحيث نموذج الرسم البياني حل يعرف متى لإنهاء (عندما يكون الخطأ صغيرا بما فيه الكفاية).
ويمكنك جوجل ACO أو TSP للعثور على مزيد من المعلومات حول هذه التقنية. أنا لم تستخدم أي من المصادر المفتوحة أدوات AI لهذا ومع ذلك، بحيث لا يمكن أن تشير إلى واحد (على الرغم من أنني سمعت كان SWARM شامل جدا).
وسوف خوارزميات الرسم البياني مثل خوارزمية ديكسترا لا تعمل لأن الرسم البياني هائلة.
وهذه الحجة لا يحمل بالضرورة لأن ديكسترا لا تبدو عادة في الرسم البياني الكامل بل مجرد مجموعة فرعية صغيرة جدا (أفضل المترابط الرسم البياني، أصغر هذه المجموعة الفرعية).
وديكسترا قد تؤدي في الواقع بشكل جيد وليس لالرسوم البيانية حسن تصرف. من ناحية أخرى، مع الحذر تمثيل وسيطي A * سوف تؤدي دائما مجرد جيدة، أو أفضل منه. هل حاولت بالفعل كيف يمكن ان تؤدي على البيانات الخاصة بك؟
وقال ذلك، فما استقاموا لكم فاستقيموا تكون مهتمة ايضا جدا أن نسمع عن تجارب الشعوب الأخرى. وبطبيعة الحال، أمثلة بارزة مثل البحث خريطة جوجل هي مثيرة للاهتمام بشكل خاص. يمكنني أن أتصور ما يشبه أقرب ارشادي جار لتوجيهات.
والوضع الحالي للفن من حيث مرات الاستعلام عن شبكات الطرق الثابتة هي خوارزمية محور العلامات التي اقترحها إبراهيم وآخرون. http://link.springer.com/chapter/10.1007/978-3-642- 20662-7_20 . ونشرت الدراسة من خلال ومكتوبة بشكل ممتاز الحقل مؤخرا في التقرير الفني ل HTTP: / /research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .
والنص القصير هو ...
والخوارزمية محور العلامات تقدم أسرع الاستعلامات للشبكات الطرق ثابتة ولكنها تتطلب كمية كبيرة من ذاكرة الوصول العشوائي لتشغيل (18 بنك الخليج الدولي).
وعقدة العبور التوجيه أبطأ قليلا، على الرغم من ذلك، فإنه يتطلب فقط حوالي 2 بنك الخليج الدولي من الذاكرة ولديه وقت أسرع تجهيزها.
تقدموالتدرجات انكماش التجارة لطيفة من بين أوقات سريعة تجهيزها، ومتطلبات مساحة منخفضة (0.4 بنك الخليج الدولي) والأوقات الاستعلام السريعة.
ولا خوارزمية واحدة هي تسيطر تماما ...
وهذا الكلام التكنولوجيا جوجل بيتر ساندرز قد تكون ذات فائدة
https://www.youtube.com/watch؟v=-0ErpE8tQbw
وأيضا هذا الحديث من قبل أندرو غولدبرغ
https://www.youtube.com/watch؟v=WPrkc78XLhw
وتنفيذا مفتوحة المصدر من التسلسلات الهرمية الانكماش هو متاح من بيتر ساندرز مجموعة البحث على الإنترنت في KIT. http://algo2.iti.kit.edu/english/routeplanning.php
وأيضا لبلوق وظيفة يمكن الوصول إليها بسهولة كتابتها من قبل Microsoft على وجود استخدام خوارزمية CRP ... <لأ href = "http://blogs.bing.com/maps/2012/01/05/bing-maps-new -routing محرك / "> http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/
وأنا قليلا فوجئت أن لا نرى خوارزمية فلويد ارشال في ذكرها هنا. هذا العمل الخوارزمية يشبه إلى حد كبير جدا في ديكسترا. كما أن لديها واحد ميزة جميلة جدا وهي أنه يسمح لك لحساب طالما كنت ترغب في الاستمرار في السماح لمزيد من القمم المتوسطة. لذلك سوف تجد بطبيعة الحال الطرق التي تستخدم الطرق السريعة أو الطرق السريعة بسرعة إلى حد ما.
ولقد فعلت ذلك تماما في الكثير من الأحيان، في الواقع، في محاولة عدة أساليب مختلفة. اعتمادا على حجم (الجغرافي) من الخريطة، قد ترغب في النظر في استخدام وظيفة haversine بمثابة الكشف عن مجريات الأمور.
وأفضل حل أخرجتها كان يستخدم A * مع مسافة خط مستقيم بوصفها وظيفة الكشف عن مجريات الأمور. ولكن بعد ذلك تحتاج نوعا من إحداثيات كل نقطة (تقاطع أو قمة الرأس) على الخريطة. يمكنك أيضا محاولة أوزان مختلفة لوظيفة الكشف عن مجريات الأمور، أي
f(n) = k*h(n) + g(n)
وحيث ك أكبر بعض ثابت من 0.
وربما مماثلة إلى الإجابة على طرق حسابها مسبقا بين المواقع الرئيسية وخرائط الطبقات، ولكن ما أفهمه هو أن في المباريات، لتسريع A *، لديك خريطة هذا هو الخشنة جدا للملاحة الكلي، وfine- خريطة الحبيبات للملاحة إلى حدود الاتجاهات الماكرو. بحيث يكون لديك 2 مسارات صغيرة لحساب، وبالتالي مساحة بحثك إلى حد أقل بكثير من مجرد القيام مسار واحد إلى الوجهة. وإذا كنت في الأعمال التجارية للقيام بذلك الكثير، وكنت لديهم الكثير من تلك البيانات قبل احتساب ذلك على الأقل جزء من البحث هو بحث عن البيانات المحسوبة مسبقا، بدلا من البحث عن المسار.
وهذا هو محض تكهنات من جانبي، ولكن أعتقد أنها قد تستخدم بنية بيانات خريطة النفوذ تتراكب الخريطة الموجهة لتضييق نطاق البحث. وسيتيح ذلك للخوارزمية البحث لتوجيه مسار إلى الطرق الرئيسية عندما رحلة المطلوب طويلة.
ونظرا إلى أن هذا هو التطبيق جوجل، كما انها المعقول أن نفترض أن الكثير من السحر يتم عن طريق التخزين المؤقت واسعة النطاق. :) أنا لن يفاجأ إذا التخزين المؤقت أعلى 5٪ الأكثر شيوعا خريطة جوجل توجيه طلبات يسمح لشريحة كبيرة (20٪؟ 50٪؟) طلبات ليتم الرد عليها من قبل بسيط نظرة المتابعة.
وكان لي بعض مزيد من الأفكار حول هذا:
1) تذكر أن الخرائط تمثل منظمة البدنية. تخزين خطوط العرض / الطول من كل تقاطع. كنت لا تحتاج إلى التحقق من ذلك بكثير أبعد النقاط التي تقع في اتجاه الهدف الخاص بك. إلا إذا كنت تجد نفسك سدت لا تحتاج للذهاب أبعد من ذلك. إذا قمت بتخزين تراكب اتصالات متفوقة يمكنك تحديد الأمر أكثر - سوف عادة لا تذهب عبر واحدة من تلك بطريقة يذهب بعيدا عن وجهتك النهائية
2) تقسيم العالم إلى مجموعة كاملة من المناطق التي يحددها الاتصال المحدود، وتحديد جميع نقاط الاتصال بين المناطق. البحث ما هي مناطق المصدر والهدف في، لبداية ونهاية الطريق منطقة من موقعك إلى كل نقطة اتصال، للمناطق بين الخريطة ببساطة بين نقاط الاتصال. (وأظن الكثير من هذا الأخير هو بالفعل قبل حساب).
ملحوظة أن المناطق يمكن أن يكون أصغر من منطقة حضرية. ومن شأن أي مدينة مع التضاريس التي تفرق عنه (ويقول، وهو النهر) يكون مناطق متعددة.
وكان من الغريب جدا عن الاستدلال المستخدمة، عندما في حين يعود حصلنا على الطرق من نفس انطلاق موقع بالقرب من سانتا روزا، إلى اثنين من المخيمات المختلفة في منتزه يوسمايت الوطني. هذه وجهات مختلفة أنتجت طرق مختلفة تماما (عن طريق I-580 أو CA-12) على الرغم من أن كلا الطريقين المتقاربة ل100 ميل مشاركة (جنبا إلى جنب CA-120) قبل متباينة مرة أخرى على بعد أميال قليلة في نهاية المطاف. وكان هذا تكرار للغاية. الطرق اثنين كانت تصل إلى 50 ميلا بحريا لحوالي 100 ميل، ولكن / مرات كانت المسافات قريبة جدا من بعضها البعض كما كنت تتوقع.
ولكن للأسف لا أستطيع أن تتكاثر - يجب أن تغيرت الخوارزميات. ولكن كان لي غريبة عن الخوارزمية. كل ما يمكنني التكهن هو أن هناك بعض التقليم الاتجاه الذي حدث أن تكون حساسة بشكل رائع الفرق الزاوي صغيرة بين الوجهات كما رأينا من بعيد، أو كانت هناك شرائح مختلفة precomputed يختارهم اختيار الوجهة النهائية.
بالحديث عن GraphHopper, سريع مفتوحة المصدر مخطط الطريق على أساس خريطة الشارع المفتوح ، لقد قرأت قليلا الأدب وتنفيذ بعض الأساليب.أبسط حل هو الخاص ديكسترا و تحسن بسيط ثنائي الاتجاه الخاص ديكسترا الذي يستكشف تقريبا سوى نصف العقد.مع bidirctional الخاص ديكسترا الطريق من خلال بأكمله ألمانيا يأخذ بالفعل 1sec (على وضع السيارة) في ج سيكون على الأرجح سوى 0.5 s أو نحو ذلك ;)
لقد قمت بإنشاء صورة gif متحركة حقيقية مسار البحث مع ثنائي الاتجاه الخاص ديكسترا هنا.أيضا هناك بعض الأفكار جعل الخاص ديكسترا أسرع مثل القيام* ، وهو "الهدف المنحى الخاص ديكسترا".أيضا لقد خلق gif المتحركة من أجل ذلك.
ولكن كيف نفعل ذلك (الكثير) أسرع ؟
المشكلة هي أن مسار البحث عن كافة العقد بين المواقع يكتشفها هذا هو حقا مكلفة كما سبق في ألمانيا هناك عدة ملايين منهم.ولكن إضافي نقطة الألم الخاص ديكسترا وما إلى ذلك هو أن مثل هذا البحث يستخدم الكثير من ذاكرة الوصول العشوائي.
هناك ارشادي الحلول ولكن أيضا الحلول الدقيقة التي organzize الرسم البياني (شبكة الطرق) في طبقات هرمية ، سواء لديهم pro&سلبيات و تحل بشكل رئيسي على سرعة ذاكرة الوصول العشوائي المشكلة.لقد سردت بعض منهم في هذا الجواب.
بالنسبة GraphHopper قررت استخدام انكماش الهرمية لأنه هو نسبي 'سهلة' لتنفيذ ولا تأخذ الأعمار إعداد الرسم البياني.فإنه لا يزال النتائج في أوقات استجابة سريعة مثل يمكنك اختبار في موقعنا على الانترنت سبيل المثال GraphHopper الخرائط.E. g. من جنوب أفريقيا إلى شرق الصين مما يؤدي 23000km المسافة ما يقرب من 14 يوما من وقت القيادة في السيارة و أخذت فقط ~0.1 s على الملقم.
ولقد عملت على توجيه لبضع سنوات، مع موجة الأخيرة من النشاط بدافع من احتياجات العملاء بلدي، ولقد وجدت أن A * بسهولة بسرعة كافية. هناك حقا لا حاجة للبحث عن تحقيق أمثلية أو أكثر خوارزميات معقدة. توجيه أكثر من الرسم البياني هائلة ليست مشكلة.
ولكن سرعة يعتمد على وجود شبكة التوجيه بأكملها، وأعني على مخطط موجه من الأقواس والعقد الذين يمثلون قطاعات الطرق والتقاطعات على التوالي، في الذاكرة. الساعة النفقات العامة الرئيسي هو الوقت اللازم لإنشاء هذه الشبكة. بعض الأرقام الخام على أساس الكمبيوتر المحمول العادي بنظام التشغيل Windows، والتوجيه على كامل إسبانيا: الوقت اللازم لإنشاء شبكة: 10-15 ثواني. الوقت اللازم لحساب المسار:. قصيرة جدا لقياس
والشيء الآخر المهم هو أن تكون قادرة على إعادة استخدام الشبكة للحصول على أكبر عدد ممكن من العمليات الحسابية التوجيه كما تريد. إذا الخوارزمية الخاصة بك اتسم العقد في بعض الطريق لتسجيل أفضل طريق (التكلفة الإجمالية لالعقدة الحالية، وأفضل قوس إلى ذلك) - كما أن في A * - لديك لإعادة تعيين أو مسح خارج هذه المعلومات القديمة. بدلا من الذهاب من خلال مئات الآلاف من العقد، فإنه من السهل أن استخدام نظام رقم الجيل. علامة كل عقدة مع عدد توليد البيانات الخاصة به. زيادة عدد جيل عند حساب طريقا جديدا. أي عقدة مع عدد الجيل الأكبر سنا هي التي لا معنى لها، ويمكن تجاهل المعلومات الخاصة به.
وأرى ما الأمر مع الخرائط في OP:
ونظرة على الطريق مع نقطة وسيطة المحدد: الطريق يذهب قليلا إلى الوراء بسبب هذا الطريق غير مباشرة
إذا وخوارزمية لا تتراجع أنها لن ترى طريقا أقصر.
وهناك كل أزواج أقصر خوارزمية مسار سوف يحسب أقصر الطرق بين جميع القمم في الرسم البياني. وهذا سوف يسمح مسارات ليكون قبل احتساب بدلا من مطالبة مسار يتم حسابها في كل مرة كان هناك من يريد العثور على أقصر مسار بين المصدر والوجهة. خوارزمية فلويد-ارشال هو الكل أزواج أقصر خوارزمية المسار.
وخرائط لم تأخذ بعين الاعتبار الخريطة كلها. تخميني هو:- 1. وفقا للموقع الخاص بك، وتحميل مكان والمعالم في ذلك المكان. 2. عند البحث في المقصد، ولهذا عندما تحميل الجزء الآخر من الخريطة وجعل الرسم البياني من مكانين ثم تطبيق أقصر خوارزميات المسار.
وبالإضافة إلى ذلك، هناك تقنية البرمجة الديناميكية الهامة التي أظن يستخدم في حساب أقصر الطرق. يمكنك الرجوع إلى ذلك أيضا.
