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

طريقة فورد-فولكرسون أو خوارزمية فورد-فولكرسون ( FFA ) هي خوارزمية جشعة تحسب التدفق الأقصى في شبكة التدفق . يُطلق عليها أحيانًا اسم "طريقة" بدلاً من "خوارزمية" لأن النهج المتبع في إيجاد مسارات متزايدة في الرسم البياني المتبقي غير محدد بالكامل ^[1] أو يتم تحديده في العديد من التنفيذات بأوقات تشغيل مختلفة. ^[2] تم نشرها في عام 1956 بواسطة LR Ford Jr. و DR Fulkerson . ^[3] غالبًا ما يُستخدم اسم "Ford-Fulkerson" أيضًا لخوارزمية Edmonds-Karp ، وهي تنفيذ محدد بالكامل لطريقة Ford-Fulkerson.

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

ليكن رسمًا بيانيًا، ولكل حافة من u إلى v ، ليكن السعة ويكون التدفق. نريد إيجاد أقصى تدفق من المصدر s إلى المصرف t . بعد كل خطوة في الخوارزمية، يتم الحفاظ على ما يلي: ${\displaystyle G(V,E)}$${\displaystyle c(u,v)}$${\displaystyle f(u,v)}$

قيود القدرة	${\displaystyle \forall (u,v)\in E:\f(u,v)\leq c(u,v)}$	لا يمكن للتدفق على طول الحافة أن يتجاوز سعته.
تماثل الانحراف	${\displaystyle \forall (u,v)\in E:\f(u,v)=-f(v,u)}$	يجب أن يكون التدفق الصافي من u إلى v معاكسًا للتدفق الصافي من v إلى u (انظر المثال).
الحفاظ على التدفق	${\displaystyle \forall u\in V:u\neq s{\text{ و }}u\neq t\Rightarrow \sum _{w\in V}f(u,w)=0}$	إن التدفق الصافي إلى العقدة يساوي صفرًا، باستثناء المصدر الذي "يُنتج" التدفق، والمصرف الذي "يستهلك" التدفق.
القيمة(ف)	${\displaystyle \sum _{(s,u)\in E}f(s,u)=\sum _{(v,t)\in E}f(v,t)}$	يجب أن يكون التدفق الخارج من s مساويًا للتدفق القادم إلى t .

