خوارزمية بلمان-فورد
- قدّمه
- Richard Bellman and Lester R. Ford
- السنة
- 1956
- النوع
- algorithm
- العائلة
- Graph Algorithms
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
خوارزمية بلمان-فورد، التي طورها ريتشارد بلمان وليستر آر. فورد في الخمسينيات من القرن الماضي، هي خوارزمية أساسية لحساب أقصر المسارات في الرسوم البيانية الموزونة التي قد تحتوي على أوزان حواف سالبة. على عكس خوارزمية ديكسترا، فإنها تتعامل بشكل صحيح مع الأوزان السالبة ويمكنها اكتشاف وجود دورات ذات أوزان سالبة.
الفكرة الحدسية وراء الطريقة
تعمل الخوارزمية عن طريق الاسترخاء التكراري للحواف: لكل حافة، تتحقق مما إذا كان المرور عبر تلك الحافة يوفر مسارًا أقصر إلى الوجهة من أفضل مسار معروف حاليًا. من خلال تكرار هذه العملية لجميع الحواف V-1 مرة، حيث V هو عدد الرؤوس، تضمن الخوارزمية العثور على أقصر مسار حتى مع الأوزان السالبة. الفكرة الرئيسية هي أن أي أقصر مسار في رسم بياني به V رأس يحتوي على 1-V حافة على الأكثر؛ إذا استمرت المسافات في التحسن بعد تكرارات V-1، فيجب أن توجد دورة سالبة.
التاريخ
طور ريتشارد بلمان الخوارزمية في عام 1958 باستخدام مبادئ البرمجة الديناميكية، بينما اكتشف ليستر آر. فورد بشكل مستقل نهجًا مشابهًا لتدفقات الشبكة في عام 1956. تم تطوير الخوارزمية وتحسينها بشكل أكبر في الستينيات، مع امتداد تطبيقاتها إلى توجيه الشبكات والتطبيقات الاقتصادية. تشمل المتغيرات الحديثة خوارزمية المسار الأقصر الأسرع (SPFA) وتحسينات مختلفة لهياكل الرسوم البيانية المحددة، على الرغم من أن نهج بلمان-فورد الأساسي يظل مرجعًا كلاسيكيًا في تصميم الخوارزميات.
متى تُستخدم
طبّق خوارزمية بلمان-فورد عند حساب أقصر المسارات في الرسوم البيانية ذات أوزان الحواف السالبة. إنها ضرورية للكشف عن مراجحة العملات، وبروتوكولات الشبكة حيث يمكن أن تكون الأوزان سالبة، وأي تطبيق تكون فيه التكاليف أو الأوزان السالبة ذات مغزى. استخدم خوارزمية ديكسترا إذا كانت جميع الأوزان غير سالبة، لأنها أكثر كفاءة. للكشف عن الدورات السالبة دون حساب المسارات، هذه الخوارزمية مناسبة أيضًا.
الحدود والاعتبارات
- أبطأ من ديكسترا للأوزان غير السالبة: O(VE) مقابل O((V+E)logV)
- أقل كفاءة للرسوم البيانية المتفرقة مقارنة بالخوارزميات الأخرى
- تتطلب إدراج جميع الحواف بشكل صريح، مما يجعلها أقل ملاءمة للرسوم البيانية الضمنية أو الديناميكية
- لا توجد إرشادات استدلالية متاحة لتسريع الحساب
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تتعامل مع الرسوم البيانية ذات أوزان الحواف السالبة بشكل صحيح
- تكشف عن الدورات ذات الأوزان السالبة، مما يمنع نتائج أقصر المسارات الخاطئة
- أبسط للفهم والتنفيذ من بعض خوارزميات أقصر المسارات المتقدمة
- تضمن العثور على أقصر المسارات في وقت O(VE)
- تعمل على الرسوم البيانية الموجهة وغير الموجهة (بحذر مع غير الموجهة)
التطبيقات
- الكشف عن مراجحة العملات: تحديد الدورات المربحة في رسوم أسعار الصرف
- بروتوكولات توجيه الشبكة: حساب أقصر المسارات حيث يمكن أن تختلف تكاليف الارتباط أو تكون سالبة
- نظرية الألعاب: حل مشاكل أقصر المسارات مع حواف العقوبة أو عوامل الخصم
- الروبوتات: تخطيط المسار في البيئات ذات القوى التنافرية (الأوزان السالبة)
- التفويض الاقتصادي: تحسين توليد الطاقة مع دوال التكلفة التي تشمل حدودًا سالبة
- الاتصالات: إيجاد المسارات المثلى عندما تمثل أوزان الارتباط مقاييس التأخير أو الجودة
كيف يعمل
كيف يعمل
عيّن المسافة إلى المصدر بصفر وجميع المسافات الأخرى إلى ما لا نهاية؛ اختياريًا، عيّن جميع الأسلاف إلى فارغ.
كرر V-1 مرة: لكل حافة (u, v) ذات الوزن w، إذا كانت المسافة[u] + w أقل من المسافة[v]، فحدّث المسافة[v] وسلف v.
تحقق من جميع الحواف مرة أخرى؛ إذا تحسنت أي مسافة، توجد دورة ذات وزن سالب. أرجع خطأ أو حدد الدورة حسب الاقتضاء.
الأخطاء الشائعة
- نسيان إجراء التكرار الإضافي للكشف عن الدورات السالبة
- افتراض أن الخوارزمية تعمل بشكل صحيح في الرسوم البيانية غير الموجهة ذات الحواف السالبة (يمكن أن تنشئ دورات سالبة افتراضية)
- استخدام الخوارزمية عندما تكون ديكسترا كافية، مما يؤدي إلى خسارة أداء غير ضرورية
الأسئلة الشائعة
لماذا تحتاج الخوارزمية إلى V-1 تكرار بالضبط؟
أي مسار في رسم بياني به V رأس يحتوي على 1-V حافة على الأكثر. من خلال التكرار V-1 مرة، تسمح الخوارزمية لمعلومات المسافة بالانتشار عبر الرسم البياني بأكمله. التكرار V سيحسن المسافات فقط إذا كانت هناك دورة سالبة.
كيف يمكن للخوارزمية اكتشاف الدورات السالبة؟
بعد إكمال V-1 تكرار، قم بتشغيل تمريرة استرخاء إضافية. إذا انخفضت أي مسافة، توجد دورة سالبة. يمكن تحديد العقد المشاركة في الدورة عن طريق التتبع باستخدام مؤشرات الأسلاف.
ما هي التعقيد الزمني وكيف يقارن بديكسترا؟
تعمل بلمان-فورد في وقت O(VE)، حيث V هي الرؤوس و E هي الحواف. تعمل ديكسترا في وقت O((V+E)logV) مع كومة ثنائية. بلمان-فورد أبطأ ولكنها تتعامل مع الأوزان السالبة؛ ديكسترا أسرع ولكنها تتطلب أوزانًا غير سالبة.
هل يمكن لبلمان-فورد العمل على الرسوم البيانية غير الموجهة ذات الأوزان السالبة؟
من الناحية الفنية نعم، ولكن يمكنها إنشاء دورات سالبة زائفة بسبب الطبيعة ثنائية الاتجاه للحواف. يلزم اتخاذ عناية خاصة لتفسير النتائج بشكل صحيح. بالنسبة للرسوم البيانية غير الموجهة، ضع في اعتبارك بدائل.
طرق ذات صلة
المصادر
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
افتح مرجع DOIتم النسخ.Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.
افتح مرجع المنشورتم النسخ.