The Edmonds-Karp Algorithm: A Detailed Efficiency Analysis

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

الوصف الافتراضي والامتيازات الرئيسية

Given a directed graph G = (V, E)] with a source ]s, sink t, and capacity function c: E ⁇ R+[FKLT follows:7]

  1. Initialize flow f(e) = 0] for all edges.
  2. Construct the residual graph Gf] (including backward edges with capacity equal to current flow).
  3. Run BFS on Gf] from s] to find the shortest directed path to t] [measured in number of edges.]
  4. وإذا لم يكن هناك طريق، يُنهي؛ فالتدفق الحالي هو أقصى ما يمكن.
  5. وإلا، حدد القدرة على الاختناقات على طول الطريق (القدرة المتبقية الدنيا).
  6. تدفق المبلغ إلى الوراء على طول الطريق واستكمال القدرات المتبقية.
  7. أكرر من الخطوة الثانية

The use of BFS ensures that each augmenting path found is a shortest path in the residual graph. A critical property emerges: the distance (in edges) from s to ]t in the residual graph never decreases and strictly increases every O(

تحليل التعقيد

[FLT:]O(V+)[FLT:]

More precise, the standard analysis shows that the number of increaseations is at most O(VE), so the overall time is ]O(V E2) (or O(V E))[FLness:5] for complete.

مقارنة مع المعلمات الأخرى

Dinic’s Algorithm

وتستخدم خوارزمية دينيك أيضاً نظاماً بيانياً من المستوى BFS لتشييد رسم بياني، ولكنها تسمح بعد ذلك بتعدد مسارات الازدياد في مرحلة واحدة عن طريق إدارة الدعم الميداني على مستوى الرسم البياني، مما يقلل من عدد شبكات BFS التي تتجه إلى معظم [(FLT:0] V] [بما أن مستوى الغسل يزيد كل مرحلة]

Push-Relabel Algorithms

(أ) أساليب القذف والوسم، مثل الخوارزمية العامة أو المتغير الأعلى درجة، تحقق O(V2 √E) أو )O(V3)]، وهي تعمل بالدفع بالتدفق المحلي على الحواف المؤهلة، والبرمجة الفوقية المثبتة على نطاق واسع للحفاظ على المذيبات التنافسية.

Another important variant is the capacity scaling algorithm, which adds a scaling parameter to the Ford-Fulkerson method, yielding O(E2 log U) whereU is maximum.

لماذا إدموندز كارب لا يزال الأمر

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

الآثار العملية وحالات الاستخدام

وفي تطبيقات العالم الحقيقي، يعتمد اختيار الخوارزميات اعتمادا كبيرا على القيود التي تواجه المشاكل، على سبيل المثال:

  • Bipartite matching: Edmonds-Karp reduces to the Hopcroft-Karp algorithm when capacities are unit and the network is bipartite? in no - Hopcroft-Karp is dedicated algorithm with O(E √5)
  • Traffic engineering]: في شبكات الاتصالات والطرق، كثيرا ما تكون التدفقات كبيرة وتتفاوت الرسوم البيانية.() ويفضل الدين أو الرافعة بسبب تحسين التوسع.
  • Image segmentation]: غلاف خمري من أجل رؤية حاسوبية يعتمد غالباً على التدفق الأقصى/الحسابات الدقيقة، ويعتمد خوارزمية بوكوف - كولموغوروف، وهي طريقة متخصصة للزيادة في التعاطف، وغالباً ما تفوق الخوارزميات العامة لهذه الرسومات الشبيهة بالشبكة، ولكن يمكن أن تستخدمها إدموند.
  • Education and prototyping ]: When simplicity and correctness are preval over raw speed, Edmonds-Karp is a safe choice, Its behavior is predictable, and debugging is straightforward because BFS is easy to implement.

الأداء التجريبي

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

اعتبارات التنفيذ

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

وتشمل أوجه الاستخدام الأمثل ما يلي:

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

وبالنسبة للشبكات الكبيرة جدا، النظر في استخدام نظام بيانات موحّد دينامي يستكمل المسافات تدريجيا، ولكن هذا يضيف في كثير من الأحيان تعقيدا دون تحقيق مكاسب كبيرة بالنسبة لمؤسسة إدموندز - كارب تحديدا.

العلاقة بمنهج فورد - فولكرسون الأصلي

(أ) أن استخدام نظام إدارة الأعمال التجارية (BFS) يُنتج نظاماً قياسياً أقصى لتدفقات التدفق، قبل ذلك، لم تحدد طريقة فورد - فولكرسون (1956) قاعدة اختيار المسار، وكان من المعروف أن الخيارات السيئة يمكن أن تؤدي إلى وقت طويل.

التمديدات والتعديلات

وتشمل متغيرات إدموندز - كارب ما يلي:

  • Capacity scaling version]: بدلاً من أن يُزايد دائماً على طول أقصر مسار، يعمل الخوارزمي بمسع ] وينظر فقط في الحواف ذات القدرة المتبقية على سد الثغرات، مما يؤدي إلى (الأول/الأول]
  • Unit capacity optimization]: When all capacities are 1, the BFS-based plusing path algorithm specializes to the Hopcroft-Karp algorithm, though the latter uses careful alternating BFS/DFS to achieve ]O(E √V)[FLT:
  • Integrality]: The algorithm naturally maintains integral flows when capacities are integral, making it suitable for combinatorial problems.

خاتمة

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

ويمكن الاطلاع على مزيد من القراءة عن خوارزميات التدفق المتقدمة في مقال ويكبيديا ] وفي الكتاب المدرسي الكلاسيكي [العرض على الخوارزميات (CLRS) للاطلاع على تحليل أعمق لأداء الأشعة، انظر