مشكلة التدفق الأقصى (Maximum-Flow) في الخوارزميات: الشرح الكامل بالأمثلة
مشكلة التدفق في الشبكة (Network Flow Problem) هي سؤال بسيط في جوهره: كم أكبر كمية يمكن دفعها من نقطة بداية إلى نقطة نهاية عبر شبكة روابط لكلٍّ منها سعة قصوى؟ وعندما يكون الهدف تحديدًا هو تعظيم هذه الكمية، نسمّيها مشكلة التدفق الأقصى (Maximum-Flow Problem) — وهي الحالة الأشهر والأكثر دراسةً من عائلة مسائل التدفق. تخيّل شبكة أنابيب مياه: لكل أنبوب قطر يحدّ من تدفقه، والسؤال هو كم لترًا في الثانية يمكن أن يصل من الخزان إلى الحنفية في أقصى الأحوال. هذا بالضبط ما تحلّه هذه الخوارزميات، لكن على رسم بياني (Graph) بدل الأنابيب.
قبل الدخول في التفاصيل، ملاحظة مهمة تُربك كثيرين: «التدفق في الشبكة» في هذا السياق ليس مراقبة سرعة الإنترنت أو تحليل حركة البيانات في راوتر منزلي؛ إنه مفهوم رياضي مجرّد في علم الخوارزميات وهياكل البيانات، حتى لو كانت إحدى تطبيقاته توجيه البيانات فعلًا.
المكوّنات الأساسية للمسألة
تُبنى المسألة على رسم بياني مُوجَّه يتألف من:
- العُقد (Nodes): نقاط الالتقاء في الشبكة.
- الحواف/الروابط (Edges): المسارات بين العُقد، ولكل حافة سعة (Capacity) تمثّل الحد الأقصى للتدفق عبرها.
- المصدر (Source) والمصب (Sink): العقدة التي يبدأ منها التدفق وتلك التي ينتهي عندها، ويُرمز لهما عادةً بـ s و t.
ويجب أن يحقق أي تدفق صحيح شرطين: قيد السعة (لا يتجاوز التدفق في أي حافة سعتها)، وحفظ التدفق (ما يدخل أي عقدة وسيطة يساوي ما يخرج منها).
نظرية القطع الأدنى: المفتاح الذي يفسّر كل شيء
أجمل نتيجة في هذا الموضوع هي نظرية التدفق الأقصى/القطع الأدنى (Max-Flow Min-Cut): قيمة أكبر تدفق ممكن تساوي تمامًا سعة أصغر «قطع» يفصل المصدر عن المصب. والقطع هنا هو أي طريقة لتقسيم العقد إلى مجموعتين، إحداهما تحوي المصدر والأخرى تحوي المصب، وسعته هي مجموع سعات الحواف العابرة من جهة المصدر إلى جهة المصب. عمليًا هذا يعني أن هناك «عنق زجاجة» في الشبكة، وأن التدفق الأقصى محكوم بأضعف نقطة فيها — وهي فكرة مفيدة جدًا عند تصميم الشبكات الحقيقية.
خوارزمية Ford-Fulkerson
الفكرة المحورية هي المسار المتزايد (Augmenting Path): ما دام يوجد مسار من المصدر إلى المصب تبقى فيه سعة غير مستغلّة، ادفع عبره أكبر كمية ممكنة، ثم كرّر. تعمل الخوارزمية على ما يُسمى الرسم المتبقّي (Residual Graph) الذي يتتبّع السعة المتبقية، ويسمح كذلك بـ«التراجع» عن تدفق سابق عبر حواف عكسية — وهذه الحيلة العكسية هي ما يجعلها تصل للحل الأمثل لا مجرد حل جيد.
الطريقة الأصلية لا تحدّد كيفية إيجاد المسار، وغالبًا ما تُنفَّذ بالبحث بالعمق (DFS). نقطة يجب الانتباه لها: مع سعات صحيحة زمنها يتناسب مع قيمة التدفق نفسها O(E × max_flow)، وقد يصبح بطيئًا جدًا لو كانت السعات ضخمة، بل قد لا ينتهي نظريًا مع سعات غير نسبية (كسور غير منتهية).
خوارزمية Edmonds-Karp
هي ببساطة تطبيق منضبط لـ Ford-Fulkerson يختار دائمًا أقصر مسار متزايد باستخدام البحث بالعرض (BFS). هذا التقييد الصغير يغيّر كل شيء: يصبح الزمن O(V × E²)، أي مستقلًّا عن قيمة السعات — ميزة حاسمة عندما تكون الأرقام كبيرة. لهذا يُنصح بها كنقطة بداية عملية موثوقة.
Ford-Fulkerson أم Edmonds-Karp؟
| المعيار | Ford-Fulkerson (بـ DFS) | Edmonds-Karp (بـ BFS) |
|---|---|---|
| اختيار المسار | أي مسار متزايد | أقصر مسار متزايد |
| التعقيد الزمني | O(E × القيمة القصوى للتدفق) | O(V × E²) |
| تأثّره بحجم السعات | يتأثر بشدة | لا يتأثر |
| سعات غير صحيحة | قد لا ينتهي | آمن ومضمون الانتهاء |
| متى تختاره | شرح تعليمي، سعات صغيرة | خيار عملي افتراضي |
للشبكات الكبيرة جدًا تُستخدم خوارزميات أحدث وأسرع مثل Dinic بزمن O(V² × E)، وهي المعيار الفعلي في المسابقات البرمجية والتطبيقات الجادة.
مثال بسيط لتثبيت الفكرة
لنفترض أربع عقد: المصدر s، وعقدتين a و b، والمصب t. السعات: s→a = 10، s→b = 10، a→t = 10، b→t = 10، مع حافة داخلية a→b = 1. سيدفع أي حل جيد 10 عبر s→a→t و10 عبر s→b→t، فيصير التدفق الأقصى 20، بينما الحافة a→b الصغيرة لا تُحدث فرقًا لأن كل عقدة لها بالفعل مخرج كافٍ. لاحظ أن أصغر قطع هنا (سعته 20) يطابق التدفق الأقصى تمامًا — تجسيدٌ حيّ لنظرية القطع الأدنى.
تطبيقات واقعية
- مطابقة ثنائية (Bipartite Matching): توزيع موظفين على مهام أو طلاب على مشاريع بأقصى عدد إسنادات ممكن.
- توجيه البيانات والشبكات: حساب أقصى سعة نقل بين خادمين.
- الجدولة وتوزيع الموارد: المياه، الكهرباء، وسلاسل الإمداد.
- معالجة الصور: فصل الخلفية عن الكائن (Image Segmentation) يُصاغ كمسألة قطع أدنى.
نصيحة عملية وخطأ شائع
الخطأ الأكثر تكرارًا عند التنفيذ هو نسيان الحواف العكسية في الرسم المتبقّي. من دونها لن تتمكن الخوارزمية من تصحيح قرار سابق، فتتوقف عند حل شبه أمثل وتظنّه نهائيًا. القاعدة: لكل حافة تدفع عبرها كمية f، أنقِص f من سعتها المتبقية وأضِف f إلى سعة الحافة المعاكسة. نصيحة إضافية: ابدأ دائمًا بـ Edmonds-Karp لوضوحه وأمانه، ولا تنتقل إلى Dinic إلا عندما تفرض عليك أحجام البيانات ذلك فعلًا.
الأسئلة الشائعة
ما الفرق بين «التدفق في الشبكة» و«التدفق الأقصى»؟ مسائل التدفق عائلة واسعة (منها التدفق بأقل تكلفة مثلًا)، أما التدفق الأقصى فهو الحالة الخاصة التي هدفها الوحيد تعظيم الكمية المنقولة من المصدر إلى المصب.
هل Edmonds-Karp دائمًا أسرع من Ford-Fulkerson؟ ليس دائمًا، لكنها أكثر ضمانًا: زمنها لا يعتمد على حجم السعات، بينما قد ينفجر زمن Ford-Fulkerson مع سعات كبيرة أو غير صحيحة.
هل يمكن أن يوجد أكثر من حل للتدفق الأقصى؟ نعم؛ قد توجد توزيعات مختلفة للتدفق على الحواف، لكن القيمة القصوى للتدفق واحدة دائمًا لأي شبكة.
أين أستخدم هذه المفاهيم عمليًا كمبرمج؟ في مسائل المطابقة والجدولة والتوجيه، وهي شائعة جدًا في المقابلات التقنية والمسابقات البرمجية، وتُبنى فوقها حلول لمشاكل تبدو غير متعلقة بالتدفق للوهلة الأولى.