مئات الآلاف من المسارات في الثانية لكل نواة. Yandex.Routing Experience

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

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

لحل المشكلة مع خمسة آلاف طلب ، عليك معرفة المسافات وأوقات السفر بين جميع النقاط. هذان مصفوفة أرقام مع البعد 5000 × 5000. نحن نخطط لطرق البريد السريع طوال اليوم ، وفي الصباح سوف ينتقل الناقل من نقطة إلى نقطة في وقت واحد ، وفي المساء - لآخر. لذلك ، تحتاج إلى حساب مصفوفة الأوقات والمسافات لكل ساعة من اليوم. ليست كل ساعات اليوم فريدة من نوعها ، ولكن يجب تغطية وقت الفلين (في الصباح والمساء) جيدًا. لذلك ، وصلنا إلى تكوين مع شرائح 13 ساعة. في المجموع ، نحتاج إلى مكعبين (مرات ومسافات) كل منهما 13x5000x5000. هذه هي 325 مليون مسار ، محسوبة وفقًا للرسم البياني للطريق الحقيقي ، حيث 165 مليون حواف. يستغرق حساب مسار واحد في الخوارزمية المحسنة جيدًا لفريق Yandex.Maps حوالي 10 مللي ثانية ، ليصبح المجموع 900 ساعة من الحسابات.حتى عند موازاة 900 وحدة معالجة مركزية ، فأنت بحاجة إلى الانتظار لمدة ساعة. لم نتمكن من بدء مثل هذه الخدمة ، كنا بحاجة إلى خوارزمية أكثر ملاءمة.

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



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



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

قام فريق جهاز توجيه البطاقة بتنفيذ مثل هذه التحسينات لبعض الوقت. هم الذين جعلوا من الممكن تحقيق 10 مللي ثانية لإيجاد مسار بين نقطتين. :) حتى الآن ، لم نقترب من حل مشكلتنا.

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



ننظر في وقت حساب السلسلة باستخدام هذه الخوارزمية ونذكر أن الحساب المتسلسل لـ 5000 مسار سيستغرق حوالي 5000 * 10 مللي ثانية = 50 ثانية:


يوضح الرسم البياني وقت حساب صف في مصفوفة مسافة بحجم 1 * N لمختلف N (وفقًا للبيانات الحقيقية). يمكن ملاحظة أن حساب صف الحجم 1 * 5000 الذي يهمنا يتناسب مع 1.3 ثانية. تمت إضافة خط اتجاه إلى الرسم البياني ، مما يدل على أن وقت الحساب ينمو بشكل أبطأ قليلاً من خطياً في N ، ترتيب N ** 0.74

ليس سيئًا بالفعل! باستخدام هذه الخوارزمية ، يمكننا حساب المكعب في 13 * 5000 * 1.3 ثانية = 84500 ثانية = 24 ساعة تقريبًا. إنه يوازي بسهولة في الصفوف ، وعند استخدام 50 وحدة معالجة مركزية ، يتم حساب المسافات في نصف ساعة. ترتيب التعقيد لخوارزمية حساب المكعب هو O (N ** 1.74):


13 N*N 50 CPU ( 13*N/50). , 5000 , . 10 000, : .

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

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


حان الوقت لحساب مصفوفة واحدة بحجم N * N على وحدة معالجة مركزية واحدة باستخدام خوارزمية "المصفوفة السريعة". يتم الحصول على التعقيد بترتيب O (N ** 1،1). يتم إخراج High Ns من خط الاتجاه ، نظرًا لأن توليد الإجابة وتنزيلها عبر الشبكة يؤثران بالفعل على الوقت.

أصبحت 115 ثانية لكل مصفوفة 5000x5000 باستخدام قلب واحد واعتماد خطي تقريبًا على N. Fiction حقيقة! تجمع فكرة الخوارزمية بين الفكرتين الموصوفتين أعلاه: Dijkstra للسلسلة والبحث الهرمي. من الواضح ، بدءًا من حساب الصف الثاني ، في مرحلة ما ، سنتجول مرة أخرى حول نفس المنطقة من الرسم البياني التي مررنا بها للتو ، وحساب الصف السابق. لذلك ، دعونا نحفظ أقصر المسافات إلى جميع الوجهات في عقد الرسم البياني الهرمي. عندما نبدأ في حساب السلسلة التالية ، بعد الوصول إلى هذه العقدة ، سنحصل على الفور على جميع المسافات إلى نقاط أخرى.



قبل عام ونصف ، سمح لنا هذا بتوفير نصف ساعة من الوقت مع eاللوجستيات وتقليل كمية الحديد بشكل ملحوظ. في السابق ، لطلب واحد كبير ، كنا بحاجة إلى 50 نواة لمدة نصف ساعة ، ولكن الآن - 13 نوى لمدة دقيقتين. هذا هو ما يقرب من 200،000 مسار في الثانية لكل نواة. هذه الحالة النادرة عندما لا تغلق الخوارزمية الجديدة فئة المشاكل فحسب ، بل توسع أفكارنا حول الممكن.

---

_{^{* مقال "تخطيط المسار في شبكات النقل" ، انظر الفقرة 2.7.2 "أقصر الطرق المجمعة"}}