الگوریتم Goldberg و Tarjan

1- مسئله گردش با کمترین هزینه

ورودی‌های مسئله عبارتند از:

• گراف جهت دار $G=(V,A)$
• هزینه‌ها که اعداد صحیح هستند. $c_{ij}\in Z,\forall (i,j)\in A$
• ظرفیت‌ها که اعداد صحیح هستند. $u_{ij}\geq 0,\forall (i,j)\in A$
• تقاضاها که اعداد صحیح هستند. $0\leq l_{ij}\leq u_{ij},\forall (i,j)\in A$

هدف: یافته جریان $f:A\rightarrow R^{\geq 0}$ است که$\sum _{(i,j)\in A}c_{ij}f_{ij}$ را مینیمم می‌کند به‌طوری که:
$l_{ij}\leq u_{ij}\quad \forall (i,j)\in A$
$\sum _{k:(i,k)\in A}f_{ik}-\sum _{k:(k,i)\in A}f_{ki}=0$
تعریف 1: یک گردش $f$ شرایط زیر را ارضا می‌کند.

• $f_{ij}\leq u_{ij}\quad \forall (i,j)\in A$
• $f_{ij}=-f_{ji}\quad \forall (i,j)\in A$
• $\sum _{k:(k,i)\in A}f_{ki}=0$

در این تعریف جدید، جریان در قوس اولیه $f_{ij}$ شرط $f_{ij}\leq u_{ij}$ را ارضا می‌کند و هر واحد جریان هزینه $c_{ij}$ را تحمیل می‌کند. جریان در قوس معکوس $f_{ji}$ شرط $f_{ji}\leq u_{ji}=-f_{ij}$ را ارضا کرده و هزینه $c_{ji}=-c_{ij}$ را برای هر واحد جریان تحمیل می‌کند. هزینه کل برای دو یال با جریان $f$ برابر $c_{ij}f_{ij}+c_{ji}f_{ji}=2c_{ij}f_{ij}$ است. بنابراین بهینه‌سازی هزینه کل برای این گراف جدید معادل بهینه‌سازی هزینه کل برای گراف اولیه است.
برای یک جریان $f$ در گراف $G$ گراف باقی‌مانده $G_{f}=(V,A_{f})$ را گرافی تعریف می‌کنیم که مجموعه یال‌های آن عبارتند از:
$A_{f}=\left\lbrace (i,j)\in A:f_{ij}<u_{ij}\right\rbrace$
کران بالای $u_{ij}^{f}=u_{ij}-f_{ij}$ را برای یال $(i,j)\in A_{f}$ تعریف می‌کنیم. واضح است که $\forall (i,j)\in A_{f}:u_{ij}^{f}<0$
تعریف 2: یک پتانسیل تابعی است به صورت $p:V\rightarrow R$
تعریف 3: فرض کنید تابع پتانسیل $p$ داده شده‌است. هزینه کاهش یافته را به صورت زیر تعریف می‌کنیم:
$c_{ij}^{p}=c_{ij}+p_{i}-p_{j}$
آنگاه داریم:
$c_{ji}^{p}=c_{ji}+p_{j}-p_{i}=-(c_{ij}+p_{i}-p_{j})=-c_{ij}^{p}$
تعریف 4: هزینه یک دور $\Gamma$ برابر است با: $c(\Gamma )=\sum _{(i,j)\in \Gamma }c_{ij}$ تئوری 1: موارد زیر با هم معادلند.

• f یک گردش با کمترین هزینه است.
• هیچ دور با هزینه منفی در $G_{f}$ وجود ندارد.
• تابع پتانسیل $f$ موجود است که برای هر $(i,j)\in A_{f}$ داریم $c_{ij}^{p}\geq 0$

2- الگوریتم حذف یک دور

تئوری فوق منجر به الگوریتمی برای محاسبه گردش با کمترین هزینه می‌شود. این الگوریتم به صورت زیر است.

فرض کنید که $f$ یک گردش شدنی باشد.

تا وقتی که $A_{f}$ شامل دور منفی $\Gamma$ است.
    $\Gamma$ را حذف کرده و  $f$ را به روز رسانی کن.

صحت الگوریتم فوق از تئوری بالا نتیجه می‌شود. اگر هزینه‌ها و ظرفیت‌ها، هر دو صحیح باشند، جریان بهینه $f$ موجود است به نحوی که $f_{ij}$ برای هر $(i,j)\in A$ صحیح است. فرض کنید:
$U=max\quad u_{ij_{(i,j)\in A}}$
$C=max\quad |c_{ij}|_{(i,j)\in A}$
بنابراین هر گردش شدنی دارای هزینه حداکثری $mCU$ و هزینه حداقلی $-mCU$ است. چون حذف یک دور، هزینه گردش را حداقل به اندازه یک واحد کاهش می‌دهد، برای یافتن یک گردش بهینه به حداکثر $O(mCU)$ حذف نیاز است.
برای رسیدن به این نتیجه‌گیری که الگوریتم فوق شبه چندجمله‌ای است، به دو مورد زیر نیاز داریم.

