Skip to content
بازگشت به نتایج جست‌وجو

الگوریتم Push-Relabel

معرفی‌شده توسط
Andrew V. Goldberg and Robert E. Tarjan
سال
1988
نوع
algorithm
خانواده
Graph Algorithms

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

الگوریتم Push-Relabel که توسط اندرو وی. گلدبرگ و رابرت ای. تارژان در سال ۱۹۸۸ توسعه یافت، روشی بسیار کارآمد برای محاسبه حداکثر جریان در شبکه‌ها است. برخلاف روش‌های مسیر افزایشی، این الگوریتم یک پیش‌جریان (preflow) را حفظ می‌کند و از عملیات محلی push و عملیات سراسری relabel برای هدایت جریان به سمت خروجی (sink) استفاده می‌کند و به پیچیدگی بدترین حالت (worst-case complexity) برتری دست می‌یابد.

شهود پشت روش

این الگوریتم یک 'ارتفاع' یا 'برچسب فاصله' (height/distance label) برای هر گره حفظ می‌کند و از پیش‌جریان استفاده می‌کند (که در آن گره‌ها می‌توانند به طور موقت از تقاضای خروجی فراتر روند). این الگوریتم به طور مکرر جریان اضافی را از گره‌های با برچسب بالاتر به همسایگان با برچسب پایین‌تر می‌راند و گره‌ها را برای ایجاد مسیر به سمت خروجی دوباره برچسب‌گذاری (relabel) می‌کند. نکته کلیدی این است که با حفظ ناوردایی‌های ارتفاع و استفاده از ساختارهای داده کارآمد، الگوریتم از کاوش مکرر کل گراف، که روش‌های مسیر افزایشی باید انجام دهند، اجتناب می‌کند. الگوریتم زمانی خاتمه می‌یابد که تمام جریان اضافی به خروجی برسد.

تاریخ

گلدبرگ و تارژان الگوریتم push-relabel خود را در سال ۱۹۸۸ منتشر کردند و یک پارادایم اساساً متفاوت برای محاسبه حداکثر جریان معرفی نمودند. الگوریتم آن‌ها به پیچیدگی بدترین حالت O(V³) دست یافت که نسبت به O(VE²) الگوریتم Edmonds-Karp بهبود یافته بود. در دهه‌های بعدی، انواع متعددی توسعه یافتند، از جمله هیوریستیک‌های شکاف (گلدبرگ و تارژان، ۱۹۹۰)، قوانین بالاترین برچسب (highest-label rules)، و آخرین انواع که به عملکرد تجربی نزدیک به خطی در شبکه‌های واقعی دست یافتند.

چه زمانی استفاده شود

الگوریتم push-relabel را برای محاسبه حداکثر جریان در شبکه‌های بزرگ و متراکم که در آن‌ها روش‌های مسیر افزایشی ناکارآمد می‌شوند، به کار ببرید. این الگوریتم به ویژه برای شبکه‌هایی با هزاران یا میلیون‌ها یال مؤثر است. زمانی از آن استفاده کنید که به عملکرد تضمین‌شده چندجمله‌ای (polynomial-time) نیاز دارید و می‌خواهید از ساختارهای داده مدرن بهره ببرید. برای شبکه‌های پراکنده یا اهداف آموزشی، روش‌های مسیر افزایشی ممکن است درک و پیاده‌سازی ساده‌تری داشته باشند.

محدودیت‌ها و ملاحظات

  • درک و پیاده‌سازی پیچیده‌تر از روش‌های مسیر افزایشی
  • نیاز به مدیریت دقیق ساختارهای داده (لیست‌های تخلیه، هیوریستیک شکاف) برای عملکرد بهینه
  • پیچیدگی بدترین حالت همچنان بالاتر از برخی الگوریتم‌های تخصصی برای کلاس‌های گراف خاص است
  • درک کمتر شهودی از فرآیند حل در مقایسه با مسیرهای افزایشی

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • پیچیدگی زمانی بدترین حالت برتر: O(V³) یا O(V²√E) با هیوریستیک شکاف (gap heuristic)
  • در عمل بسیار کارآمد، به ویژه برای شبکه‌های بزرگ و متراکم
  • محلّی بودن عملیات (push/relabel) امکان عملکرد خوب حافظه نهان (cache performance) را فراهم می‌کند
  • قابلیت موازی‌سازی و پیاده‌سازی توزیع‌شده
  • انواع مختلف پیاده‌سازی برای ساختارهای مسئله متفاوت

