الگوریتم Goldberg و Tarjan

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

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

تعریف 5: فرض کنید که هزینه متوسط دور  برابر با  باشد که
 هزینه دور و  تعداد یال‌های موجود در  است.
تعریف 6: فرض کنید گردش   داده شده باشد و  هزینه دور با کمترین هزینه متوسط باشد.
می توان با حذف دور با کمترین هزینه مینیمم، یک الگوریتم چندجمله‌ای به دست آورد. اکنون می‌توانیم الگوریتم زیر را بیان کنیم.
فرض کنید  یک گردش باشد
تا زمانی که 
     دور  با کمترین هزینه متوسط را حذف کن.  را به روز رسانی کن.
شرط  معادل داشتن یک دور با هزینه منفی در  است. برای داشتن یک الگوریتم با زمان چندجمله‌ای، باید بتوانیم دور با هزینه متوسط کمینه را در زمان چندجمله‌ای پیدا کنیم.
برای تحلیل الگوریتم فوق، تعدادی اصطلاح را تعریف می‌کنیم.
تعریف7: یک گردش ، -بهینه است اگر تابع پتانسیل  موجود باشد که برای هر   داشته باشیم 
واضح است که ، 0-بهینه است؛ اگر و تنها اگر  یک گردش با کمترین هزینه باشد. برای هر گردش،
، -بهینه است. زیرا اگر برای هر  قرار دهیم ؛ برای هر
 داریم .
تعریف 8:  کمترین  است که ، - بهینه باشد.
دو مقدار  و  به شکل جالبی به هم مرتبطند.
تئوری 2: برای یک گردش  داریم: 
اثبات: ابتدا نشان می‌دهیم .
چون
با جمع کردن روی تمام یال‌های هر دور  می‌بینیم که
. بنابراین برای دور با هزینه متوسط کمینه  داریم:
حال نشان می‌دهیم که .
قرار می‌دهیم . آنگاه برای هر دور در  داریم:
راس  را به گراف اضافه کرده و و آن را به همه رئوس ، با یال‌هایی به وزن  وصل می‌کنیم. پتانسیل  را برای گره  به صورت طول کوتاه‌ترین مسیر از  به  با استفاده از هزینه‌های  تعریف می‌کنیم. با استفاده از تعریف کوتاهترین مسیر داریم:
که نتیجه می‌دهد:
این بدان معنی است که ، - بهینه است. بنابراین 
فرض کنید گردش  داده شده باشد و  گردش به دست آمده بعد از  بار تکرار الگوریتم حذف دور با کمترین هزینه متوسط روی  باشد. تئوری زیر ثابت می‌کند که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای اجرا می‌شود.
تئوری3: 
تئوری4: 
که  و  تعداد یال‌ها و گره‌ها در گراف هستند.
تئوری5: اگر  گردش  بهینه است.
اثبات: این حقیقت که  نشان می‌دهد که پتانسیل  موجود است که
. بنابراین برای هر دور . با توجه به صحیح بودن هزینه‌ها داریم؛ 
حال با توجه به سه نتیجه قبل ثابت می‌کنیم که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای بر حسب اندازه ورودی، خاتمه می یابد.
تئوری6: الگوریتم حذف دور با کمترین هزینه متوسط Goldberg-Tarjan، به حداکثر  تکرار نیاز دارد.
اثبات: هر گردش اولیه C- بهینه است. بعد از  تکرار، با توجه به اینکه
، داریم:
اگر محاسبه دور با هزینه متوسط کمینه، زمانی برابر  داشته باشد، زمان اجرای الگوریتم Goldberg-tarjan برابر
 خواهد بود. البته توجه داشته باشید که این الگوریتم کاملاً چندجمله‌ای نیست.
اثبات تئوری 3: می‌دانیم پتانسیل  موجود است که:
به علاوه، . برای دور  با کمترین هزینه متوسط، چون
، نتیجه می‌گیریم که
. حال ادعا می‌کنیم که
. داریم ، اگر
 یا . در حالت اول، . در حالت دوم، . در هر دو حالت، ،
 -بهینه است و تئوری ثابت می‌شود.
اثبات تئوری4: می‌دانیم پتانسیل  موجود است که
. فرض کنید در تکرار ، دور  را حذف می‌کنیم که در آن،
. آنگاه
بنابراین
حذف دور، یک یال با  را از گراف باقی‌مانده حذف و تنها یال‌هایی با  را ایجاد می‌کند. بنابراین برای حذف چنین یالی به بیش از  تکرار نیاز نیست.
انتزاعی

الگوریتم هزینه پیمایش گولد برگ (Goldberg) و تارجان(Tarjan)، یکی

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

مقدمه

فرض می‌کنیم با تئوری روند شبکه آشنایی داریم و نتایج و نشان‌گذاری استاندارد را استفاده می‌کنیم.
برای مثال آهوجا(Ahuja)، مگنانتی(Magnanti)،ارلین(Orlin)را  ببینید. در اینجا فقط مهمترین‌ها را ذکر می‌کنیم. مسئله روند کمترین هزینه به این صورت تعریف می‌شود: گراف جهتدار  با گنجایش  داده شده‌است:  ، سنگینی   و ارزش تعادل ،  را به عنوان یک روند کمترین روند هزینه بیابید، به‌طوری‌که تابع  با  برای همهٔ ‌های عضو  و برای همهٔ ‌های عضو  از قبیل  که کمترین مقدار یا همان مینیموم می‌باشد مجموعه‌ای از ورودی‌های را تشکیل می‌دهد. راس  باقی می‌ماند.

