الگوریتم بلمن-فورد
- معرفیشده توسط
- Richard Bellman and Lester R. Ford
- سال
- 1956
- نوع
- algorithm
- خانواده
- Graph Algorithms
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
الگوریتم بلمن-فورد که توسط ریچارد بلمن و لستر آر. فورد در دهه ۱۹۵۰ توسعه یافت، یک الگوریتم بنیادی برای محاسبه کوتاهترین مسیرها در گرافهای وزندار است که ممکن است شامل وزنهای یال منفی باشد. برخلاف الگوریتم دایکسترا، این الگوریتم وزنهای منفی را به درستی مدیریت میکند و میتواند وجود دورهای با وزن منفی را تشخیص دهد.
شهود پشت روش
این الگوریتم با تکرار فرایند شل کردن یالها کار میکند: برای هر یال، بررسی میکند که آیا عبور از آن یال مسیر کوتاهتری به مقصد نسبت به بهترین مسیر شناخته شده فعلی ارائه میدهد یا خیر. با تکرار این فرآیند برای تمام یالها V-1 بار، که V تعداد رأسها است، الگوریتم تضمین میکند که کوتاهترین مسیر را حتی با وجود وزنهای منفی پیدا کند. نکته کلیدی این است که هر مسیر کوتاهتری در گرافی با V رأس، حداکثر شامل V-1 یال است؛ اگر فاصلهها پس از V-1 تکرار همچنان بهبود یابند، باید یک دور منفی وجود داشته باشد.
تاریخ
ریچارد بلمن الگوریتم را در سال ۱۹۵۸ با استفاده از اصول برنامهریزی پویا توسعه داد، در حالی که لستر آر. فورد به طور مستقل رویکرد مشابهی را برای جریانهای شبکه در سال ۱۹۵۶ کشف کرد. این الگوریتم در دهه ۱۹۶۰ بیشتر توسعه یافت و بهبود یافت و کاربردهای آن به مسیریابی شبکه و کاربردهای اقتصادی گسترش یافت. انواع مدرن شامل الگوریتم کوتاهترین مسیر سریعتر (SPFA) و بهینهسازیهای مختلف برای ساختارهای گراف خاص است، اگرچه رویکرد اساسی بلمن-فورد به عنوان یک مرجع کلاسیک در طراحی الگوریتم باقی مانده است.
چه زمانی استفاده شود
الگوریتم بلمن-فورد را هنگام محاسبه کوتاهترین مسیرها در گرافهای با وزن یال منفی اعمال کنید. این الگوریتم برای تشخیص آربیتراژ ارز، پروتکلهای شبکه که در آنها وزنها میتوانند منفی باشند، و هر کاربردی که در آن هزینهها یا وزنهای منفی معنیدار هستند، ضروری است. اگر تمام وزنها نامنفی هستند، از الگوریتم دایکسترا استفاده کنید، زیرا کارآمدتر است. این الگوریتم همچنین برای تشخیص دورهای منفی بدون محاسبه مسیرها مناسب است.
محدودیتها و ملاحظات
- کندتر از دایکسترا برای وزنهای نامنفی: O(VE) در مقابل O((V+E)logV)
- برای گرافهای پراکنده نسبت به الگوریتمهای دیگر کارایی کمتری دارد
- نیاز به لیست شدن صریح تمام یالها دارد، که آن را برای گرافهای ضمنی یا پویا نامناسبتر میکند
- راهنمایی ابتکاری برای سرعت بخشیدن به محاسبات در دسترس نیست
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- گرافهای با وزن یال منفی را به درستی مدیریت میکند
- دورهای با وزن منفی را تشخیص میدهد و از نتایج نادرست کوتاهترین مسیر جلوگیری میکند
- درک و پیادهسازی آن نسبت به برخی الگوریتمهای پیشرفته کوتاهترین مسیر سادهتر است
- تضمین شده است که کوتاهترین مسیرها را در زمان O(VE) پیدا کند
- روی گرافهای جهتدار و بدون جهت کار میکند (با احتیاط در گرافهای بدون جهت)
کاربردها
- تشخیص آربیتراژ ارز: شناسایی دورهای سودآور در گرافهای نرخ ارز
- پروتکلهای مسیریابی شبکه: محاسبه کوتاهترین مسیرها در جایی که هزینههای پیوند میتواند متغیر یا منفی باشد
- نظریه بازی: حل مسائل کوتاهترین مسیر با یالهای جریمه یا ضرایب تخفیف
- رباتیک: برنامهریزی مسیر در محیطهایی با نیروهای دافعه (وزنهای منفی)
- تخصیص اقتصادی: بهینهسازی تولید برق با توابع هزینه شامل عبارات منفی
- مخابرات: یافتن مسیرهای بهینه زمانی که وزنهای پیوند نشاندهنده معیارهای تأخیر یا کیفیت هستند
چگونه کار میکند
چگونه کار میکند
فاصله مبدأ را صفر و تمام فواصل دیگر را بینهایت تنظیم کنید؛ به صورت اختیاری، تمام پیشینیان را null تنظیم کنید.
تکرار V-1 بار: برای هر یال (u, v) با وزن w، اگر distance[u] + w کمتر از distance[v] باشد، distance[v] و پیشین v را بهروزرسانی کنید.
یک بار دیگر تمام یالها را بررسی کنید؛ اگر هر فاصلهای بهبود یافت، یک دور با وزن منفی وجود دارد. در صورت لزوم خطا را برگردانید یا دور را شناسایی کنید.
دامهای رایج
- فراموش کردن انجام تکرار اضافی برای تشخیص دورهای منفی
- فرض اینکه الگوریتم در گرافهای بدون جهت با یالهای منفی به درستی کار میکند (میتواند دورهای منفی مجازی ایجاد کند)
- استفاده از الگوریتم زمانی که دایکسترا کافی است، منجر به از دست دادن عملکرد غیرضروری میشود
پرسشهای متداول
چرا الگوریتم دقیقاً به V-1 تکرار نیاز دارد؟
هر مسیری در گرافی با V رأس حداکثر شامل V-1 یال است. با تکرار 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.
باز کردن مرجع انتشارکپی شد.