کاربردها

  • مسیریابی شبکه: محاسبه حداکثر توان عبوری در شبکه‌های ارتباطی در مقیاس بزرگ
  • پردازش تصویر: استفاده از max-flow برای بخش‌بندی تصویر و کاربردهای matting
  • بهینه‌سازی خطوط هوایی: تعیین حداکثر جریان مسافر از طریق شبکه‌های مسیریابی پیچیده
  • تحلیل شبکه برق: محاسبه حداکثر ظرفیت انتقال توان در شبکه‌های الکتریکی
  • مدیریت زنجیره تأمین: بهینه‌سازی جریان محصول از طریق شبکه‌های توزیع چندلایه
  • شبکه‌های بیولوژیکی: تجزیه و تحلیل حداکثر جریان در شبکه‌های متابولیک و برهم‌کنش پروتئین

چگونه کار می‌کند

چگونه کار می‌کند

1

ارتفاع مبدأ (source) را برابر تعداد رأس‌ها و ارتفاع سایر گره‌ها را صفر قرار دهید. تمام یال‌های خروجی از مبدأ را اشباع کنید تا پیش‌جریان اولیه ایجاد شود (جریان اضافی در گره‌های همسایه).

2

به طور مکرر یک گره فعال (دارای جریان اضافی) را انتخاب کنید و یا جریان اضافی را به یک همسایه با ارتفاع کمتر برانید (push) یا گره را برای افزایش ارتفاعش دوباره برچسب‌گذاری کنید (relabel). از استراتژی‌های انتخاب کارآمد و عملیات تخلیه (discharge) برای به حداقل رساندن تکرارها استفاده کنید.

3

تا زمانی که هیچ گره فعالی باقی نمانده است، ادامه دهید؛ در این مرحله، تمام پیش‌جریان به حداکثر جریان از مبدأ به خروجی تبدیل شده است.

دام‌های رایج

  • پیاده‌سازی نادرست به‌روزرسانی ارتفاع یا عملیات push که منجر به جریان‌های غیرحداکثر می‌شود
  • نادیده گرفتن استفاده از هیوریستیک شکاف و انتخاب گره کارآمد، که منجر به عملکرد ضعیف عملی می‌شود
  • عدم حفظ صحیح ناوردایی پیش‌جریان (جریان اضافی در گره‌ها و محدودیت‌های ظرفیت روی یال‌ها)

پرسش‌های متداول

تفاوت پیش‌جریان (preflow) و جریان (flow) چیست؟

پیش‌جریان به طور موقت به گره‌ها اجازه می‌دهد تا جریان اضافی را نگه دارند (جریان ورودی منهای جریان خروجی می‌تواند مثبت باشد)، در حالی که جریان واقعی باید در تمام گره‌ها به جز مبدأ و خروجی، پایسته باشد. الگوریتم زمانی خاتمه می‌یابد که پیش‌جریان به یک جریان معتبر تبدیل شود.

هدف تابع ارتفاع چیست؟

ارتفاع‌ها یک معیار شبه‌فاصله ایجاد می‌کنند: جریان فقط می‌تواند به سمت پایین (از ارتفاع‌های بالاتر به پایین‌تر) رانده شود، که از چرخه‌های غیرضروری جلوگیری کرده و خاتمه را تضمین می‌کند. ارتفاع‌ها از طریق relabeling افزایش می‌یابند تا در صورت نیاز مسیرهای جدیدی ایجاد کنند.

هیوریستیک شکاف چیست و چرا مهم است؟

هیوریستیک شکاف زمانی تشخیص می‌دهد که هیچ گره‌ای در یک محدوده ارتفاعی خاص وجود ندارد، که نشان می‌دهد برخی گره‌ها نمی‌توانند به خروجی برسند. این گره‌ها و جریان اضافی آن‌ها به سرعت شناسایی و پردازش می‌شوند و عملکرد عملی را به طور قابل توجهی بهبود می‌بخشند.

مقایسه عملی push-relabel با Edmonds-Karp چگونه است؟

push-relabel پیچیدگی بدترین حالت بهتری دارد و معمولاً در شبکه‌های بزرگ از Edmonds-Karp بهتر عمل می‌کند، اما برای شبکه‌های کوچک یا گراف‌های پراکنده، Edmonds-Karp ممکن است پیاده‌سازی ساده‌تری با عملکرد رقابتی داشته باشد.

روش‌های مرتبط

منابع

  1. Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.

    باز کردن مرجع DOI
    کپی شد.
  2. Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.

    باز کردن مرجع انتشار
    کپی شد.