هذا يعني أن التدفق عبر الشبكة هو تدفق قانوني بعد كل جولة في الخوارزمية. نُعرّف الشبكة المتبقية على أنها الشبكة ذات السعة ولا يوجد بها تدفق. لاحظ أنه من الممكن أن يُسمح بالتدفق من v إلى u في الشبكة المتبقية، على الرغم من عدم السماح به في الشبكة الأصلية: إذا و ثم . ${\displaystyle G_{f}(V,E_{f})}$${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$${\displaystyle f(u,v)>0}$${\displaystyle c(v,u)=0}$${\displaystyle c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0}$

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

يمكن العثور على المسار في الخطوة 2، على سبيل المثال، باستخدام البحث أولاً بالعرض (BFS) أو البحث أولاً بالعمق في . يُعرف الأول باسم خوارزمية إدموندز-كارب . ${\displaystyle G_{f}(V,E_{f})}$

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

إذا كان الرسم البياني يحتوي على مصادر ومصارف متعددة، فسنتصرف على النحو التالي: افترض أن و . أضف مصدرًا جديدًا بحافة من إلى كل عقدة ، بسعة . وأضف مصرفًا جديدًا بحافة من كل عقدة إلى ، بسعة . ثم طبق خوارزمية فورد-فولكرسون. ${\displaystyle G(V,E)}$${\displaystyle T=\{t\mid t{\text{ is a sink}}\}}$${\displaystyle S=\{s\mid s{\text{ is a source}}\}}$${\displaystyle s^{*}}$${\displaystyle (s^{*},s)}$${\displaystyle s^{*}}$${\displaystyle s\in S}$${\displaystyle c(s^{*},s)=d_{s}=\sum _{(s,u)\in E}c(s,u)}$${\displaystyle t^{*}}$${\displaystyle (t,t^{*})}$${\displaystyle t\in T}$${\displaystyle t^{*}}$${\displaystyle c(t,t^{*})=d_{t}=\sum _{(v,t)\in E}c(v,t)}$

أيضًا، إذا كانت العقدة u لها قيد سعة ، فإننا نستبدل هذه العقدة بعقدتين ، وحافة ، بسعة . ثم نطبق خوارزمية فورد-فولكرسون. ${\displaystyle d_{u}}$${\displaystyle u_{\mathrm {in} },u_{\mathrm {out} }}$${\displaystyle (u_{\mathrm {in} },u_{\mathrm {out} })}$${\displaystyle c(u_{\mathrm {in} },u_{\mathrm {out} })=d_{u}}$

من خلال إضافة مسار زيادة التدفق إلى التدفق المحدد بالفعل في الرسم البياني، سيتم الوصول إلى الحد الأقصى للتدفق عندما لا يمكن العثور على المزيد من مسارات زيادة التدفق في الرسم البياني. ومع ذلك، لا يوجد يقين من أن هذا الموقف سيتم الوصول إليه على الإطلاق، لذا فإن أفضل ما يمكن ضمانه هو أن الإجابة ستكون صحيحة إذا انتهت الخوارزمية. في حالة تشغيل الخوارزمية إلى الأبد، فقد لا يتقارب التدفق حتى نحو الحد الأقصى للتدفق. ومع ذلك، يحدث هذا الموقف فقط مع قيم التدفق غير المنطقية. ^[4] عندما تكون السعات أعدادًا صحيحة، يكون وقت تشغيل فورد فولكرسون محدودًا بـ (انظر تدوين O الكبير )، حيث هو عدد الحواف في الرسم البياني و هو الحد الأقصى للتدفق في الرسم البياني. وذلك لأن كل مسار زيادة يمكن العثور عليه في الوقت ويزيد التدفق بمقدار صحيح لا يقل عن ، مع الحد الأعلى . ${\displaystyle O(Ef)}$${\displaystyle E}$${\displaystyle f}$${\displaystyle O(E)}$${\displaystyle 1}$${\displaystyle f}$

أحد أشكال خوارزمية فورد-فولكرسون ذات الإنهاء المضمون ووقت التشغيل المستقل عن قيمة التدفق الأقصى هي خوارزمية إدموندز-كارب ، والتي تعمل في الوقت المناسب. ${\displaystyle O(VE^{2})}$

يوضح المثال التالي الخطوات الأولى لخوارزمية فورد-فولكرسون في شبكة تدفق بها 4 عقد، مصدر ومصرف . يوضح هذا المثال أسوأ سلوك للخوارزمية. في كل خطوة، يتم إرسال تدفق واحد فقط عبر الشبكة. إذا تم استخدام البحث أولاً بالعرض بدلاً من ذلك، فلن تكون هناك حاجة إلا إلى خطوتين. ${\displaystyle A}$${\displaystyle D}$${\displaystyle 1}$

خطوة	شبكة التدفق
شبكة التدفق الأولية.
يتم إرسال التدفق على طول مسار الزيادة . هنا، يكون عنق الزجاجة هو الحافة - ، وبالتالي فإن وحدة واحدة فقط من التدفق ممكنة. ${\displaystyle A,B,C,D}$${\displaystyle B}$${\displaystyle C}$
هنا، يتم إرسال وحدة تدفق واحدة على طول مسار الزيادة . في هذه الحالة، يتم "دفع" التدفق للخلف من إلى . يأتي التدفق إلى الذي جاء في الأصل من الآن من ، وهو الآن حر في إرسال التدفق إلى مباشرة. ونتيجة لذلك، تُترك الحافة - مع تدفق صفري، لكن التدفق الإجمالي يزداد بمقدار واحد. ${\displaystyle A,C,B,D}$${\displaystyle C}$${\displaystyle B}$${\displaystyle C}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle D}$${\displaystyle B}$${\displaystyle C}$
تم حذف الخطوات الوسيطة لعام 1998 هنا.
شبكة التدفق النهائية بإجمالي تدفق 2000 وحدة.

لننظر إلى شبكة التدفق الموضحة على اليمين، مع المصدر والمصرف وسعات الحواف و على التوالي و و وسعة جميع الحواف الأخرى بعض الأعداد الصحيحة . تم اختيار الثابت بحيث . نستخدم مسارات الزيادة وفقًا للجدول التالي، حيث و و . ${\displaystyle s}$${\displaystyle t}$${\displaystyle e_{1}}$${\displaystyle e_{2}}$${\displaystyle e_{3}}$${\displaystyle 1}$${\displaystyle r=({\sqrt {5}}-1)/2}$${\displaystyle 1}$${\displaystyle M\geq 2}$${\displaystyle r}$${\displaystyle r^{2}=1-r}$${\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}}$${\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\}}$${\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\}}$

