الگوریتم Goldberg و Tarjan کیست؟ توضیح بده.
فرض می‌کنیم با تئوری روند شبکه آشنایی داریم و نتایج و نشان‌گذاری استاندارد را استفاده می‌کنیم.برای مثال آهوجا(Ahuja)، مگنانتی(Magnanti)،ارلین(Orlin)را ببینید. در اینجا فقط مهمترین‌ها را ذکر می‌کنیم. مسئله روند کمترین هزینه به این صورت تعریف می‌شود: گراف جهت دار formula_1 با گنجایش formula_2 داده شده‌است: formula_3 ، سنگینی formula_4 و ارزش تعادل formula_5، formula_6 را به عنوان یک روند کمترین روند هزینه بیابید، به‌طوری‌که تابع formula_7 با formula_8 برای همهٔ formula_9‌های عضو formula_10 و formula_11برای همهٔ formula_12‌های عضو formula_13 از قبیل formula_14 که کمترین مقدار یا همان مینیموم می‌باشد formula_15مجموعه‌ای از ورودی‌های را تشکیل می‌دهد. راس formula_12 باقی می‌ماند.واضح است که امکان وجود روند کمترین هزینهٔ مسائل، می‌تواند در برابر محاسبه روند ماکسیموم چک شود ( و در بهترین شرایط روند formula_6 می‌تواند پیدا شود). مسائل روند ماکسیموم آسانترند و خیلی سریعتر از مسائل روند کمترین هزینه حل می‌شوند.نمونه داده شده formula_18 از مسئله روند کمترین هزینه و روندformula_7 با formula_20 برای همهٔ formula_21، ظرفیت باقی‌ماندهٔ یال formula_21 به وسیله formula_23 تعریف می‌شود.علاوه بر این، ما یک یال جدید formula_9 از formula_25 به formula_12 برای هر یالformula_27 در نظر گرفته ایم و formula_28 وformula_29 تعریف کرده ایم. باقی‌مانده گراف formula_30 شامل همه بال‌ها ( قدیمی و جدید) با ظرفیت باقی‌مانده مثبت می‌باشد. معروف است که روند formula_6 از formula_32 بهینه است( کمترین هزینه را دارد) اگر و تنها اگر هیچ جریان مستقیم در formula_30 وزن منفی نداشته باشد.دیاگراف formula_1 داده شده با وزن formula_4، یک ذخیره امکانپذیر در formula_36 است، تابع formula_37 به این صورت که هزینه کاهش یافته formula_38 است که برای هر formula_9 نامنفی عبارت formula_40 برقرار است. یک ذخیره امکانپذیر وجود دارد اگر و تنها اگر هیچ جریان مستقیمی، وزن کل منفی نداشته باشد. این توسط کوتاه‌ترین راه محاسبه منبع واحد قطعی و تصمیم گرفته می‌شود.روند داده شدهformula_41 با formula_20 و ذخیرهformula_43، یک گراف مجاز تعریف می‌کنیم که تمام یال‌های formula_30 که هزینهٔ کاهش یافته منفی را دارند، در بر بگیرد. گراف مجاز را با formula_45 معنی می‌کنیم. اگر formula_32 یک روند formula_6 بهینه باشد( برای بعضی از formula_6ها) وformula_49 یک ذخیره امکانپذیر در formula_30 باشد، پس مارپیچ است.1- مسئله گردش با کمترین هزینه.ورودی‌های مسئله عبارتند از:هدف: یافته جریان formula_55 است کهformula_56را مینیمم می‌کند به‌طوری که:formula_57formula_58تعریف 1: یک گردش formula_32 شرایط زیر را ارضا می‌کند.در این تعریف جدید، جریان در قوس اولیه formula_63 شرط formula_64 را ارضا می‌کند و هر واحد جریان هزینه formula_65 را تحمیل می‌کند. جریان در قوس معکوس formula_66 شرط formula_67 را ارضا کرده و هزینه formula_68 را برای هر واحد جریان تحمیل می‌کند. هزینه کل برای دو یال با جریانformula_32 برابر formula_70 است. بنابراین بهینه‌سازی هزینه کل برای این گراف جدید معادل بهینه‌سازی هزینه کل برای گراف اولیه است.برای یک جریان formula_32 در گراف formula_1 گراف باقی‌مانده formula_73 را گرافی تعریف می‌کنیم که مجموعه یال‌های آن عبارتند از:formula_74کران بالای formula_75 را برای یال formula_76 تعریف می‌کنیم. واضح است کهformula_77تعریف 2: یک پتانسیل تابعی است به صورت formula_78تعریف 3: فرض کنید تابع پتانسیل formula_79 داده شده‌است. هزینه کاهش یافته را به صورت زیر تعریف می‌کنیم:formula_80آنگاه داریم:&lt;br&gt;formula_81تعریف 4: هزینه یک دور formula_82 برابر است با:formula_83تئوری 1: موارد زیر با هم معادلند.2- الگوریتم حذف یک دور.تئوری فوق منجر به الگوریتمی برای محاسبه گردش با کمترین هزینه می‌شود. این الگوریتم به صورت زیر است.فرض کنید که formula_32 یک گردش شدنی باشد.تا وقتی که formula_89 شامل دور منفی formula_82 است.formula_82 را حذف کرده و formula_32 را به روز رسانی کن.صحت الگوریتم فوق از تئوری بالا نتیجه می‌شود. اگر هزینه‌ها و ظرفیت‌ها، هر دو صحیح باشند، جریان بهینه formula_32 موجود است به نحوی که formula_63 برای هر formula_95 صحیح است. فرض کنید:formula_96formula_97بنابراین هر گردش شدنی دارای هزینه حداکثری formula_98 و هزینه حداقلی formula_99 است. چون حذف یک دور، هزینه گردش را حداقل به اندازه یک واحد کاهش می‌دهد، برای یافتن یک گردش بهینه به حداکثر formula_100 حذف نیاز است.برای رسیدن به این نتیجه‌گیری که الگوریتم فوق شبه چندجمله‌ای است، به دو مورد زیر نیاز داریم.3- حذف دور با کمترین هزینه متوسط.با انتخاب مناسب دوری که در هر مرحله تکرار الگوریتم باید حذف شود، می‌توان یک الگوریتم با زمان چندجمله‌ای به دست آورد.تعریف 5: فرض کنید که هزینه متوسط دور formula_82 برابر با formula_104 باشد کهformula_105 هزینه دور و formula_106 تعداد یال‌های موجود در formula_82 است.تعریف 6: فرض کنید گردش formula_32 داده شده باشد و formula_109 هزینه دور با کمترین هزینه متوسط باشد.formula_110می توان با حذف دور با کمترین هزینه مینیمم، یک الگوریتم چندجمله‌ای به دست آورد. اکنون می‌توانیم الگوریتم زیر را بیان کنیم.فرض کنید formula_32 یک گردش باشدتا زمانی که formula_112دور formula_82 با کمترین هزینه متوسط را حذف کن. formula_32 را به روز رسانی کنشرط formula_112 معادل داشتن یک دور با هزینه منفی در formula_89 است. برای داشتن یک الگوریتم با زمان چندجمله‌ای، باید بتوانیم دور با هزینه متوسط کمینه را در زمان چندجمله‌ای پیدا کنیم.برای تحلیل الگوریتم فوق، تعدادی اصطلاح را تعریف می‌کنیم.تعریف7: یک گردش formula_32، formula_118-بهینه است اگر تابع پتانسیل formula_79 موجود باشد که برای هر formula_76 داشته باشیم formula_121واضح است که formula_32، 0-بهینه است؛ اگر و تنها اگر formula_32 یک گردش با کمترین هزینه باشد. برای هر گردش،formula_32، formula_125-بهینه است. زیرا اگر برای هر formula_126 قرار دهیم formula_127؛ برای هرformula_76 داریم formula_129.تعریف 8: formula_130 کمترین formula_118 است که formula_32، formula_118- بهینه باشد.دو مقدار formula_130 و formula_109 به شکل جالبی به هم مرتبطند.تئوری 2: برای یک گردش formula_32 داریم: formula_137&lt;br&gt;اثبات: ابتدا نشان می‌دهیم formula_138.چونformula_139با جمع کردن روی تمام یال‌های هر دور formula_82 می‌بینیم کهformula_141. بنابراین برای دور با هزینه متوسط کمینه formula_82 داریم:formula_143حال نشان می‌دهیم که formula_144.قرار می‌دهیم formula_145. آنگاه برای هر دورformula_82 در formula_89 داریم:formula_148راس formula_149 را به گراف اضافه کرده و و آن را به همه رئوس formula_150، با یال‌هایی به وزن formula_151 وصل می‌کنیم. پتانسیل formula_152 را برای گره formula_150 به صورت طول کوتاه‌ترین مسیر از formula_149 به formula_150 با استفاده از هزینه‌های formula_156 تعریف می‌کنیم. با استفاده از تعریف کوتاهترین مسیر داریم:formula_157که نتیجه می‌دهد:formula_158این بدان معنی است که formula_32، formula_160- بهینه است. بنابراین formula_161فرض کنید گردش formula_32 داده شده باشد و formula_163 گردش به دست آمده بعد از formula_164 بار تکرار الگوریتم حذف دور با کمترین هزینه متوسط روی formula_32 باشد. تئوری زیر ثابت می‌کند که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای اجرا می‌شود.تئوری3: formula_166تئوری4: formula_167که formula_168 و formula_169 تعداد یال‌ها و گره‌ها در گراف هستند.تئوری5: اگر formula_170 گردش formula_32 بهینه است.اثبات: این حقیقت که formula_172 نشان می‌دهد که پتانسیل formula_79 موجود است کهformula_174. بنابراین برای هر دور formula_175. با توجه به صحیح بودن هزینه‌ها داریم؛ formula_176حال با توجه به سه نتیجه قبل ثابت می‌کنیم که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای بر حسب اندازه ورودی، خاتمه می یابد.تئوری6: الگوریتم حذف دور با کمترین هزینه متوسط Goldberg-Tarjan، به حداکثر formula_177 تکرار نیاز دارد.اثبات: هر گردش اولیه C- بهینه است. بعد از formula_178 تکرار، با توجه به اینکهformula_179، داریم:formula_180اگر محاسبه دور با هزینه متوسط کمینه، زمانی برابر formula_101 داشته باشد، زمان اجرای الگوریتم Goldberg-tarjan برابرformula_182 خواهد بود. البته توجه داشته باشید که این الگوریتم کاملاً چندجمله‌ای نیست.اثبات تئوری 3: می‌دانیم پتانسیل formula_79 موجود است که:formula_184به علاوه، formula_137. برای دور formula_82 با کمترین هزینه متوسط، چونformula_187، نتیجه می‌گیریم کهformula_188. حال ادعا می‌کنیم کهformula_189. داریم formula_190، اگرformula_191 یا formula_192. در حالت اول، formula_193. در حالت دوم، formula_194. در هر دو حالت، formula_195،formula_130 -بهینه است و تئوری ثابت می‌شود.اثبات تئوری4: می‌دانیم پتانسیل formula_79 موجود است کهformula_184. فرض کنید در تکرار formula_164، دور formula_82 را حذف می‌کنیم که در آن،formula_201. آنگاهformula_202بنابراینformula_203حذف دور، یک یال با formula_204 را از گراف باقی‌مانده حذف و تنها یال‌هایی با formula_205 را ایجاد می‌کند. بنابراین برای حذف چنین یالی به بیش از formula_168 تکرار نیاز نیست.انتزاعیالگوریتم هزینه پیمایش گولد برگ (Goldberg) و تارجان(Tarjan)، یکی از کارآمدترین الگوریتم‌ها، برای روند کمترین هزینهٔ مسائل، شناخته شده‌است. اگر چه بازده آن در عمل، به بسیاری از جوانب اجرا بستگی دارد. علاوه بر این، گنجایش بسیاری از ابتکارات، کارایی آن را شدیدا بهبود می‌بخشد. در این مقاله به شرح جوانب اجرا و کارآمدترین ابتکارات، می پردازیم. همچنین، نتایج تجربی، اثر ابتکارات مختلف ترکیبی را پررنگ می‌کند.الگوریتم گولبرگ و تارجان.یک روند formula_6، formula_118 -بهینه نامیده می‌شود اگر یک ذخیره formula_37 مانند formula_210 برای همهٔ formula_211. پس بهینه 0 هیچ چیز نیست ولی بهینه است. الگوریتم هزینه پیمایش گولبرگ و تارجان یک روند formula_6 را محاسبه می‌کند که بهینه formula_118 برای بعضی از formula_118‌های بزرگ است. پس مقدار formula_118 را در هر تکرار، نگهداری کردن و بهینگی formula_118، کاهش می‌دهد.ساده است که هر روند formula_6، بهینه formula_118 است اگرformula_219 . علاوه بر این، از دید هزینه‌های انتگرال، هر روند formula_118-بهینه با formula_221، بهینه است.پس ساختار جهانی این الگوریتم، به صورت زیر است.&lt;br&gt; formula_223 formula_224 formula_225 formula_226 formula_227 formula_228 formula_229 formula_230 formula_231 formula_230این روال دستوری( مجموعه کد) به صورت زیر اجرا می‌شود:ابتدا مقدار ممکن ماکسیموم از رونددر طول همهٔ یال‌ها با هزینه کاهش یافته منفی هل داده می‌شود. این نتیجه یک روند formula_233 بهینه برای بعضی formula_233‌ها است. یک راس فعال نامیده می‌شود اگر اضافی باشد.formula_235تا زمانی که حتی یک راس فعال وجود داشته باشد، چه relabel یا چه push، به جای راس فعال اجرا می‌شود. formula_236 formula_224 formula_238 formula_239 formula_224 formula_241 formula_242 formula_243 formula_244 formula_245 formula_230 formula_230 formula_248 formula_224 formula_250 formula_251 formula_244 formula_253 formula_230 formula_255 formula_224 formula_257 formula_230هر اجرای refine، formula_259 عمل relabel و formula_260. عمل push استفاده می‌کند که formula_261 و formula_262. اثبات این موارد قبلاً ذکر شده‌است. ملاحظه می‌کنیم که به‌طور تئوری زمان refine را می‌توان با استفاده از درخت‌های پویا به formula_263 بهبود داد.برای محاسبه روند formula_6 اولیه، الگوریتم روند ماکسیموم گولدبرگ و تارجان استفاده می‌شود. در آزمایش‌های ما فقط بخش کوچکی از زمان اجرا برای این قدم اولیه مصرف شد.جنبه‌های پیاده سازی.تصمیم اولیه در هنگام پیاده‌سازی الگوریتم فوق مربوط به گراف باقی مانده‌ای است: لازم نیست که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم. اما اگر بدون ذخیره‌سازی عمل شود، لازم است تمام یال‌های همسایهٔ یک راس فعال چک شود قبل از این که بتوان آن را relabel کرد. این کار بسیار پر هزینه است. لذا تصمیم گرفتیم که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم به وجودی که لازم است بعد از هر عمل push آن را به روز کنیم.ظرفیت باقی مانده‌ای ذخیره و در هر یال به روز می‌شود. در نتیجه نیازی به ذخیره روند نیست. در حقیقت روند به‌طور صریح مورد نیاز نیست مگر در زمان باز گرداندن خروجی بعد از پایان الگوریتم. برای هر راس formula_12،افزونگی formula_266 وformula_267 احتمالی ذخیره می‌شود. هزینه‌های کاهش یافته به‌طور صریح ذخیره نمی‌شوند چون مشخص گردید که به صرفه تر است که هر گاه که مورد نیاز بودند مجدداً محاسبه شوند. برای هر راس لیستی از یال‌های خارج شونده با ظرفیت باقی مانده‌ای مثبت موجود است. اشاره‌گری داریم که برای هر راس فعال عنصر جاری در این لیست را نشانه‌گذاری می‌کند. هرگاه یک push یال جاری را اشباح کند( یا وقتی که الگوریتم مشخص می‌کند که یال جاری دارای هزینه کاهش یافته غیر منفی است) اشاره گر به جلو حرکت می‌کند. این امر متضمن آن است که یک relabel می‌تواند زمانی که اشاره گر به انتهای لیست می‌رسد انجام پذیرد.یک امر مهم در پیاده‌سازی انتخاب راس فعال است. با توجه به این که تعداد رأس‌های فعال معمولاً کم است لازم است که ساختمان داده‌ای استفاده شود که مجموعه گره‌های فعال را در بر دارد. ساختمان داده‌های ساده یا یک صف یا یک پشته هستند. راه پیچیده تر عبارت است از ذخیره کردن رأس‌های فعال به صورت یک ترتیب مبتنی بر همبندی نسبت به گراف قابل تصدیق ( که غیر چرخه‌ای است). اما در عمل تعداد عملیات pushو relabel اندکی بزرگتر از حالتی است که از پیاده‌سازی ساده صف استفاده می‌شود. به علاوه انتخاب اولین راس با ترتیب مبتنی بر همبندی پر هزینه تر است حتی موقعی که از کارآمدترین ساختمان داده، دنباله فیبوناچی استفاده شود. با توجه به این ملاحظات تصمیم گرفتیم که رأس‌های فعال را در یک صف ساده ذخیره کنیم. توجه شود که این رویکرد مرز تئوری بر روی تعداد عملیات push را برای هر بار اجرای refine به formula_268 کاهش می‌دهد.مکاشفه ای.پالایش قیمت.رویه refine یک روند formula_6 ،formula_118-بهینه محاسبه می‌کند. از طرفی بسیار اتفاق میافتد که این روند از قبل برای بعضی از formula_271 بهینه برای بعضی از formula_272. در این صورت ممکن است بتوانیم از بعضی تکرارها بدون اجرای refine صرف نظر کنیم در نتیجه دو سؤال مطرح می‌شوداولین مسئله را می‌توان توسط یک محاسبه کوتاه‌ترین مسیر مبدأ واحد در formula_285 حل کرد که formula_286 از روی formula_286 با اضافه کردن formula_118 به هر وزن یال به دست می‌آیدو گولدبرگ پیشنهاد کرد که محاسبهٔ کوتاهترین مسیر در هر تکرار انجام گیرد یعنی چک شود که آیا روند formula_6 جاری بهینه است یا خیر و تنها در صورت منفی بودن جواب refine صدا زده شود.مکاشفهٔ دیگر توسط راه حل مسئله دوم به دست می‌آید. این احتمال گولد برگ و تارجان، و گولدبرگ و همکارانش، مورد اشاره قرار گرفته اما بیشتر دنبال نشده‌است. ملاحظه کنید که formula_32 ،formula_118 بهینه است اگر هیچ مدار جهت دار از مجموع وزن منفی در formula_285 وجود نداشته باشد که در آن formula_293 برای همه یformula_278 . لذا کوچکترین formula_118 که به ازای آن formula_118 بهینه می‌شود عبارت است ازformula_297 که در آن formula_298 عبارت است از کمترین وزن میانگین مدار جهت دار در formula_299.لذا مسئله دوم چیری به جز یک مسئله کمترین چرخهٔ میانگین نیست. این مسئله را می‌توان توسط یک الگوریتم پارامتری کوتاه‌ترین مسیر به‌طور بسیار کارآند حل کرد. یک نسخهٔ پایه توسط کارپ و ارلین و اشنایدر توصیف شده و نسخهٔ بهبود یافتهٔ آن توسط تارجان و ارلین بیان شده‌است. یک پیاده‌سازی کارآمد این الگوریتم توسط بوناگل توصیف شده‌است. زمان اجرا در بدترین حالت عبارت است از formula_300.برای پیاده‌سازی الگوریتم روند کمترین هزینه، ما مسئله دوم را با استفاده از محاسبه پارامتری کوتاه‌ترین مسیر در هر تکرار حل کردیم. کوچکترین formula_118 که سبب شود روند formula_6 جاری formula_118 بهینه شود را پیدا می‌کنیم و همچنین یک formula_49 بالقوه مناسب را میابیم. سپس refine را به formula_32، formula_49 وformula_307 اعمال می‌کنیم.این مکاشفه منجر به بهبود قابل ملاحظه‌ای در زمان اجرا شد. در مقایسه با این که توسط یک محاسبه ساده کوتاه‌ترین مسیر فقط چک شود که آیا روند بهینه است، ما به بهبود زمان اجرا به میزان 40% دست یافتیم.سؤال دیگر این است که پارامتر formula_222 چه طور انتخاب شود. ملاحظات تئوری مقدار 4 را پیشنهاد می‌کند، پیشگویی push.مکاشفه دیگر به نام پیشگویی push به گولدبرگ منتسب است. هدف آن اجتناب از هل دادن روند از یک راس formula_12 به یک همسایه formula_222. است اگر این روند در قدم بعد از آن احتمال دارد مجدداً به formula_12 هول داده شود. ما الگوریتم را تغییر می‌دهیم و هل دادن را بیش از formula_312 واحد از روند به راس formula_25 انجام نمی‌دهیم. اگر این عدد مثبت باشد بیانگر تعداد روندهایی است که می‌تواند از formula_222، بدون relabeling هل داده شود.لازم است رویه relabel را گسترش داد. اگر به اندازه formula_315 واحد از formula_12 بهformula_25 هل داده شود، راس formula_25 به عنوان بیش فعال علامت می خورد. پس از آن هیچ روند اضافه‌ای نمی‌تواند به سمت formula_25 هل داده شود تا این که formula_25، relabel شود. به علاوه قبل از relabel کردنformula_12، formula_25را نمی‌توان relabel کرد اما اگر formula_323، آنگاه پس از آن که تمام هل‌های احتمالی از formula_25 انجام گرفته باشد formula_25 فعال نخواهد بود. این موضوع نشان می‌دهد که لازم است عمل relabel به رأس‌های بیش فعال گسترش داده شود. مستقل از این که آیا این رأس‌ها فعالند یا خیر.گولدبرگ و خاریتونوف نیز پیشنهاد می‌دهند که رویه relabel به صورت فوق ذکر به رأس‌های پیش فعال اعمال شود با این فرق که در مواردی که هیچ یال باقی مانده‌ای راس relabel را ترک نمی‌کند، این احتمال به اندازه formula_118 کاهش یابد. ما رویه relabel متفاوت زیر را پیاده‌سازی کردیم. formula_255 formula_224 formula_329 formula_330 formula_244 formula_332 formula_230دلیل ما برای انتخاب رویه relabel گسترش یافته آن است که نا را قادر می‌سازد که مقدار بیشینه قدر مطلق مقادیر بالقوه را محدود کنیم. این موضوع به دلایل عددی مهم است.در هنگام بررسی یک راس بیش فعال formula_12 امکان دارد راس دیگری مانند formula_25 بیش فعال گردد. اگر رأس‌های بیش فعال در داخل یک پشته قرار دهیم و همیشه آخرین راس بیش فعال اضافه شده را در نظر داشته باشیم می‌توان این رأس‌ها را با ترتیب سریع بررسی کرد.( توجه شود که گراف قابل تصدیق فاقد چرخه است). رویه بازگشتی زیر این موضوع را منعکس می‌کند. formula_236 formula_224 formula_238 formula_239 formula_224 formula_241 formula_342 formula_230 formula_230 formula_345 formula_224 formula_347 formula_224 formula_349 formula_224 formula_351 formula_352 formula_224 formula_354 formula_355 formula_230 formula_230 formula_244 formula_224 formula_360 formula_361 formula_224 formula_363 formula_364 formula_230 formula_230 formula_230 formula_230تعداد عمل‌های relabel که به هر راس اعمال می‌شود را کماکان می‌توان به formula_369 محدود کرد. در عمل تعداد عمل‌های relabel تقریباً ثابت می‌ماند در حالی که تعداد عمل‌های push به اندازه 40-60% کاهش می یابد. به علاوه روند محاسبه شده توسط رویه refine جدید معمولاً بهتر است یعنی برای formula_271 کوچکتری formula_271-بهینه است. در نتیجه ترکیب با مکاشفه پالایش قیمت توصیف شده در فصل قبل بسیار کارآمد می‌باشد.برچسب‌گذاری مجدد کردن.سومین کشف مهم عملیات برچسب‌گذاری مجدد را گسترش می‌دهد به‌طوری‌که رأس‌ها ی زیادی در یک مرحله برچسب‌گذاری مجدد می‌شوند. اگر S یک زیرمجموعه از راس‌هایی باشد که شامل همهٔ رأس‌های بیش از حد منفی باشد، متمم v(g)/sحداقل یک راس فعال داردو فرض کنید که در گراف مورد قبول از V (G) / S به Sلبه هم نداریم سپس عملیات برچسب‌گذاری مجدد قابل اجرا است:پتانسیل همهٔ راس‌ها در V (G) / S را می‌توان به اندازه ɛ کاهش داد.مشخص است که این عملیات بهینگی ɛ را در f از بین نمی‌برد. این نظریه که در محدوده اعداد push و عملیات برچسب‌گذاری مجدد است،اگر عملیات برچسب‌گذاری مجدد به کار برده شوند ، تغییر نمی‌کنند و تعداد دفعات ان هم اهمیتی ندارد.(در مثال [2] اثبات شده‌است)عملیات برچسب‌گذاری مجدد (set_relabel) می‌تواند این‌گونه بازگو شود: formula_224procedure relabel global(π)beginS := { v∊ V (G) : ef (v) &lt; 0};while V (G) \ S contains an active vertex dobeginAdd 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&gt; 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 DiscreteMathematics 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