خوارزمية الدفع-إعادة التسمية
- قدّمه
- Andrew V. Goldberg and Robert E. Tarjan
- السنة
- 1988
- النوع
- algorithm
- العائلة
- Graph Algorithms
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تُعد خوارزمية الدفع-إعادة التسمية (Push-Relabel Algorithm)، التي طورها أندرو في. غولدبرغ وروبرت إي. تارغان في عام 1988، طريقة عالية الكفاءة لحساب التدفق الأقصى في الشبكات. على عكس طرق المسار المعزز، فإنها تحافظ على تدفق أولي (preflow) وتستخدم عمليات دفع محلية وإعادة تسمية شاملة لدفع التدفق نحو المصرف (sink)، محققة بذلك تعقيدًا أسوأ حالة متفوقًا.
الفكرة الحدسية وراء الطريقة
تحافظ الخوارزمية على 'ارتفاع' أو 'تسمية مسافة' لكل عقدة وتستخدم التدفق الأولي (حيث يمكن للعقد أن تتجاوز مؤقتًا طلب المصرف). تدفع بشكل متكرر التدفق الزائد من العقد ذات التسمية الأعلى إلى الجيران ذوي التسمية الأقل، وتعيد تسمية العقد لإنشاء مسارات إلى المصرف. تكمن الفكرة الرئيسية في أنه من خلال الحفاظ على ثوابت الارتفاع واستخدام هياكل بيانات فعالة، تتجنب الخوارزمية استكشاف الرسم البياني بأكمله بشكل متكرر، كما يجب أن تفعل طرق المسار المعزز. تتوقف الخوارزمية عندما يصل كل التدفق الزائد إلى المصرف.
التاريخ
نشر غولدبرغ وتارغان خوارزمية الدفع-إعادة التسمية في عام 1988، مقدمين نموذجًا مختلفًا جذريًا لحساب التدفق الأقصى. حققت خوارزميتهما تعقيدًا أسوأ حالة O(V³)، وهو تحسين على O(VE²) لخوارزمية إدموندز-كارب. على مدى العقود اللاحقة، تم تطوير العديد من المتغيرات، بما في ذلك استدلالات الفجوة (غولدبرغ وتارغان، 1990)، وقواعد التسمية الأعلى، وأحدث المتغيرات التي تحقق أداءً تجريبيًا شبه خطي على الشبكات الواقعية.
متى تُستخدم
طبق خوارزمية الدفع-إعادة التسمية لحساب التدفق الأقصى في الشبكات الكبيرة الكثيفة حيث تصبح طرق المسار المعزز غير فعالة. إنها فعالة بشكل خاص للشبكات التي تحتوي على آلاف أو ملايين الحواف. استخدمها عندما تحتاج إلى أداء مضمون في زمن متعدد الحدود وترغب في الاستفادة من هياكل البيانات الحديثة. بالنسبة للشبكات المتفرقة أو الأغراض التعليمية، قد تكون طرق المسار المعزز أبسط في الفهم والتنفيذ.
الحدود والاعتبارات
- أكثر تعقيدًا في الفهم والتنفيذ من طرق المسار المعزز
- تتطلب معالجة دقيقة لهياكل البيانات (قوائم التفريغ، استدلالات الفجوة) للحصول على الأداء الأمثل
- تعقيد أسوأ حالة لا يزال أعلى من بعض الخوارزميات المتخصصة لفئات الرسوم البيانية الخاصة
- فهم أقل بديهية لعملية الحل مقارنة بمسارات التعزيز
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تعقيد زمني أسوأ حالة متفوق: O(V³) أو O(V²√E) مع استدلال الفجوة (gap heuristic)
- عالية الكفاءة عمليًا، خاصة للشبكات الكبيرة والكثيفة
- محلية العمليات (الدفع/إعادة التسمية) تسمح بأداء جيد لذاكرة التخزين المؤقت (cache)
- قابلة للتوازي والتنفيذ الموزع
- متغيرات تنفيذ متعددة لهياكل المشكلات المختلفة
التطبيقات
- توجيه الشبكات: حساب أقصى إنتاجية في شبكات الاتصالات واسعة النطاق
- معالجة الصور: استخدام التدفق الأقصى لتجزئة الصور وتطبيقات التعتيم
- تحسين شركات الطيران: تحديد أقصى تدفق للركاب عبر شبكات التوجيه المعقدة
- تحليل شبكة الطاقة: حساب أقصى سعة نقل للطاقة في الشبكات الكهربائية
- إدارة سلسلة التوريد: تحسين تدفق المنتجات عبر شبكات التوزيع متعددة المستويات
- الشبكات البيولوجية: تحليل التدفق الأقصى في شبكات التمثيل الغذائي وتفاعل البروتين
كيف يعمل
كيف يعمل
عيّن ارتفاع المصدر (source) ليكون عدد الرؤوس، وجميع الارتفاعات الأخرى إلى الصفر. اشبع جميع الحواف التي تغادر المصدر، مما يؤدي إلى إنشاء تدفق أولي مبدئي (فائض عند العقد المجاورة).
اختر بشكل متكرر عقدة نشطة (بها تدفق زائد) وقم إما بدفع الفائض إلى جار ذي ارتفاع أقل أو أعد تسمية العقدة لزيادة ارتفاعها. استخدم استراتيجيات اختيار وعمليات تفريغ فعالة لتقليل التكرارات.
استمر حتى لا تبقى أي عقد نشطة، وعند هذه النقطة يكون كل التدفق الأولي قد تحول إلى تدفق أقصى من المصدر إلى المصرف.
الأخطاء الشائعة
- التنفيذ غير الصحيح لتحديثات الارتفاع أو عمليات الدفع مما يؤدي إلى تدفقات غير قصوى
- إهمال استخدام استدلالات الفجوة واختيار العقد الفعال، مما يؤدي إلى أداء عملي ضعيف
- الفشل في الحفاظ على ثابت التدفق الأولي بشكل صحيح (الفائض عند العقد وقيود السعة على الحواف)
الأسئلة الشائعة
ما الفرق بين التدفق الأولي (preflow) والتدفق (flow)؟
يسمح التدفق الأولي مؤقتًا للعقد بالاحتفاظ بالتدفق الزائد (يمكن أن يكون التدفق الداخل ناقص التدفق الخارج موجبًا)، بينما يجب الحفاظ على التدفق الحقيقي عند جميع العقد باستثناء المصدر والمصرف. تتوقف الخوارزمية عندما يصبح التدفق الأولي تدفقًا صالحًا.
ما الغرض من دالة الارتفاع (height function)؟
تنشئ الارتفاعات مقياسًا شبه مسافة: لا يمكن دفع التدفق إلا إلى الأسفل (من الارتفاعات الأعلى إلى الأقل)، مما يمنع الدورات غير الضرورية ويضمن التوقف. تزداد الارتفاعات من خلال إعادة التسمية لإنشاء مسارات جديدة عند الحاجة.
ما هو استدلال الفجوة (gap heuristic) ولماذا هو مهم؟
يكتشف استدلال الفجوة متى لا توجد عقدة ذات ارتفاع في نطاق معين، مما يشير إلى أن بعض العقد لا يمكنها الوصول إلى المصرف. يتم تحديد هذه العقد وفائضها ومعالجتها بسرعة، مما يحسن الأداء العملي بشكل كبير.
كيف تقارن خوارزمية الدفع-إعادة التسمية عمليًا بخوارزمية إدموندز-كارب؟
تتمتع خوارزمية الدفع-إعادة التسمية بتعقيد أسوأ حالة أفضل وتتفوق عادةً على خوارزمية إدموندز-كارب في الشبكات الكبيرة، ولكن بالنسبة للشبكات الصغيرة أو الرسوم البيانية المتفرقة، قد تكون خوارزمية إدموندز-كارب أبسط في التنفيذ مع أداء تنافسي.
طرق ذات صلة
المصادر
Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.
افتح مرجع DOIتم النسخ.Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
افتح مرجع المنشورتم النسخ.