خطوة	مسار التعزيز	تم إرسال التدفق	القدرات المتبقية
			${\displaystyle e_{1}}$	${\displaystyle e_{2}}$	${\displaystyle e_{3}}$
0			${\displaystyle r^{0}=1}$	${\displaystyle r}$	${\displaystyle 1}$
1	${\displaystyle \{s,v_{2},v_{3},t\}}$	${\displaystyle 1}$	${\displaystyle r^{0}}$	${\displaystyle r^{1}}$	${\displaystyle 0}$
2	${\displaystyle p_{1}}$	${\displaystyle r^{1}}$	${\displaystyle r^{0}-r^{1}=r^{2}}$	${\displaystyle 0}$	${\displaystyle r^{1}}$
3	${\displaystyle p_{2}}$	${\displaystyle r^{1}}$	${\displaystyle r^{2}}$	${\displaystyle r^{1}}$	${\displaystyle 0}$
4	${\displaystyle p_{1}}$	${\displaystyle r^{2}}$	${\displaystyle 0}$	${\displaystyle r^{1}-r^{2}=r^{3}}$	${\displaystyle r^{2}}$
5	${\displaystyle p_{3}}$	${\displaystyle r^{2}}$	${\displaystyle r^{2}}$	${\displaystyle r^{3}}$	${\displaystyle 0}$

لاحظ أنه بعد الخطوة 1 وكذلك بعد الخطوة 5، تكون السعات المتبقية للحواف ، و في النموذج ، و ، على التوالي، لبعض . وهذا يعني أنه يمكننا استخدام مسارات الزيادة ، و، و مرات لا نهائية وستكون السعات المتبقية لهذه الحواف دائمًا في نفس الشكل. التدفق الكلي في الشبكة بعد الخطوة 5 هو . إذا استمرينا في استخدام مسارات الزيادة كما هو مذكور أعلاه، فإن التدفق الكلي يتقارب إلى . ومع ذلك، لاحظ أن هناك تدفقًا بقيمة ، عن طريق إرسال وحدات التدفق على طول ، وحدة تدفق واحدة على طول ، ووحدات تدفق على طول . لذلك، لا تنتهي الخوارزمية أبدًا ولا يتقارب التدفق حتى إلى الحد الأقصى للتدفق. ^[5]${\displaystyle e_{1}}$${\displaystyle e_{2}}$${\displaystyle e_{3}}$${\displaystyle r^{n}}$${\displaystyle r^{n+1}}$${\displaystyle 0}$${\displaystyle n\in \mathbb {N} }$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{3}}$${\displaystyle 1+2(r^{1}+r^{2})}$${\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}$${\displaystyle 2M+1}$${\displaystyle M}$${\displaystyle sv_{1}t}$${\displaystyle sv_{2}v_{3}t}$${\displaystyle M}$${\displaystyle sv_{4}t}$

يقدم باكمان وهوينه (2018) مثالًا آخر غير منتهٍ يعتمد على الخوارزمية الإقليدية ، حيث يظهران أيضًا أن أسوأ وقت تشغيل لخوارزمية فورد-فولكرسون على شبكة بأعداد ترتيبية هو . ${\displaystyle G(V,E)}$${\displaystyle \omega ^{\Theta (|E|)}}$

