Bi Directional Dijkstra

ثنائي الاتجاه ديجكسترا

مشكلة

بالنظر إلى رسم بياني مع أوزان حافة غير سالبة ، فإن قمة المصدر S و vertec t الهدف. ابحث عن أقصر مسار بين S و T.

ولكن لماذا لا نستخدم خوارزمية Dijkstra لحل المشكلة؟

0 (E + VLOGV) هو أسوأ حالة تعقيد وقت في خوارزمية Dijkstra التي هي سريعة جدًا. ولكن ، بالنسبة لرسم بياني يحتوي على 20 مليون قمة و 50 مليون حواف ، ستعمل لعدة ثوان في المتوسط. لذلك ، نحن بحاجة إلى شيء أسرع بكثير.

قبل أن نذهب إلى تفاصيل البحث ثنائي الاتجاه ، دعونا نستكشف مفهوم "ست درجات من الانفصال"

• في عام 1929 ، اقترح مؤلف مجري ، فريجيس كارينثي لأول مرة مفهوم "ست درجات من الانفصال" في سلاسل قصته القصيرة.
• ست درجات من الانفصال هي فكرة أن جميع الكائنات الحية وكل شيء آخر في العالم هي ست خطوات أو أقل من بعضها البعض.

الآن ، دعنا ننظر إلى الشبكة الاجتماعية الأكثر شعبية ، Facebook. لنفترض أن الشخص العادي على Facebook لديه حوالي 100 صديق. ثم ، إذا اعتبرنا أصدقاء هذا الشخص ، فسيكون 100*100 هو 10000 صديق للأصدقاء. إذا اعتبرنا "أصدقاء الأصدقاء" ، فسيكون ذلك أكثر من 100 مرة أو مليون. وإذا واصلنا ذلك ست مرات ، فسيكون لدينا 1 تريليون شخص.

لكن السكان العالميين هو 7.6 مليار.

الآن ، كيف نجد أقصر مسار بين أي شخصين عشوائيين A و B عبر اتصالاتهما على الشبكة الاجتماعية؟

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

لاحظ أنه سيكون لدينا ما يقرب من مليار من أصدقاء الأصدقاء لكل من A و B. لذلك ، سننظر في المجموع 2 مليون شخص فقط في هذه الحالة.

سيتعين على خوارزمية Dijkstra العادية أن تبدو ما يقرب من مليوني شخص على الشبكة الاجتماعية لإيجاد أقصر مسار بين A و B.

ما هو البحث ثنائي الاتجاه

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

الكود الكاذب ل dijkstra ثنائية الاتجاه على الرسم البياني g

• Build GR (الرسم البياني المنعكس)
• ابدأ Dijkstra من S (المصدر) في G و T (Target) في GR
• البديل بين خطوات Dijkstra في G و GR
• توقف عندما تتم معالجة بعض قمة "V" في G و GR.
• حساب أقصر مسار بين S و T.

حساب أقصر مسار بين S و T: دعنا dist [u] هو تقدير المسافة في dijkstra إلى الأمام من S في G. دع توزيع [u] هو تقدير المسافة في dijkstra للخلف من t في gr. بعد أن تتم معالجة بعض العقدة "V" في G و GR على حد سواء ، يمر بعض أقصر المسار من S إلى T من خلال بعض العقدة "U" التي تتم معالجتها إما في G أو في GR أو كلاهما و D (S ، T) = Dist [u] + distr [u]