الگوریتم ارسال-برچسب

الگوریتم ارسال-برچسب یکی از کارآمدترین الگوریتم‌ها برای محاسبه‌ی یک مسئله بیشینه جریان است. الگوریتم عمومی دارای پیچیدگی زمانی $O(V^2 E)$ است، در حالی که پیاده‌سازی آن با قانون شیوه‌ی رأس‌ها به صورت FIFO دارای زمان اجرای $O(V^3)$، با شیوه‌ی انتخاب فعال‌ترین رأس دارای پیچیدگی زمانی $O(V^2\sqrt{E})$ و با پیاده سازی با کمک داده‌ساختار درخت پویای ترجان و اسلیتور دارای زمان اجرای $O(V E \log(V^2/E))$ است. مجانباً این الگوریتم، از الگوریتم ادموند-کارپ که زمان اجرای آن $O(VE^2)$ است کاراتر است.

الگوریتم

شبکه جریان $O(VE^2)$ داده شده که دارای ظرفیت (به انگلیسی: capacity) از گره u تا گره v است که به صورت $c(u,v)$ داده شده، دارای منبع (به انگلیسی: s (source و چاهک (به انگلیسی: t (sink است. می‌خواهیم بیشترین میزان جریان را که می‌شود درون شبکه از s به t فرستاد را بیابیم. دو نوع عملیات روی گره‌ها انجام می‌شود: push و relabel. به طور کلی داریم:

• $f(u,v)$. جریان از u به v. ظرفیت قابل استفاده برابر است با $c(u,v) - f(u,v)$.
• $height(u)$. تنها در صورتی از u به v عمل push را انجام می‌دهیم که $height(u) > height(v)$. به ازای همه‌ی مقادیر u مقدار $height(u)$ یک عدد صحیح غیر منفی است.
• $excess(u)$. حاصل جمع جریان وارد شده و خارج شده از u.

بعد از هر گام الگوریتم، جریان یک پیش جریان (به انگلیسی: preflow) است که شرایط زیر را دارد:

• $\ f(u,v) \leq c(u,v)$. جریان بین $u$ و $v$ از ظرفیت بیشتر نباشد.
• $\ f(u,v) = - f(v,u)$. جریان شبکه را در هر دو جهت حفظ می‌کنیم.
• به ازای تمام گره‌ها به صورت $u \neq s$ ،$\ \sum_v f(v,u) = excess(u) \geq 0$. تنها منبع امکان ایجاد جریان داشته باشد.

توجه داشته باشید که آخرین وضعیت یک پیش‌جریان از وضعیت متناظر برای یک جریان مجاز در یک در یک شبکه جریان منظم، مجزاست.

ملاحظه می‌کنیم که طولانی‌ترین مسیر ممکن از s به t دارای بزرگی $|V|$ گره است. بنا بر این باید امکان‌.پذیر باشد که ارتفاع (به انگلیسی: height) را به گره‌های هر جریان مجاز اختصاص دهیم، $height(s) = |V|$ و $height(t) = 0$، و اگر یک جریان مثبت از u به v وجود داشت، $height(u) > height(v)$. حال که ما ارتفاع گره‌ها را تعیین کردیم، جریان در شبکه به حرکت در می‌آید (مانند جریان آب بر روی پستی و بلندی). بر خلاف الگوریتم‌هایی مانند فورد-فالکرسون،‌ جریان در طول شبکه، لزماً یک جریان مجاز در اجرای الگوریتم نیست.

به طور خلاصه، ارتفاع‌های گره‌ها (به جز s و t) تعیین شده‌اند، و جریان بین گره‌ها فرستاده می‌شود، تا زمانی که تمام جریان‌های ممکن به t برسند. سپس می‌توانیم افزایش ارتفاع گره‌های درونی را ادامه دهیم تا تمام جریان‌هایی که درون شبکه رفته‌اند ولی به t نرسیده‌اند، به سمت s بازگردند. یک گره قبل از پایان کار می‌تواند به ارتفاع $2|V|-1$ برسد، بنا بر این، طولانی‌ترین مسیر ممکن که به s بر می‌گردد ولی شامل t نیست دارای طول $|V|-1$ است و $height(s) = |V|$. ارتفاع t روی صفر نگه داشته می‌شود.

Push

یک push از u به v به معنی فرستادن قسمتی از جریان اضافی ورودی به u به سمت v است. برای رخ دادن یک push باید سه شرط رعایت شود:

• $excess(u) > 0$. جریان ورودی به گره، از جریانی که تا کنون از آن خارج می‌شده بیشتر باشد.
• $c(u,v) - f(u,v) > 0$. ظرفیت قابل استفاده از u به v.
• $height(u) > height(v)$. تنها امکان ارسال به گره در ارتفاع کم‌تر وجود دارد. ما جریانی به اندازه‌ی $\min(excess(u), c(u,v)-f(u,v))$ می‌فرستیم.

Relabel

یک عمل relabel روی یک گره، افزایش ارتفاع آن است تا جایی که حداقل از یکی از گره‌هایی که به آن ظرفیت قابل استفاده دارد ارتفاع بیشتری پیدا کند. شرط‌هایی که برای یک relabel وجود دارد:

• $excess(u) > 0$. باید یک حدی برای relabel وجود داشته باشد.
• $height(u) \leq height(v)$ به ازای هر v برقرار باشد. تنها گره‌هایی که به آن‌ها ظرفیت قابل استفاده داریم در ارتفاع بیشتری باشند.

هنگام انجام relabel روی u، باید $height(u)$ را با کم‌ترین مقدار، مقداردهی کنیم به طوری که برای بعضی vها که $c(u,v)-f(u,v) > 0$ است، $height(u) > height(v)$.

الگوریتم push-relabel

push-relabel در حالت کلی چیدمان زیر را دارد:

• تا زمانی که یک عمل push یا relabel مجاز وجود دارد
  1. یک push مجاز انجام بده، یا
  2. یک relabel مجاز

زمان اجرای برای این الگوریتم در حالت کلی برابر $O(V^2 E)$ است.

تخلیه

در relabel رو به جلو (به انگلیسی: relabel-to-front)، عمل تخلیه (به انگلیسی: decharge) روی گره‌ u به صورت زیر است:

• تا زمانی که $excess(u) > 0$:
  1. اگر از زمان آخرین relabel همسایه‌ای وجود دارد که بررسی نشده است:
     • push کردن جریان به یک همسایه‌ي بررسی نشده را انجام بده.
  2. در غیر این صورت:
     • u را relabel کن.

برای این کار لازم است که برای هر گره، بدانیم از زمان آخرین relabel کردن کدام گره‌ها بررسی نشده‌اند.

الگوریتم relabel رو به جلو

در الگوریتم relabel رو به جلو، ترتیب push و relabel بدین صورت است:

1. تا جای ممکن از s به بیرون جریان بفرست.
2. لیستی از تمام رأس‌ها به جز s و t بساز.
3. تا زمانی که تمام لیست را پیمایش نکردیم:
   1. رأس فعلی را تخلیه کن.
   2. اگر ارتفاع رأس فعلی تغییر کرد:
      1. رأس فعلی را به جلوی لیست منتقل کن.
      2. دوباره از جلوی لیست پیمایش کن.

زمان اجرای الگوریتم relabel رو به جلو برابر $O(V^3)$ است.

پیاده‌سازی نمونه

پیاده‌سازی با پایتون:

  def relabel_to_front(C, source, sink):
     n = len(C) # C is the capacity matrix
     F = [[0] * n for _ in xrange(n)]
     # residual capacity from u to v is C[u][v] - F[u][v]
 
     height = [0] * n # height of node
     excess = [0] * n # flow into node minus flow from node
     seen   = [0] * n # neighbours seen since last relabel
     # node "queue"
     list   = [i for i in xrange(n) if i != source and i != sink]
 
     def push(u, v):
         send = min(excess[u], C[u][v] - F[u][v])
         F[u][v] += send
         F[v][u] -= send
         excess[u] -= send
         excess[v] += send
 
     def relabel(u):
         # find smallest new height making a push possible,
         # if such a push is possible at all
         min_height = ∞
         for v in xrange(n):
             if C[u][v] - F[u][v] > 0:
                 min_height = min(min_height, height[v])
                 height[u] = min_height + 1
 
     def discharge(u):
         while excess[u] > 0:
             if seen[u] < n: # check next neighbour
                 v = seen[u]
                 if C[u][v] - F[u][v] > 0 and height[u] > height[v]:
                     push(u, v)
                 else:
                     seen[u] += 1
             else: # we have checked all neighbours. must relabel
                 relabel(u)
                 seen[u] = 0
 
     height[source] = n   # longest path from source to sink is less than n long
     excess[source] = Inf # send as much flow as possible to neighbours of source
     for v in xrange(n):
         push(source, v)
 
     p = 0
     while p < len(list):
         u = list[p]
         old_height = height[u]
         discharge(u)
         if height[u] > old_height:
             list.insert(0, list.pop(p)) # move to front of list
             p = 0 # start from front of list
         else:
             p += 1
 
     return sum(F[source])

توجه داشته‌باشید که پیاده‌سازی بالا چندان کارآمد نیست. این پیاده‌سازی از الگوریتم ادموند-کارپ حتی برای گراف‌های پرتراکم کندتر است.

منابع

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 26.4: Push-relabel algorithms, and section 26.5: The relabel-to-front-algorithm.

• Andrew V. Goldberg, Robert E. Tarjan. A new approach to the maximum flow problem. Annual ACM Symposium on Theory of Computing, Proceedings of the eighteenth annual ACM symposium on Theory of computing, 136–146. ISBN 0-89791-193-8 1986

• مشارکت‌کنندگان ویکی‌پدیا، «Push-relabel maximum flow algorithm»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در 30 نوامبر ۲۰۱۱).

جستارهای وابسته

• الگوریتم فورد-فالکرسون
• برش بیشینه
• برش کمینه
• مسئله بیشینه جریان