استيراد  المجموعات


 الرسم البياني للصف :
    """
    تمثل هذه الفئة رسمًا بيانيًا موجهًا باستخدام
    تمثيل مصفوفة المجاورة.
    """

    def  __init__ ( self ،  الرسم البياني ):
        الرسم البياني الذاتي = الرسم البياني # الرسم البياني المتبقي    
        ذاتي . الصف  =  طول ( رسم بياني )

    تعريف  bfs ( الذات ،  s ،  t ،  الأصل ):
        """
        يعود صحيحًا إذا كان هناك مسار من
        المصدر 's' لإغراق 't' في الرسم البياني المتبقي.
        يملأ أيضًا parent[] لتخزين المسار.
        """

        # قم بوضع علامة على جميع القمم على أنها غير مزار
         تمت الزيارة =  [ خطأ ]  *  صف ذاتي

        # إنشاء قائمة انتظار لـ BFS
        قائمة الانتظار  =  المجموعات . ديكي ()

        # قم بتمييز العقدة المصدر على أنها تمت زيارتها ووضعها في قائمة الانتظار
        قائمة الانتظار . إضافة ( إضافات )
        تمت الزيارة [ s ]  =  صحيح

        # حلقة BFS القياسية
        أثناء  قائمة الانتظار :
            u  =  queue . popleft ()

            # احصل على جميع الرؤوس المجاورة للرأس الذي تم إخراجه من قائمة الانتظار
            # إذا لم تتم زيارة مكان مجاور، فقم بوضع علامة عليه
            # تمت زيارتها ووضعها في قائمة الانتظار
            بالنسبة إلى  ind ،  val  في  enumerate ( self.graph [ u ] ) :
                إذا  ( تمت الزيارة [ ind ]  ==  False )  و  ( val  >  0 ):
                    قائمة الانتظار . إضافة ( ind )
                    تمت الزيارة [ ind ]  =  صحيح
                    الوالد [ ind ]  =  u

        # إذا وصلنا إلى الحوض في BFS بدءًا من المصدر، ثم العودة
        # صحيح، وإلا خطأ
        العودة  تمت الزيارة [ ت ]

    # إرجاع الحد الأقصى للتدفق من s إلى t في الرسم البياني المعطى
    def  edmonds_karp ( self ،  المصدر ،  المصب ):
        # يتم ملء هذه المجموعة بواسطة BFS لتخزين المسار
        الأصل  =  [ - 1 ]  *  صف ذاتي​

        max_flow  =  0   # لا يوجد تدفق في البداية

        # قم بزيادة التدفق أثناء وجود مسار من المصدر إلى المصرف
        بينما  self.bfs ( المصدر ، المصرف ، الأصل ) :​  
            # إيجاد الحد الأدنى من السعة المتبقية للحواف على طول
            # المسار ممتلئ بـ BFS. أو يمكننا القول العثور على الحد الأقصى للتدفق
            # من خلال المسار الذي تم العثور عليه.
            path_flow  =  float ( "Inf" )
            س  =  بالوعة
            بينما  s  !=  المصدر :
                path_flow  =  min ( path_flow ,  self . graph [ parent [ s ]][ s ])
                س  =  الوالد [ س ]

            # إضافة تدفق المسار إلى التدفق الإجمالي
            الحد الأقصى للتدفق  +=  مسار التدفق

            # تحديث السعات المتبقية للحواف والحواف العكسية
            # على طول الطريق
            v  =  بالوعة
            بينما  v  !=  المصدر :
                u  =  الأصل [ v ]
                رسم بياني ذاتي [ u ] [ v ] -= مسار التدفق  
                رسم بياني ذاتي [ v ][ u ] += مسار التدفق  
                v  =  الأصل [ v ]

        العودة  إلى الحد الأقصى للتدفق

• نظرية بيرج
• نظرية الحد الأقصى للتدفق والحد الأدنى للقطع التقريبي
• توجيه تقييد الدوران
• خوارزمية دينيك

• كورمن، توماس إتش .؛ ليسيرسون، تشارلز إي .؛ ريفست، رونالد إل .؛ شتاين، كليفورد (2001). "القسم 26.2: طريقة فورد-فولكرسون". مقدمة إلى الخوارزميات (الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ص 651-664. رقم ISBN 0-262-03293-7.
• جورج ت. هاينمان؛ جاري بوليس؛ ستانلي سيلكو (2008). "الفصل الثامن: خوارزميات تدفق الشبكة". الخوارزميات في لمحة . أوريلي ميديا . ص 226-250. رقم ISBN 978-0-596-51624-6.
• جون كلاينبيرج ؛ إيفا تاردوس (2006). "الفصل 7: التوسعات لمشكلة التدفق الأقصى". تصميم الخوارزمية . بيرسون للتعليم. ص 378-384. رقم ISBN 0-321-29535-8.
• صمويل جوتيكونست (2019). ENGRI 1101. جامعة كورنيل.
• باكمان، سبنسر؛ هوينه، توني (2018). "Transfinite Ford–Fulkerson on a finite network". Computability . 7 (4): 341–347. arXiv : 1504.04363 . doi :10.3233/COM-180082. S2CID  15497138.

• برنامج تعليمي يشرح طريقة فورد-فولكرسون لحل مشكلة التدفق الأقصى
• رسوم متحركة أخرى بلغة جافا
• تطبيق Java Web Start

الوسائط المتعلقة بخوارزمية فورد-فولكرسون على ويكيميديا ​​كومنز

Original text

Rate this translation

Your feedback will be used to help improve Google Translate