الگوریتم فورد-فالکرسون
- معرفیشده توسط
- Lester R. Ford and Delbert R. Fulkerson
- سال
- 1956
- نوع
- algorithm
- خانواده
- Graph Algorithms
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
الگوریتم فورد-فالکرسون، که توسط لستر آر. فورد و دلبرت آر. فالکرسون در سال ۱۹۵۶ توسعه یافت، یک روش بنیادی برای محاسبه حداکثر جریان در یک شبکه جریان است. این الگوریتم حداکثر مقدار جریانی را پیدا میکند که میتواند از یک مبدأ به یک مقصد از طریق یک گراف جهتدار با محدودیتهای ظرفیت در یالها ارسال شود.
شهود پشت روش
این الگوریتم با یافتن مکرر مسیرهای افزایشی از مبدأ به مقصد از طریق شبکه پسماند کار میکند، جایی که هر یال ظرفیت باقیمانده دارد. هر مسیر جریانی اضافی برابر با ظرفیت گلوگاه خود (یال با حداقل ظرفیت باقیمانده در مسیر) را فراهم میکند. این فرآیند تا زمانی ادامه مییابد که دیگر مسیر افزایشی وجود نداشته باشد، در این نقطه حداکثر جریان به دست میآید. بینش کلیدی، قضیه حداکثر جریان-حداقل برش است: حداکثر جریان برابر با حداقل ظرفیت برش در شبکه است.
تاریخ
فورد و فالکرسون مسئله حداکثر جریان و الگوریتم بنیادی خود را در سال ۱۹۵۶ معرفی کردند. این کار انقلابی بود و هم یک روش الگوریتمی و هم قضیه مشهور حداکثر جریان-حداقل برش را بنیان نهاد. ادموندز و کارپ (۱۹۷۲) با استفاده از جستجوی عرض اول برای انتخاب مسیر، پیچیدگی بدترین حالت را بهبود بخشیدند. پیشرفتهای بعدی توسط دینیک، کارزانوف و دیگران منجر به الگوریتمهای حتی سریعتر شد، اما روش فورد-فالکرسون همچنان یک الگوریتم کلاسیک و از نظر آموزشی ارزشمند در علوم کامپیوتر باقی مانده است.
چه زمانی استفاده شود
الگوریتم فورد-فالکرسون را برای یافتن حداکثر جریان در شبکههای جریان جهتدار یا بدون جهت با ظرفیتهای عدد صحیح مثبت به کار ببرید. این الگوریتم برای شبکههای کوچک تا متوسط به خوبی کار میکند و درک شهودی از مفاهیم جریان شبکه را فراهم میآورد. برای شبکههای بسیار بزرگ یا زمانی که جریانهای صحیح مورد نیاز است، الگوریتم ادموندز-کارپ (با استفاده از BFS) یا الگوریتم دینیک را برای عملکرد بهتر در بدترین حالت در نظر بگیرید. از آن زمانی استفاده کنید که درک رفتار الگوریتم به اندازه سرعت مهم است.
محدودیتها و ملاحظات
- پیچیدگی زمانی به مقادیر ظرفیت بستگی دارد (به طور کلی چندجملهای نیست؛ میتواند با ظرفیتهای غیرمنطقی نمایی باشد)
- ممکن است در صورت غیرمنطقی بودن ظرفیتها خاتمه نیابد (نیاز به پیادهسازی دقیق با محاسبات منطقی دارد)
- کمتر کارآمد از الگوریتمهای تخصصی مانند ادموندز-کارپ یا دینیک در شبکههای بزرگ
- حساس به ترتیب انتخاب مسیر افزایشی
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- رویکرد ساده و شهودی مبتنی بر مسیرهای افزایشی
- راه حل بهینه در صورت منطقی یا صحیح بودن ظرفیتها تضمین شده است
- کارآمد برای شبکههای با ظرفیتهای عدد صحیح کوچک
- مبانی نظری برای درک دوگانگی حداکثر جریان-حداقل برش را تشکیل میدهد
- با هر دو گراف جهتدار و بدون جهت کار میکند
کاربردها
- مسیریابی شبکه: به حداکثر رساندن توان عملیاتی داده از مبدأ به مقصد در شبکههای ارتباطی
- شبکههای حمل و نقل: تعیین حداکثر ظرفیت بار بین شهرها با در نظر گرفتن محدودیتهای جادهای و ریلی
- تطبیق دو بخشی: یافتن تطبیقهای حداکثر در گرافهای دو بخشی با ساخت شبکههای جریان
- تقسیمبندی تصویر: استفاده از الگوریتمهای حداکثر جریان برای تقسیم تصاویر به پیشزمینه و پسزمینه
- برنامهریزی خطوط هوایی: بهینهسازی مسیر هواپیما برای به حداکثر رساندن جریان مسافر از طریق شبکههای هاب و اسپوک
- تجزیه و تحلیل پروتئین: محاسبه حداکثر جریان در شبکههای بیولوژیکی برای درک مسیرهای تعامل
چگونه کار میکند
چگونه کار میکند
گراف پسماند را با ظرفیتهایی برابر با ظرفیتهای یال اصلی و جریان صفر در تمام یالها مقداردهی اولیه کنید.
یک مسیر افزایشی از مبدأ به مقصد در گراف پسماند با استفاده از جستجوی عمق اول یا عرض اول پیدا کنید، حداقل ظرفیت در طول مسیر را محاسبه کنید، و این جریان را به تمام یالهای مسیر اضافه کنید در حالی که ظرفیتهای پسماند آنها را کاهش میدهید.
افزایش را تکرار کنید تا زمانی که هیچ مسیر افزایشی در گراف پسماند وجود نداشته باشد؛ کل جریان انباشته شده حداکثر جریان است.
دامهای رایج
- انتخاب مسیرهای افزایشی نامناسب که منجر به همگرایی کند یا نتایج نادرست میشود
- عدم بهروزرسانی صحیح ظرفیتهای پسماند یا عدم افزودن یالهای معکوس برای خنثی کردن جریان
- استفاده از تقسیم عدد صحیح یا محاسبات ممیز شناور زمانی که محاسبات دقیق برای صحت مورد نیاز است
پرسشهای متداول
قضیه حداکثر جریان-حداقل برش چیست؟
این قضیه بیان میکند که حداکثر جریان از مبدأ به مقصد برابر با حداقل ظرفیت هر برشی است که مبدأ را از مقصد جدا میکند. این امر هم یک بینش نظری و هم یک روش تأیید برای الگوریتمهای جریان فراهم میکند.
چرا الگوریتم گاهی اوقات به کندی همگرا میشود؟
با انتخابهای نامناسب مسیر، الگوریتم ممکن است در هر تکرار تنها یک واحد جریان را افزایش دهد، حتی زمانی که افزایشهای بزرگتر امکانپذیر است. استفاده از جستجوی عرض اول (ادموندز-کارپ) همگرایی در زمان چندجملهای را تضمین میکند.
الگوریتم چگونه یالهای بدون جهت را مدیریت میکند؟
هر یال بدون جهت را با دو یال جهتدار در جهتهای مخالف، هر دو با ظرفیت یکسان، جایگزین کنید. سپس الگوریتم جریان را در شبکه جهتدار پیدا میکند.
تفاوت بین جریان روی یک یال و ظرفیت پسماند چیست؟
جریان روی یک یال نشاندهنده مقدار ماده ارسال شده در طول آن است، در حالی که ظرفیت پسماند ظرفیت باقیمانده موجود است. ظرفیت پسماند با افزایش جریان کاهش مییابد، و یالهای معکوس قابلیت خنثی کردن جریان را ردیابی میکنند.
روشهای مرتبط
منابع
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
باز کردن مرجع DOIکپی شد.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
شابک: 978-0-262-03384-8کپی شد.