الانتقال إلى المحتوى
العودة إلى نتائج البحث

خوارزمية فورد-فولكرسون

قدّمه
Lester R. Ford and Delbert R. Fulkerson
السنة
1956
النوع
algorithm
العائلة
Graph Algorithms

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

خوارزمية فورد-فولكرسون، التي طورها ليستر آر. فورد وديلبرت آر. فولكرسون في عام 1956، هي طريقة أساسية لحساب أقصى تدفق في شبكة تدفق. تجد الكمية القصوى من التدفق التي يمكن إرسالها من مصدر إلى مصرف عبر رسم بياني موجه مع قيود سعة على الحواف.

الفكرة الحدسية وراء الطريقة

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

التاريخ

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

متى تُستخدم

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

الحدود والاعتبارات

  • تعتمد التعقيد الزمني على قيم السعة (ليست متعددة الحدود بشكل عام؛ يمكن أن تكون أسية مع سعات غير عقلانية)
  • قد لا تنتهي إذا كانت السعات غير عقلانية (تتطلب تنفيذًا دقيقًا مع حسابات عقلانية)
  • أقل كفاءة من الخوارزميات المتخصصة مثل إدموندز-كارب أو دينيك على الشبكات الكبيرة
  • حساسة لترتيب اختيار المسار التعزيزي

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • نهج بسيط وبديهي يعتمد على المسارات التعزيزية
  • حل أمثل مضمون عندما تكون السعات عقلانية أو صحيحة
  • فعالة للشبكات ذات السعات الصحيحة الصغيرة
  • تشكل الأساس النظري لفهم ازدواجية الحد الأقصى للتدفق والحد الأدنى للقطع
  • تعمل مع الرسوم البيانية الموجهة وغير الموجهة

التطبيقات

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

كيف يعمل

كيف يعمل

1

تهيئة الرسم البياني المتبقي بسعات تساوي سعات الحواف الأصلية وتدفق صفري على جميع الحواف.

2

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

3

تكرار التعزيز حتى لا يوجد مسار تعزيزي في الرسم البياني المتبقي؛ إجمالي التدفق المتراكم هو أقصى تدفق.

الأخطاء الشائعة

  • اختيار مسارات تعزيزية سيئة تؤدي إلى تقارب بطيء أو نتائج غير صحيحة
  • الفشل في تحديث السعات المتبقية بشكل صحيح أو إضافة حواف عكسية لإلغاء التدفق
  • استخدام القسمة الصحيحة أو حسابات الفاصلة العائمة عندما تكون الحسابات الدقيقة مطلوبة للصحة

الأسئلة الشائعة

ما هي نظرية الحد الأقصى للتدفق والحد الأدنى للقطع؟

تنص النظرية على أن أقصى تدفق من المصدر إلى المصرف يساوي الحد الأدنى لسعة أي قطع يفصل المصدر عن المصرف. يوفر هذا رؤية نظرية وطريقة تحقق لخوارزميات التدفق.

لماذا تتقارب الخوارزمية أحيانًا ببطء؟

مع اختيارات المسار غير الموفقة، قد تقوم الخوارزمية بزيادة وحدة تدفق واحدة فقط في كل تكرار، حتى عندما تكون الزيادات الأكبر ممكنة. يضمن استخدام البحث بالعرض أولاً (إدموندز-كارب) التقارب في وقت متعدد الحدود.

كيف تتعامل الخوارزمية مع الحواف غير الموجهة؟

استبدل كل حافة غير موجهة بحافتين موجهتين في اتجاهين متعاكسين، وكلاهما بنفس السعة. ثم تجد الخوارزمية التدفق على الشبكة الموجهة.

ما الفرق بين التدفق على حافة والسعة المتبقية؟

يمثل التدفق على حافة كمية المادة المرسلة على طولها، بينما السعة المتبقية هي السعة المتاحة المتبقية. تقل السعة المتبقية مع زيادة التدفق، وتتبع الحواف العكسية القدرة على إلغاء التدفق.

طرق ذات صلة

المصادر

  1. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.

    افتح مرجع DOI
    تم النسخ.
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

    ردمك: 978-0-262-03384-8
    تم النسخ.