واضح است که امکان وجود روند کمترین هزینهٔ مسائل، می‌تواند در برابر محاسبه روند ماکسیموم چک شود ( و در بهترین شرایط روند  می‌تواند پیدا شود). مسائل روند ماکسیموم آسانترند و خیلی سریعتر از مسائل روند کمترین  هزینه حل می‌شوند.

نمونه داده شده  از مسئله روند کمترین هزینه و روند
 با  برای همهٔ ، ظرفیت باقی‌ماندهٔ یال  به وسیله  تعریف می‌شود.

علاوه بر این، ما یک یال جدید   از  به   برای هر یال
 در نظر گرفته ایم و  و
 تعریف کرده ایم. باقی‌مانده گراف  شامل همه بال‌ها ( قدیمی و جدید) با ظرفیت باقی‌مانده مثبت می‌باشد. معروف است که روند  از  بهینه است( کمترین هزینه را دارد) اگر و تنها اگر هیچ جریان مستقیم در  وزن منفی نداشته باشد.

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

روند داده شده با  و ذخیره
، یک گراف مجاز تعریف می‌کنیم که تمام یال‌های  که هزینهٔ کاهش یافته منفی را دارند، در بر بگیرد. گراف مجاز را با  معنی می‌کنیم. اگر  یک روند  بهینه باشد( برای بعضی از ها) و
 یک ذخیره امکانپذیر در  باشد، پس   مارپیچ است.

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

یک روند ،  -بهینه نامیده می‌شود اگر یک ذخیره  مانند  برای همهٔ . پس بهینه 0 هیچ چیز نیست ولی بهینه است. الگوریتم هزینه پیمایش گولبرگ و تارجان  یک روند  را محاسبه می‌کند که بهینه  برای بعضی از ‌های بزرگ است. پس مقدار  را در هر تکرار، نگهداری کردن و بهینگی ، کاهش می‌دهد.

ساده است که هر روند ، بهینه  است اگر
 . علاوه بر این، از دید هزینه‌های  انتگرال، هر روند -بهینه با ، بهینه است.
پس ساختار جهانی این الگوریتم، به صورت زیر است.

( یک پارامتر ثابت است و حداقل مقدار آن 2 می‌باشد)

  
  
  
    
    
  
  
این روال دستوری( مجموعه کد) به صورت زیر اجرا می‌شود:

ابتدا مقدار ممکن ماکسیموم از رونددر طول همهٔ یال‌ها با هزینه کاهش یافته منفی هل داده می‌شود. این نتیجه یک روند  بهینه برای بعضی ‌ها است. یک راس فعال نامیده می‌شود اگر اضافی باشد.

تا زمانی که حتی یک راس فعال وجود داشته باشد، چه relabel یا چه push، به جای راس فعال اجرا می‌شود.

  
  
  
    
    
      
    
      
    
 
  
    
  
    
  
 
هر اجرای refine،  عمل relabel و . عمل push استفاده می‌کند که  و . اثبات این موارد قبلاً ذکر شده‌است.
 ملاحظه می‌کنیم که به‌طور تئوری زمان refine را می‌توان با استفاده از درخت‌های پویا به  بهبود داد.

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

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

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

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

یک امر مهم در پیاده‌سازی انتخاب راس فعال است. با توجه به این که تعداد رأس‌های فعال معمولاً کم است لازم است که ساختمان داده‌ای استفاده شود که مجموعه گره‌های فعال را در بر دارد. ساختمان داده‌های ساده یا یک صف یا یک پشته هستند. راه پیچیده تر عبارت است از ذخیره کردن رأس‌های فعال به صورت یک ترتیب مبتنی بر همبندی نسبت به گراف قابل تصدیق ( که غیر چرخه‌ای است). اما در عمل تعداد عملیات pushو relabel اندکی بزرگتر از حالتی است که از پیاده‌سازی ساده صف استفاده می‌شود. به علاوه انتخاب اولین راس با ترتیب مبتنی بر همبندی پر هزینه تر است حتی موقعی که از کارآمدترین ساختمان داده، دنباله فیبوناچی استفاده شود. با توجه به این ملاحظات تصمیم گرفتیم که رأس‌های فعال را در یک صف ساده ذخیره کنیم. توجه شود که این رویکرد مرز تئوری بر روی تعداد عملیات push را برای هر بار اجرای refine به  کاهش می‌دهد.

پیشگویی push

مکاشفه دیگر به نام پیشگویی push به گولدبرگ منتسب است. هدف آن اجتناب از هل دادن روند از یک راس  به یک همسایه . است اگر این روند در قدم بعد از آن احتمال دارد مجدداً به  هول داده شود. ما الگوریتم را تغییر می‌دهیم و هل دادن را بیش از  واحد از روند به راس  انجام نمی‌دهیم. اگر این عدد مثبت باشد بیانگر تعداد روندهایی است که می‌تواند از ، بدون relabeling هل داده شود.

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

گولدبرگ و خاریتونوف نیز پیشنهاد می‌دهند که رویه relabel به صورت فوق ذکر به رأس‌های پیش فعال اغمال شود با این فرق که در مواردی که هیچ یال باقی مانده‌ای راس relabel را ترک نمی‌کند، این احتمال به اندازه  کاهش یابد. ما رویه relabel  متفاوت زیر را پیاده‌سازی کردیم.

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

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

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

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

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

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).
برچسب‌گذاری مجدد  از بقیه کم اهمیت تر است اما مواردی هست که با عدم استفاده از هر یک از کشفیات می‌توان زمان اجرا را بسیار بالاتر برد.