• یک گردش اولیه. (این گردش را می‌توان با محاسبه گردش ماکسیمم به دست آورد.)
• امکان چک کردن وجود دور با هزینه منفی. (این کار را می‌توان با استفاده از الگوریتم bellman-ford در زمان $O(mn)$ انجام داد. بنابراین ما یک الگوریتم چندجمله‌ای داریم که در زمان $O(m^{2}nCU)$ اجرا می‌شود.

3- حذف دور با کمترین هزینه متوسط

با انتخاب مناسب دوری که در هر مرحله تکرار الگوریتم باید حذف شود، می‌توان یک الگوریتم با زمان چندجمله‌ای به دست آورد.
تعریف 5: فرض کنید که هزینه متوسط دور $\Gamma$ برابر با ${\frac {c(\Gamma )}{|\Gamma |}}$ باشد که $c(\Gamma )$ هزینه دور و $|\Gamma |$ تعداد یال‌های موجود در $\Gamma$ است.
تعریف 6: فرض کنید گردش $f$ داده شده باشد و $\mu (f)$ هزینه دور با کمترین هزینه متوسط باشد. $\mu (f)=min{\frac {c(\Gamma )}{|\Gamma |}}_{cycles\Gamma \subseteq A_{f}}$
می توان با حذف دور با کمترین هزینه مینیمم، یک الگوریتم چندجمله‌ای به دست آورد. اکنون می‌توانیم الگوریتم زیر را بیان کنیم.

فرض کنید $f$ یک گردش باشد
تا زمانی که $\mu (f)<0$
     دور $\Gamma$ با کمترین هزینه متوسط را حذف کن. $f$ را به روز رسانی کن.

شرط $\mu (f)<0$ معادل داشتن یک دور با هزینه منفی در $A_{f}$ است. برای داشتن یک الگوریتم با زمان چندجمله‌ای، باید بتوانیم دور با هزینه متوسط کمینه را در زمان چندجمله‌ای پیدا کنیم.
برای تحلیل الگوریتم فوق، تعدادی اصطلاح را تعریف می‌کنیم.
تعریف7: یک گردش $f$، $\varepsilon$-بهینه است اگر تابع پتانسیل $p$ موجود باشد که برای هر $(i,j)\in A_{f}$ داشته باشیم $c_{ij}^{p}\geq -\varepsilon$
واضح است که $f$، 0-بهینه است؛ اگر و تنها اگر $f$ یک گردش با کمترین هزینه باشد. برای هر گردش، $f$، $C$-بهینه است. زیرا اگر برای هر $i\in V$ قرار دهیم $p_{i}=0$؛ برای هر $(i,j)\in A_{f}$ داریم $c_{ij}^{p}\geq -C$.
تعریف 8: $\varepsilon (f)$ کمترین $\varepsilon$ است که $f$، $\varepsilon$- بهینه باشد.
دو مقدار $\varepsilon (f)$ و $\mu (f)$ به شکل جالبی به هم مرتبطند.
تئوری 2: برای یک گردش $f$ داریم: $\mu (f)=-\varepsilon (f)$
اثبات: ابتدا نشان می‌دهیم $\mu (f)\geq -\varepsilon (f)$.
چون
$\exists p:c_{ij}^{p}\geq -\varepsilon (f)\forall (i,j)\in A_{f}$
با جمع کردن روی تمام یال‌های هر دور $\Gamma$ می‌بینیم که

$c^{p}(\Gamma )\geq \varepsilon (f)|\Gamma |$. بنابراین برای دور با هزینه متوسط کمینه $\Gamma$ داریم:

$\mu (f)={\frac {c\left(\Gamma \right)}{|\Gamma |}}={\frac {c^{p}\left(\Gamma \right)}{|\Gamma |}}\geq -\varepsilon (f)$
حال نشان می‌دهیم که $\mu (f)\leq -\varepsilon (f)$.
قرار می‌دهیم ${\bar {c}}_{ij}=c_{ij}-\mu (f)$. آنگاه برای هر دور$\Gamma$ در $A_{f}$ داریم:
${\bar {c}}(\Gamma )=c(\Gamma )-|\Gamma |\mu (f)\geq c(\Gamma )-|\Gamma |{\frac {c(\Gamma )}{|\Gamma |}}=0$
راس $s$ را به گراف اضافه کرده و و آن را به همه رئوس $i$، با یال‌هایی به وزن $c_{si}=0$ وصل می‌کنیم. پتانسیل $p_{i}$ را برای گره $i$ به صورت طول کوتاه‌ترین مسیر از $s$ به $i$ با استفاده از هزینه‌های ${\bar {c}}_{ij}$ تعریف می‌کنیم. با استفاده از تعریف کوتاهترین مسیر داریم:
$\forall (i,j)\in A_{f},p_{j}\leq p_{i}+{\bar {c}}_{ij}=p_{i}+c_{ij}-\mu (f)$
که نتیجه می‌دهد:
$\forall (i,j)\in A_{f},c_{ij}^{p}=c_{ij}+p_{i}-p_{j}\geq \mu (f)$
این بدان معنی است که $f$، $-\mu (f)$- بهینه است. بنابراین $\varepsilon (f)\leq -\mu (f)$
فرض کنید گردش $f$ داده شده باشد و $f^{(k)}$ گردش به دست آمده بعد از $k$ بار تکرار الگوریتم حذف دور با کمترین هزینه متوسط روی $f$ باشد. تئوری زیر ثابت می‌کند که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای اجرا می‌شود.
تئوری3: $\varepsilon \left(f^{(1)}\right)\geq \varepsilon (f)$
تئوری4: $\varepsilon \left(f^{(m)}\right)\geq \left(1-{\frac {1}{n}}\right)\varepsilon (f)$
که $m$ و $n$ تعداد یال‌ها و گره‌ها در گراف هستند.
تئوری5: اگر $\varepsilon (f)\geq {\frac {1}{n}}$ گردش $f$ بهینه است.
اثبات: این حقیقت که $\varepsilon (f)\leq {\frac {1}{n}}$ نشان می‌دهد که پتانسیل $p$ موجود است که $\forall (i,j)\in A_{f}:c_{ij}^{p}>{\frac {-1}{n}}$. بنابراین برای هر دور $\Gamma \in A_{f},c(\Gamma )=c^{p}>-1$. با توجه به صحیح بودن هزینه‌ها داریم؛ $c(\Gamma )\geq 0$
حال با توجه به سه نتیجه قبل ثابت می‌کنیم که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای بر حسب اندازه ورودی، خاتمه می یابد.
تئوری6: الگوریتم حذف دور با کمترین هزینه متوسط Goldberg-Tarjan، به حداکثر $O(mn\log(nC))$ تکرار نیاز دارد.
اثبات: هر گردش اولیه C- بهینه است. بعد از $mn\log(nC)$ تکرار، با توجه به اینکه $\left(1-{\frac {1}{n}}\right)^{n}<e^{-1}$، داریم: $\varepsilon \left(f^{(k)}\right)\leq \left(1-{\frac {1}{n}}\right)^{n\log(nC)}<e^{-\log(nC)}C={\frac {1}{n}}$
اگر محاسبه دور با هزینه متوسط کمینه، زمانی برابر $O(mn)$ داشته باشد، زمان اجرای الگوریتم Goldberg-tarjan برابر $O\left(m^{2}n^{2}\log(nC)\right)$ خواهد بود. البته توجه داشته باشید که این الگوریتم کاملاً چندجمله‌ای نیست.
اثبات تئوری 3: می‌دانیم پتانسیل $p$ موجود است که:
$\forall (i,j)\in A_{f}:c_{ij}^{p}\geq -\varepsilon (f)$
به علاوه، $\mu (f)=-\varepsilon (f)$. برای دور $\Gamma$ با کمترین هزینه متوسط، چون $\mu (f)={\frac {c^{p}(\Gamma )}{|\Gamma |}}$، نتیجه می‌گیریم که $\forall (i,j)\in \Gamma ,c_{ij}^{p}\geq -\varepsilon (f)$. حال ادعا می‌کنیم که $\forall (i,j)\in A_{f^{(1)}}:c_{ij}^{p}\geq -\varepsilon (f)$. داریم $(i,j)\in A_{f^{(1)}}$، اگر $(i,j)\in A_{f}$ یا $(j,i)\in \Gamma$. در حالت اول، $c_{ij}^{p}\geq -\varepsilon (f)$. در حالت دوم، $c_{ij}^{p}=c_{ji}^{p}=\varepsilon (f)\geq 0$. در هر دو حالت، $f^{(1)}$، $\varepsilon (f)$ -بهینه است و تئوری ثابت می‌شود.
اثبات تئوری4: می‌دانیم پتانسیل $p$ موجود است که $\forall (i,j)\in A_{f}:c_{ij}^{p}\geq -\varepsilon (f)$. فرض کنید در تکرار $k$، دور $\Gamma$ را حذف می‌کنیم که در آن، $\exists (i,j)\in \Gamma :c_{ij}^{p}\geq 0$. آنگاه
$\varepsilon \left(f^{(k)}\right)=\mu \left(f^{(k)}\right)={\frac {c^{p}(\Gamma )}{|\Gamma |}}\geq {\frac {|\Gamma |-1}{|\Gamma |}}\left(-\varepsilon (f)\right)\geq \left(1-{\frac {1}{n}}\right)(-\varepsilon (f))$
بنابراین $\varepsilon \left(f^{(k)}\right)\leq \left(1-{\frac {1}{n}}\right)(\varepsilon (f))$

حذف دور، یک یال با $c_{ij}^{p}<0$ را از گراف باقی‌مانده حذف و تنها یال‌هایی با $c_{ij}^{p}>0$ را ایجاد می‌کند. بنابراین برای حذف چنین یالی به بیش از $m$ تکرار نیاز نیست. انتزاعی
الگوریتم هزینه پیمایش گولد برگ (Goldberg) و تارجان(Tarjan)، یکی از کارآمدترین الگوریتم‌ها، برای روند کمترین هزینهٔ مسائل، شناخته شده‌است. اگر چه بازده آن در عمل، به بسیاری از جوانب اجرا بستگی دارد. علاوه بر این، گنجایش بسیاری از ابتکارات، کارایی آن را شدیدا بهبود می‌بخشد. در این مقاله به شرح جوانب اجرا و کارآمدترین ابتکارات، می پردازیم. همچنین، نتایج تجربی، اثر ابتکارات مختلف ترکیبی را پررنگ می‌کند.

کلمات کلیدی: روند کمترین هزینه، الگوریتم گولد برگ- تارجان، اجرا کارآمد

مقدمه

فرض می‌کنیم با تئوری روند شبکه آشنایی داریم و نتایج و نشان‌گذاری استاندارد را استفاده می‌کنیم. برای مثال آهوجا(Ahuja)، مگنانتی(Magnanti)،ارلین(Orlin)را ببینید. در اینجا فقط مهمترین‌ها را ذکر می‌کنیم. مسئله روند کمترین هزینه به این صورت تعریف می‌شود: گراف جهتدار $G$ با گنجایش $u$ داده شده‌است: $E(G)\rightarrow R_{+}$ ، سنگینی $c:E(G)\rightarrow R$ و ارزش تعادل $b:V(G)\rightarrow R$، $b$ را به عنوان یک روند کمترین روند هزینه بیابید، به‌طوری‌که تابع $f:E(G)\rightarrow R_{+}$ با $F(e)\leq u(e)$ برای همهٔ $e$‌های عضو $E(G)$ و $\sum _{e\in \delta _{G}^{+}(v)}f(e)-\sum _{e\in \delta _{G}^{-}(v)}$برای همهٔ $v$‌های عضو $V(G)$ از قبیل $\sum {e\in E(G)}(f(e)c(e))$ که کمترین مقدار یا همان مینیموم می‌باشد $\delta _{G}^{+}$مجموعه‌ای از ورودی‌های را تشکیل می‌دهد. راس $v$ باقی می‌ماند.
واضح است که امکان وجود روند کمترین هزینهٔ مسائل، می‌تواند در برابر محاسبه روند ماکسیموم چک شود ( و در بهترین شرایط روند $b$ می‌تواند پیدا شود). مسائل روند ماکسیموم آسانترند و خیلی سریعتر از مسائل روند کمترین هزینه حل می‌شوند.
نمونه داده شده $(G,u,c,b)$ از مسئله روند کمترین هزینه و روند $f:E(G)\rightarrow R_{+}$ با $f(e)\leq u(e)$ برای همهٔ $e\in E(G)$، ظرفیت باقی‌ماندهٔ یال $e\in E(G)$ به وسیله $u_{f}(e):=u(f)-f(e)$ تعریف می‌شود.
علاوه بر این، ما یک یال جدید $e$ از $w$ به $v$ برای هر یال $e=(v,w)$ در نظر گرفته ایم و $u_{f}(e):=f(e)$ و $c(e):=-c(e)$ تعریف کرده ایم. باقی‌مانده گراف $G_{f}$ شامل همه بال‌ها ( قدیمی و جدید) با ظرفیت باقی‌مانده مثبت می‌باشد. معروف است که روند $b$ از $f$ بهینه است( کمترین هزینه را دارد) اگر و تنها اگر هیچ جریان مستقیم در $G_{f}$ وزن منفی نداشته باشد.
دیاگراف $G$ داده شده با وزن $c:E(G)\rightarrow R$، یک ذخیره امکانپذیر در $(G,c)$ است، تابع $\pi :V(G)\rightarrow R$ به این صورت که هزینه کاهش یافته $C\pi (e):=c(e)+\pi (v)\pi (w)$ است که برای هر $e$ نامنفی عبارت $e=(v,w)$ برقرار است. یک ذخیره امکانپذیر وجود دارد اگر و تنها اگر هیچ جریان مستقیمی، وزن کل منفی نداشته باشد. این توسط کوتاه‌ترین راه محاسبه منبع واحد قطعی و تصمیم گرفته می‌شود.
روند داده شده$f:E(G)\rightarrow R_{+}$ با $f(e)\leq u(e)$ و ذخیره $\pi :V(G)\rightarrow R$، یک گراف مجاز تعریف می‌کنیم که تمام یال‌های $G_{f}$ که هزینهٔ کاهش یافته منفی را دارند، در بر بگیرد. گراف مجاز را با ${}_{f}^{\pi }G$ معنی می‌کنیم. اگر $f$ یک روند $b$ بهینه باشد( برای بعضی از $b$ها) و $\pi$ یک ذخیره امکانپذیر در $G_{f}$ باشد، پس مارپیچ است.

الگوریتم گولبرگ و تارجان

یک روند $b$، $\varepsilon$ -بهینه نامیده می‌شود اگر یک ذخیره $\pi :V(G)\rightarrow R$ مانند $c_{\pi }(e)\geq -\varepsilon$ برای همهٔ $e\in (G_{f})$. پس بهینه 0 هیچ چیز نیست ولی بهینه است. الگوریتم هزینه پیمایش گولبرگ و تارجان یک روند $b$ را محاسبه می‌کند که بهینه $\varepsilon$ برای بعضی از $\varepsilon$‌های بزرگ است. پس مقدار $\varepsilon$ را در هر تکرار، نگهداری کردن و بهینگی $\varepsilon$، کاهش می‌دهد.
ساده است که هر روند $b$، بهینه $\varepsilon$ است اگر $\varepsilon \geq max_{e\in E(G)}\quad |c(e)|$ . علاوه بر این، از دید هزینه‌های انتگرال، هر روند $\varepsilon$-بهینه با $\varepsilon <{\frac {1}{n}}$، بهینه است. پس ساختار جهانی این الگوریتم، به صورت زیر است.
($\alpha$ یک پارامتر ثابت است و حداقل مقدار آن 2 می‌باشد)

${\text{procedure }}minimum\_cost\_flow(G,u,c,b)$
${\text{begin}}$
  $\pi (v):=0\quad \forall v\in V(G){\text{ and }}\varepsilon :=max_{e\in E(G)}|c(e)|;$
  ${\text{Determine a b}}\_{\text{flow f. If no b}}\_{\text{flow exists, return(null);}}$
  ${\text{while }}\varepsilon \geq {\frac {1}{n}}{\text{ do }}$
    $\varepsilon :={\frac {\varepsilon }{\alpha }}$
    ${\text{refine}}(\varepsilon ,f,\pi )$
  ${\text{end;}}$
  ${\text{return}}(f);$
${\text{end;}}$

این روال دستوری( مجموعه کد) به صورت زیر اجرا می‌شود:
ابتدا مقدار ممکن ماکسیموم از رونددر طول همهٔ یال‌ها با هزینه کاهش یافته منفی هل داده می‌شود. این نتیجه یک روند $b'$ بهینه برای بعضی $b'$‌ها است. یک راس فعال نامیده می‌شود اگر اضافی باشد.
$e_{f}(v):=b(v)-\sum _{e\in {}_{G}^{+}\delta (v)}f(e)+\sum _{e\in {}_{G}^{-}\delta (v)}f(e)$ تا زمانی که حتی یک راس فعال وجود داشته باشد، چه relabel یا چه push، به جای راس فعال اجرا می‌شود.

${\text{procedure }}refine(\varepsilon ,f,\pi )$
${\text{begin}}$
  ${\text{for }}e\in E({}_{f}^{\pi }G){\text{do push}}(e,u_{f}(e));$
  ${\text{while there exists an active vertex do}}$
  ${\text{begin}}$
    ${\text{choose an active vertex}}v$
    ${\text{if }}{}_{f}^{\pi }G{\text{ contains an edge }}e=(v,w){\text{ then}}$
      ${\text{push}}(e,min(u_{f}(e),e_{f}(v)));$
    ${\text{else}}$
      ${\text{relabel(v)}}$
    ${\text{end;}}$
 ${\text{end;}}$

${\text{procedure push}}(e,\delta )$
${\text{begin}}$
  ${\text{if }}e=(v,w)\in E(G){\text{ then}}$
    ${\text{increase }}f=(e){\text{ by }}\delta ;$
  ${\text{else}}$
    ${\text{decrease }}f(\leftarrow e){\text{ by }}\delta ;$
${\text{end;}}$

${\text{procedure }}relabel(v)$
${\text{begin}}$
  ${\text{replace }}\pi (v){\text{ by }}max_{(v,w)\in E(G_{f})}(\pi (w)-c(v,w)-\varepsilon );$
 ${\text{end;}}$

هر اجرای refine، $O(n^{2})$ عمل relabel و $O(n^{2}m)$. عمل push استفاده می‌کند که $n:=|V(G)|$ و $m:=|E(G)|$. اثبات این موارد قبلاً ذکر شده‌است. ملاحظه می‌کنیم که به‌طور تئوری زمان refine را می‌توان با استفاده از درخت‌های پویا به $O\left(nm\log({\frac {n^{2}}{m}})\right)$ بهبود داد.
برای محاسبه روند $b$ اولیه، الگوریتم روند ماکسیموم گولدبرگ و تارجان استفاده می‌شود. در آزمایش‌های ما فقط بخش کوچکی از زمان اجرا برای این قدم اولیه مصرف شد.

جنبه‌های پیاده سازی

تصمیم اولیه در هنگام پیاده‌سازی الگوریتم فوق مربوط به گراف باقی مانده‌ای است: لازم نیست که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم. اما اگر بدون ذخیره‌سازی عمل شود، لازم است تمام یال‌های همسایهٔ یک راس فعال چک شود قبل از این کع بتوان آن را relabel کرد. این کار بسیار پر هزینه است. لذا تصمیم گرفتیم که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم به وجودی که لازم است بعد از هر عمل push آن را به روز کنیم.
ظرفیت باقی مانده‌ای ذخیره و در هر یال به روز می‌شود. در نتیجه نیازی به ذخیره روند نیست. در حقیقت روند به‌طور صریح مورد نیاز نیست مگر در زمان باز گرداندن خروجی بعد از پایان الگوریتم. برای هر راس $v$،افزونگی $e_{f}(v)$ و $\pi (v)$ احتمالی ذخیره می‌شود. هزینه‌های کاهش یافته به‌طور صریح ذخیره نمی‌شوند چون مشخص گردید که به صرفه تر است که هر گاه که مورد نیاز بودند مجدداً محاسبه شوند. برای هر راس لیستی از یال‌های خارج شونده با ظرفیت باقی مانده‌ای مثبت موجود است. اشاره‌گری داریم که برای هر راس فعال عنصر جاری در این لیست را نشانه‌گذاری می‌کند. هرگاه یک push یال جاری را اشباح کند( یا وقتی که الگوریتم مشخص می‌کند که یال جاری دارای هزینه کاهش یافته غیر منفی است) اشاره گر به جلو حرکت می‌کند. این امر متضمن آن است که یک relabel می‌تواند زمانی که اشاره گر به انتهای لیست می‌رسد انجام پذیرد.
یک امر مهم در پیاده‌سازی انتخاب راس فعال است. با توجه به این که تعداد رأس‌های فعال معمولاً کم است لازم است که ساختمان داده‌ای استفاده شود که مجموعه گره‌های فعال را در بر دارد. ساختمان داده‌های ساده یا یک صف یا یک پشته هستند. راه پیچیده تر عبارت است از ذخیره کردن رأس‌های فعال به صورت یک ترتیب مبتنی بر همبندی نسبت به گراف قابل تصدیق ( که غیر چرخه‌ای است). اما در عمل تعداد عملیات pushو relabel اندکی بزرگتر از حالتی است که از پیاده‌سازی ساده صف استفاده می‌شود. به علاوه انتخاب اولین راس با ترتیب مبتنی بر همبندی پر هزینه تر است حتی موقعی که از کارآمدترین ساختمان داده، دنباله فیبوناچی استفاده شود. با توجه به این ملاحظات تصمیم گرفتیم که رأس‌های فعال را در یک صف ساده ذخیره کنیم. توجه شود که این رویکرد مرز تئوری بر روی تعداد عملیات push را برای هر بار اجرای refine به $O(n^{3})$ کاهش می‌دهد.

مکاشفه ای

پالایش قیمت

رویه refine یک روند $b$ ،$\varepsilon$-بهینه محاسبه می‌کند. از طرفی بسیار اتفاق میافتد که این روند از قبل برای بعضی از $\varepsilon '$ بهینه برای بعضی از $\varepsilon '<\varepsilon$. در این صورت ممکن است بتوانیم از بعضی تکرارها بدون اجرای refine صرف نظر کنیم در نتیجه دو سؤال مطرح می‌شود

1. برای بک روند $b$ به نام $f$ یک $\varepsilon \geq 0$ یک $\pi V(G)\rightarrow R$ بالقوه پیدا می‌کنیم مانند $c_{\pi }(e)\geq =\varepsilon$ برای همه $e\in E(G_{f})$ یا یک $f$ که $\varepsilon$ بهینه نباشد، تعریف می‌شود.
2. برای یک روند $b$ به نام $f$، کوچکترین $\varepsilon \geq 0$ پیدا می‌شود که $\varepsilon$ بهینه است.

اولین مسئله را می‌توان توسط یک محاسبه کوتاه‌ترین مسیر مبدأ واحد در $(G_{f},c')$ حل کرد که $c'$ از روی $c'$ با اضافه کردن $\varepsilon$ به هر وزن یال به دست می‌آیدو گولدبرگ پیشنهاد کرد که محاسبهٔ کوتاهترین مسیر در هر تکرار انجام گیرد یعنی چک شود که آیا روند $b$ جاری بهینه است یا خیر و تنها در صورت منفی بودن جواب refine صدا زده شود. مکاشفهٔ دیگر توسط راه حل مسئله دوم به دست می‌آید. این احتمال گولد برگ و تارجان، و گولدبرگ و همکارانش، مورد اشاره قرار گرفته اما بیشتر دنبال نشده‌است. ملاحظه کنید که $f$ ،$\varepsilon$ بهینه است اگر هیچ مدار جهت دار از مجموع وزن منفی در $(G_{f},c')$ وجود نداشته باشد که در آن $c'(e):=c(e)+\varepsilon$ برای همه ی $e\in E(G_{f})$ . لذا کوچکترین $\varepsilon$ که به ازای آن $\varepsilon$ بهینه می‌شود عبارت است از$-\mu$ که در آن $\mu$ عبارت است از کمترین وزن میانگین مدار جهت دار در $(G_{f},c)$.
لذا مسئله دوم چیری به جز یک مسئله کمترین چرخهٔ میانگین نیست. این مسئله را می‌توان توسط یک الگوریتم پارامتری کوتاه‌ترین مسیر به‌طور بسیار کارآند حل کرد. یک نسخهٔ پایه توسط کارپ و ارلین و اشنایدر توصیف شده و نسخهٔ بهبود یافتهٔ آن توسط تارجان و ارلین بیان شده‌است. یک پیاده‌سازی کارآمد این الگوریتم توسط بوناگل توصیف شده‌است. زمان اجرا در بدترین حالت عبارت است از $O(nm+n^{2}log(n))$.
برای پیاده‌سازی الگوریتم روند کمترین هزینه، ما مسئله دوم را با استفاده از محاسبه پارامتری کوتاه‌ترین مسیر در هر تکرار حل کردیم. کوچکترین $\varepsilon$ که سبب شود روند $b$ جاری $\varepsilon$ بهینه شود را پیدا می‌کنیم و همچنین یک $\pi$ بالقوه مناسب را میابیم. سپس refine را به $f$، $\pi$ و ${\frac {\varepsilon }{\alpha }}$ اعمال می‌کنیم.
این مکاشفه منجر به بهبود قابل ملاحظه‌ای در زمان اجرا شد. در مقایسه با این که توسط یک مخاسبه ساده کوتاه‌ترین مسیر فقط چک شود که آیا روند بهینه است، ما به بهبود زمان اجرا به میزان 40% دست یافتیم.
سؤال دیگر این است که پارامتر $\alpha$ چه طور انتخاب شود. ملاحظات تئوری مقدار 4 را پیشنهاد می‌کند،

پیشگویی push

مکاشفه دیگر به نام پیشگویی push به گولدبرگ منتسب است. هدف آن اجتناب از هل دادن روند از یک راس $v$ به یک همسایه $\alpha$. است اگر این روند در قدم بعد از آن احتمال دارد مجدداً به $v$ هول داده شود. ما الگوریتم را تغییر می‌دهیم و هل دادن را بیش از $A_{f}(w):=max\{0,-e_{f}(w)+\sum u_{f}(e)\}$ واحد از روند به راس $w$ انجام نمی‌دهیم. اگر این عدد مثبت باشد بیانگر تعداد روندهایی است که می‌تواند از $\alpha$، بدون relabeling هل داده شود.
لازم است رویه relabel را گسترش داد. اگر به اندازه $a_{f}(w)<min\{u_{f}(e),e_{f}(v)\}$ واحد از $v$ به $w$ هل داده شود، راس $w$ به عنوان بیش فعال علامت می خورد. پس از آن هیچ روند اضافه‌ای نمی‌تواند به سمت $w$ هل داده شود تا این که $w$، relabel شود. به علاوه قبل از relabel کردن $v$، $w$را نمی‌توان relabel کرد اما اگر $a_{f}(w)<0$، آنگاه پس از آن که تمام هل‌های احتمالی از $w$ انجام گرفته باشد $w$ فعال نخواهد بود. این موضوع نشان می‌دهد که لازم است عمل relabel به رأس‌های بیش فعال گسترش داده شود. مستقل از این که آیا این رأس‌ها فعالند یا خیر.
گولدبرگ و خاریتونوف نیز پیشنهاد می‌دهند که رویه relabel به صورت فوق ذکر به رأس‌های پیش فعال اغمال شود با این فرق که در مواردی که هیچ یال باقی مانده‌ای راس relabel را ترک نمی‌کند، این احتمال به اندازه $\varepsilon$ کاهش یابد. ما رویه relabel متفاوت زیر را پیاده‌سازی کردیم.

${\text{procedure }}relabel(v)$
${\text{begin}}$
  ${\text{if }}f_{f}{v}=0{\text{ then}}$
    ${\text{Decrease }}\pi (v){\text{ by }}\varepsilon ;$
  ${\text{else}}$
    ${\text{replace }}\pi (v){\text{ by }}max_{(v,w)\in E(G_{f})}(\pi (w)-c(v,w)-\varepsilon );$
${\text{end;}}$

دلیل ما برای انتخاب رویه relabel گسترش یافته آن است که نا را قادر می‌سازد که مقدار بیشینه قدر مطلق مقادیر بالقوه را محدود کنیم. این موضوع به دلایل عددی مهم است.
در هنگام بررسی یک راس بیش فعال $v$ امکان دارد راس دیگری مانند $w$ بیش فعال گردد. اگر رأس‌های بیش فعال در داخل یک پشته قرار دهیم و همیشه آخرین راس بیش فعال اضافه شده را در نظر داشته باشیم می‌توان این رأس‌ها را با ترتیب سریع بررسی کرد.( توجه شود که گراف قابل تصدیق فاقد چرخه است). رویه بازگشتی زیر این موضوع را منعکس می‌کند.

${\text{procedure }}refine(\varepsilon ,f,\pi )$
${\text{begin}}$
  ${\text{for }}e\in E({}_{f}^{\pi }G){\text{do push}}(e,u_{f}(e));$
  ${\text{while there exists an active vertex do}}$
  ${\text{begin}}$
    ${\text{choose an active vertex}}v$
    $discharge(v);$
  ${\text{end;}}$
${\text{end;}}$

${\text{procedure }}discharge(e,\delta )$
${\text{begin}}$
  ${\text{while }}e_{f}(v)>0{\text{ or }}v{\text{ is hyperactive do}}$
  ${\text{begin}}$
    ${\text{if }}{}_{f}^{\pi }{\text{contains an edge }}e=(v,w){\text{then}}$
    ${\text{begin}}$
      $push(e,min(u_{f}(e),e_{f}(v),a_{f}(w)));$
      ${\text{if }}a_{f}(w)<min(u_{f}(e),e_{f}(v)){\text{ then}}$
      ${\text{begin}}$
        ${\text{mark }}w{\text{ as hyperactive}}$
        $discharge(w);$
      ${\text{end;}}$
    ${\text{end;}}$
    ${\text{else}}$
    ${\text{begin}}$
      $relabel(v);$
      ${\text{if }}v{\text{ is hyperactive then}}$
      ${\text{begin}}$
        ${\text{mark }}v{\text{ as non-hyperactive}}$
        ${\text{return;}}$
      ${\text{end;}}$
    ${\text{end;}}$
  ${\text{end;}}$
${\text{end;}}$

تعداد عمل‌های relabel که به هر راس اعمال می‌شود را کماکان می‌توان به $(\alpha +1)$ محدود کرد. در عمل تعداد عمل‌های relabel تقریباً ثابت می‌ماند در حالی که تعداد عمل‌های push به اندازه 40-60% کاهش می یابد. به علاوه روند محاسبه شده توسط رویه refine جدید معمولاً بهتر است یعنی برای $\varepsilon '$ کوچکتری $\varepsilon '$-بهینه است. در نتیجه ترکیب با مکاشفه پالایش قیمت توصیف شده در فصل قبل بسیار کارآمد می‌باشد.

برچسب‌گذاری مجدد کردن

سومین کشف مهم عملیات برچسب‌گذاری مجدد را گسترش می‌دهد به‌طوری‌که رأس‌ها ی زیادی در یک مرحله برچسب‌گذاری مجدد می‌شوند. اگر S یک زیرمجموعه از راس‌هایی باشد که شامل همهٔ رأس‌های بیش از حد منفی باشد، متمم v(g)/sحداقل یک راس فعال داردو فرض کنید که در گراف مورد قبول از V (G) / S به Sلبه هم نداریم سپس عملیات برچسب‌گذاری مجدد قابل اجرا است:پتانسیل همهٔ راس‌ها در V (G) / S را می‌توان به اندازه ɛ کاهش داد. مشخص است که این عملیات بهینگی ɛ را در f از بین نمی‌برد. این نظریه که در محدوده اعداد push و عملیات برچسب‌گذاری مجدد است،اگر عملیات برچسب‌گذاری مجدد به کار برده شوند ، تغییر نمی‌کنند و تعداد دفعات ان هم اهمیتی ندارد.(در مثال [2] اثبات شده‌است)

عملیات برچسب‌گذاری مجدد (set_relabel) می‌تواند این‌گونه بازگو شود:

${\text{begin}}$ procedure relabel global(π) begin S := { v∊ V (G) : ef (v) < 0}; while V (G) \ S contains an active vertex do begin Add all vertices to S from which S can be reached in G f; if V (G) \ S contains an active vertex then π(v) := π (v) - ɛ for all v ∊V (G) \ S; end; end;

این روش می‌تواند به صورت کارامدی توسط ساختار سطلی (bucket structure) انجام شود. سطل‌ها با اعداد صحیح نامنفی نشان داده می‌شوند. اولین سطل به شماره B(v) به هر راس v اختصاص داده می‌شود برای اینکه سطل حاوی v یا ∞را (در صورتی‌که v در هیچ‌کدام از سطل‌ها قرار نگرفته باشد) نشان دهد. در نهایت B(v) شماره عملیات برچسب‌گذاری مجدد خواهد شد که برای راس v به کار برده می‌شود. ابتدا همهٔ رأس‌ها ی منفی در سطل با مقدار صفر قرار می‌گیرند و بقیه سطل‌ها خالی می‌مانند. سپس سطل‌ها به این شکل بررسی می‌شوند: برای هر سطل i، به‌طوری‌که i=1,2,…. و هر راس v به صورت B(v) = i و هر لبهٔ e=(w,v)به عنوان عضوی از Gf ، راس w از B(w) حذف می‌شود. اگر k بزرگترین سطل نشان دهنده راس فعال باشد، پتانسیل هر راس v اندازه ɛ کم می‌شودmin(B(v), k). اگر این بعد از هر n بار عملیات عادی برچسب‌گذاری مجدد استفاده شود، بدترین حالت زمان اجرای بهبود بخشیدن تغییر نمی‌کند. تعداد عملیات برچسب‌گذاری مجدد (همان عدد k) در طول برچسب‌گذاری مجدد کلی( (relabel global برابر O(n) است. بنابراین تعداد کل عملیات برچسب‌گذاری مجدد در طول بهبود بخشیدن O(n2) است.

ادعا می‌کنند که هر گره که درGoldberg [6] و GoldbergO(n) سهیم می‌شود، در هر مرحله بهبود بخشی برچسب‌گذاری مجدد می‌شود. هر چند که این، زمانی می‌تواند درست باشد که فقط در هر مرحله بهبود بخشی به اندازه O(n)، برچسب‌گذاری مجدد داشته باشیم. چون در هر برچسب‌گذاری مجدد، راس‌های منزوی شرکت دارند.

به‌طور تجربی، کشف برچسب‌گذاری مجدد ، تعداد عملیات را کاهش می‌دهد . کار اضافه برای روش

برچسب‌گذاری مجددکلی قابل توجه است. اما در اکثر مواقع زمان اجرای کل کاهش می یابد.

5)نتایج تجربی نتایجی روی IBMRS/6000Mod .550 workstations. به دست آمده‌است ، با دو ویژگی سر وکار داریم: اولین گروه توسط NETGEN تولید می‌شوند٫ابزاریست که توسط Klingmanو Napier توسعه داده شده‌است. ابتدا یک مولد، منبعی را تولید می‌کند و سپس یک شبکه یدک شامل لبه‌های با ظرفیت بالا را می‌سازد برای اینکه از امکان ان اطمینان حاصل شود. سپس لبه هارا به صورت رندم اضافه می‌کند. گروه شامل 35 شبکه با 200 تا 8000 راس است. دومین گروه شامل مشکلات ناشی از فاز دادن در طرح VLSI است. این شبکه ها خیلی پراکنده‌اند. تعداد لبه‌ها فقط 2-3برابر تعداد رأس‌ها است. گروه شامل 570 شبکه است. تعداد رأس‌ها بین 10 تا 1000 است. چون تفاوت‌های ناچیزی در نتایج محاسبه شده بین دو کلاس داریم، باید خودمان را به حالت دوم محدود کنیم چون حالت اول مشکلات بیشتری دارد. محاسبه اولیه در الگوریتم Goldberg و Tarjan در اکثر مواقع کمتر از %1 از زمان اجرای کل است. اجرای این اکتشاف‌ها برای اینکه الگوریتم Goldberg-Tarjan رقابتی شوند بسیار مفید است. با این کشفیات کوتاه‌ترین مسیر الگوریتم موفق به دست می اید. به هر حال ما باید بیان کنیم که نمونه‌هایی هم داریم که از مسیرهای کوتاه الگوریتم Goldberg-Tarjan بهتر است. هر اکتشافی پیشرفت قابل توجهی از تعداد عملیات برچسب‌گذاری مجدد و pushرا می‌دهد و زمان اجرا به وضوح به این عملیات‌ها بستگی دارد. کشف push-look-ahead اثر قابل توجهی روی تعداد عملیات push دارد:وقتی در الگوریتم پایه این تعداد تقریباً دوبرابرتعداد عملیات برچسب‌گذاری مجدد است، فرکانس هر دو عملیات هنگام استفاده از push-look-ahead برابر می‌شود. استفاده زیاد از برچسب‌گذاری مجدد می‌تواند زمان اجرا را برای اعداد بزرگ کاهش دهد (n> 1000). برچسب‌گذاری مجدد از بقیه کم اهمیت تر است اما مواردی هست که با عدم استفاده از هر یک از کشفیات می‌توان زمان اجرا را بسیار بالاتر برد.

پانویس

منابع

منابع

[1] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin (1993) Network Flows. Prentice Hall, Engelwood Cli_s

[2] U. Bunnagel (1998) E_ziente Implementierung von Netzwerkalgorithmen. Diploma thesis, University of Bonn

[3] R.G. Busacker, and P.J. Gowen (1961) A Procedure for Determining a Family of Minimum-Cost Network Flow Patterns. O.R.O. Technical Paper 15

[4] J. Edmonds, and R.M. Karp (1972) Theoretical Improvements in Algorithmic E_- ciency for Network Flow Problems. Journal of the ACM 19, 248-264

[5] M.L. Fredman, and R.E. Tarjan (1987) Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34, 596-615

[6] A.V. Goldberg (1992) An E_cient Implementation of a scaling Minimum{Cost Flow Algorithm. Departement of Computer Science, Stanford University, August 1992; NEC Research Institute, Princeton, October 1992; Journal of Algorithms 22 (1997), 1-29

[7] A.V. Goldberg, and M. Kharitonov (1993) On Implementing Scaling Push-Relabel Algorithms for the Minimum-Cost Flow Problem. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, 157-198

[8] A.V. Goldberg, and R.E. Tarjan (1988) A New Approach to the Maximum Flow Problem. Journal of the ACM 35, 921-940

[9] A.V. Goldberg, and R.E. Tarjan (1990) Finding Minimum{Cost Circulations by Successive Approximation. Mathematics of Operations Research 15, 430-466

[10] A.V. Goldberg, _E. Tardos, and R.E. Tarjan (1990) Network Flow Algorithms. In: B. Korte, L. Lov_asz, H. J. Promel, A. Schrijver (eds.): Flows, Paths and VLSI Layout, Springer, Berlin, 101-164

[11] M. Iri (1960) A New Method for Solving Transportation-Network Problems. Journal of the Operations Research Society of Japan 3, 27-87

[12] W.S. Jewell (1958) Optimal Flow through Networks. Interim Technical Report 8, MIT