مشكلة تدفق الشبكة

في مجال التحسين التوافقي ، تُعدّ مسائل تدفق الشبكة فئة من المسائل الحسابية التي يكون فيها المدخل عبارة عن شبكة تدفق (رسم بياني ذو سعات عددية على حوافه)، والهدف هو إنشاء تدفق ، وقيم عددية على كل حافة تحترم قيود السعة ويكون التدفق الوارد مساوياً للتدفق الصادر عند جميع الرؤوس باستثناء بعض المحطات الطرفية المحددة. ^{[ 1 ]}

تشمل أنواع محددة من مشاكل تدفق الشبكة ما يلي:

مشكلة التدفق الأقصى ، والتي يتمثل الهدف فيها في زيادة إجمالي كمية التدفق الخارج من محطات المصدر والداخل إلى محطات المصب ^{[ 1 ]}^{: 166-206}
مشكلة التدفق بأقل تكلفة ، حيث تكون للحواف تكاليف بالإضافة إلى قدرات، والهدف هو تحقيق كمية معينة من التدفق (أو أقصى تدفق) بأقل تكلفة ممكنة ^{[ 1 ]}^{: 294-356}
مشكلة تدفق السلع المتعددة ، والتي يجب فيها إنشاء تدفقات متعددة لسلع مختلفة بحيث تحترم كميات التدفق الإجمالية معًا القدرات ^{[ 1 ]}^{: 649-694}
التدفق غير الصفري ، وهو نوع من التدفقات التي تُدرس في علم التوافق حيث تقتصر كميات التدفق على مجموعة محدودة من القيم غير الصفرية

تُساوي نظرية التدفق الأقصى والقطع الأدنى قيمة التدفق الأقصى بقيمة القطع الأدنى ، وهو تقسيم لرؤوس شبكة التدفق يُقلل من إجمالي سعة الحواف المارة من جانب إلى آخر من هذا التقسيم. وتُقدم نظريات تقريبية للتدفق الأقصى والقطع الأدنى امتدادًا لهذه النتيجة ليشمل مسائل تدفق السلع المتعددة. وتُوفر شجرة جوموري-هو لشبكة تدفق غير موجهة تمثيلًا موجزًا لجميع القطوع الدنيا بين أزواج مختلفة من الرؤوس الطرفية.

تتضمن خوارزميات بناء التدفقات ما يلي:

خوارزمية دينيك ، وهي خوارزمية متعددة الحدود قوية للتدفق الأقصى ^{[ 1 ]}^{: 221-223}
خوارزمية إدموندز -كارب ، وهي خوارزمية متعددة الحدود قوية وأسرع لتحقيق أقصى تدفق
خوارزمية فورد -فولكرسون ، وهي خوارزمية جشعة لتحقيق أقصى تدفق، وهي ليست متعددة الحدود بشكل عام.
خوارزمية الشبكة البسيطة ، وهي طريقة تعتمد على البرمجة الخطية ولكنها متخصصة في تدفق الشبكة ^{[ 1 ]}^{: 402-460}
خوارزمية عدم التوازن لتدفق التكلفة الأدنى ^{[ 1 ]}^{: 326-331}
خوارزمية التدفق الأقصى للدفع وإعادة التسمية ، هي إحدى أكثر التقنيات المعروفة كفاءة لتحقيق التدفق الأقصى

وإلا يمكن صياغة المشكلة كبرنامج خطي أكثر تقليدية أو ما شابه ذلك وحلها باستخدام برنامج حل التحسين للأغراض العامة.

مراجع

1 2 3 4 5 6 7 أهوجا، رافيندرا ك.؛ ماجنانتي، توماس ل.؛ أورلين، جيمس ب. (1993). تدفقات الشبكة: النظرية والخوارزميات والتطبيقات . برنتيس هول.

[FNbook-1] 1 2 3 4 5 6 7 أهوجا، رافيندرا ك.؛ ماجنانتي، توماس ل.؛ أورلين، جيمس ب. (1993). تدفقات الشبكة: النظرية والخوارزميات والتطبيقات . برنتيس هول.

[ 1 ]

اللغة	العربية (RTL)
روابط موسوعية	20 رابطاً
المصدر الأصلي	ويكيبيديا ↗