خوارزمية سوربال

في علوم الحاسوب النظرية وتوجيه الشبكات ، تُعدّ خوارزمية سوربال خوارزميةً لإيجاد مسارين منفصلين في رسم بياني موجه ذي أوزان غير سالبة ، بحيث يربط كلا المسارين نفس زوج الرؤوس ويكون لهما أقصر طول إجمالي. ^{[ 1 ]} ابتكر جون دبليو سوربال هذه الخوارزمية ونُشرت عام 1974. ^{[ 2 ]} تقوم فكرة خوارزمية سوربال الرئيسية على استخدام خوارزمية ديكسترا لإيجاد مسار واحد، ثم تعديل أوزان حواف الرسم البياني، ثم تشغيل خوارزمية ديكسترا مرة ثانية. يتكون ناتج الخوارزمية من دمج هذين المسارين، مع استبعاد الحواف التي يسلكها المساران في اتجاهين متعاكسين، واستخدام الحواف المتبقية لتكوين المسارين اللذين يُعادان كناتج. إن تعديل الأوزان مشابه لتعديل الوزن في خوارزمية جونسون ، ويحافظ على عدم سلبية الأوزان مع السماح للنسخة الثانية من خوارزمية ديكسترا بالعثور على المسار الثاني الصحيح.

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

ليكن G رسمًا بيانيًا موجهًا مُثقَّلًا بمجموعة رؤوس V ومجموعة حواف E (الشكل A)؛ وليكن s رأسًا مصدرًا مُعيَّنًا في G ، وليكن t رأسًا وجهة مُعيَّنًا. ولتكن تكلفة كل حافة ( u , v ) في E ، من الرأس u إلى الرأس v ، غير سالبة w ( u , v ) .

عرّف d( s , u ) على أنه تكلفة أقصر مسار إلى الرأس u من الرأس s في شجرة أقصر مسار التي جذرها s (الشكل C).

ملاحظة: غالبًا ما يتم استخدام مصطلحي العقدة والرأس بشكل متبادل.

تقوم خوارزمية سوربال بالخطوات التالية:

1. أوجد شجرة أقصر مسار T التي جذرها العقدة s بتطبيق خوارزمية ديكسترا (الشكل C). تحتوي هذه الشجرة على أقصر مسار من s إلى u لكل رأس u . ليكن P1 أقصر مسار تكلفة من s إلى t (الشكل B). تُسمى الحواف في T حواف الشجرة ، بينما تُسمى الحواف المتبقية (الحواف غير الظاهرة في الشكل C) _حواف غير الشجرة .
2. عدّل تكلفة كل حافة في الرسم البياني باستبدال التكلفة w ( u , v ) لكل حافة ( u , v ) بالتكلفة w′ ( u , v ) = w ( u , v ) − d( s , v ) + d( s , u ) . وفقًا لدالة التكلفة المعدلة الناتجة، تكون تكلفة جميع حواف الشجرة صفرًا، بينما تكون تكلفة الحواف غير الشجرية غير سالبة. على سبيل المثال: إذا كانت u = B و v = E ، فإن w′ ( u , v ) = w (B, E) − d(A, E) + d(A, B) = 2 − 3 + 1 = 0. وإذا كانت u = E و v = B ، فإن w′ ( u , v ) = w (E, B) − d(A, B) + d(A, E) = 2 − 1 + 3 = 4.
3. قم بإنشاء رسم بياني متبقي G _t مكون من G عن طريق إزالة حواف G على المسار P ₁ التي تتجه إلى s ثم اعكس اتجاه الحواف ذات الطول الصفري على طول المسار P ₁ (الشكل D).
4. ابحث عن أقصر مسار P ₂ في الرسم البياني المتبقي G _t عن طريق تشغيل خوارزمية Dijkstra (الشكل E).
5. تجاهل الحواف المعكوسة للمسار _P2 من كلا المسارين. تشكل الحواف المتبقية من P1 _و P2 رسمًا بيانيًا فرعيًا بحافتين صادرتين عند s ، وحافتين واردتين عند t ، وحافة واردة وحافة صادرة عند كل رأس متبقٍ. بالتالي، _يتكون هذا الرسم البياني الفرعي من مسارين منفصلين من s إلى t ، وربما بعض الدورات الإضافية (ذات الطول الصفري). أعد المسارين المنفصلين من الرسم البياني الفرعي.

يوضح المثال التالي كيف تجد خوارزمية Suurballe أقصر زوج من المسارات المنفصلة من A إلى F.

يوضح الشكل أ الرسم البياني الموزون G.

الشكل B يحسب أقصر مسار P ₁ من A إلى F ( A – B – D – F ).

يوضح الشكل C أقصر مسار شجرة T التي جذرها A ، والمسافات المحسوبة من A إلى كل رأس ( u ).

يوضح الشكل D الرسم البياني المتبقي G _t مع التكلفة المحدثة لكل حافة وحواف المسار P ₁ المعكوسة.

الشكل E يحسب المسار P ₂ في الرسم البياني المتبقي G _t ( A – C – D – B – E – F ).

يوضح الشكل F كلاً من المسار P ₁ والمسار P ₂ .

يُحدد الشكل G أقصر زوج من المسارات المنفصلة بدمج حواف المسارين P1 و _P2 ، ثم حذف الحواف المعكوسة المشتركة بينهما ( B - D ). ونتيجةً لذلك، نحصل على أقصر زوجين من المسارات المنفصلة ( _A - B - E - F ) و( A - C - D - F ) .

وزن أي مسار من s إلى t في نظام الأوزان المعدل يساوي وزنه في الرسم البياني الأصلي، مطروحًا منه d( s , t ) . لذلك، فإن أقصر مسارين منفصلين في ظل الأوزان المعدلة هما نفس أقصر مسارين في الرسم البياني الأصلي، على الرغم من اختلاف أوزانهما.

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

تتطلب هذه الخوارزمية دورتين من خوارزمية ديكسترا. باستخدام أكوام فيبوناتشي ، يمكن تنفيذ كلتا الدورتين في وقت${\displaystyle O(|E|+|V|\log |V|)}$أين${\displaystyle |V|}$و${\displaystyle |E|}$يمثل عدد الرؤوس والحواف على التوالي. لذلك، ينطبق نفس الحد الزمني على خوارزمية سوربال.

تجد نسخة خوارزمية سوربال الموصوفة أعلاه مسارات ذات حواف منفصلة، ​​ولكنها قد تشترك في بعض الرؤوس. ويمكن استخدام الخوارزمية نفسها لإيجاد مسارات ذات رؤوس منفصلة، ​​وذلك باستبدال كل رأس بزوج من الرؤوس المجاورة، أحدهما يحمل جميع الروابط الواردة (u-in) للرأس الأصلي، والآخر يحمل جميع الروابط الصادرة (u-out) . يقابل مساران ذوا حواف منفصلة في هذا الرسم البياني المُعدَّل بالضرورة مسارين ذوي رؤوس منفصلة في الرسم البياني الأصلي، والعكس صحيح، لذا فإن تطبيق خوارزمية سوربال على الرسم البياني المُعدَّل ينتج عنه مساران ذوا رؤوس منفصلة في الرسم البياني الأصلي. كانت خوارزمية سوربال الأصلية، التي طُوِّرت عام ١٩٧٤، مخصصة لنسخة الرؤوس المنفصلة من المسألة، ثم وُسِّعت عام ١٩٨٤ بواسطة سوربال وتارجان لتشمل نسخة الحواف المنفصلة. ^{[ ٣ ]}

باستخدام نسخة معدلة من خوارزمية ديكسترا التي تحسب في نفس الوقت المسافات إلى كل رأس t في الرسوم البيانية G _t ، من الممكن أيضًا إيجاد الأطوال الإجمالية لأقصر أزواج المسارات من رأس مصدر معين s إلى كل رأس آخر في الرسم البياني، في فترة زمنية تتناسب مع حالة واحدة من خوارزمية ديكسترا.

ملاحظة: يتم ربط زوج الرؤوس المتجاورة الناتج عن الانقسام بحافة أحادية الاتجاه بتكلفة صفرية من الرأس الداخل إلى الرأس الخارج. يصبح رأس المصدر s-out ويصبح رأس الوجهة t-in .