موضوع مقاله: الگوریتم Goldberg و Tarjan | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم Goldberg و Tarjan | مقدمه: فرض می‌کنیم با تئوری روند شبکه آشنایی داریم و نتایج و نشان‌گذاری استاندارد را استفاده می‌کنیم. | ## بخش 1: الگوریتم Goldberg و Tarjan | مسئله روند کمترین هزینه به این صورت تعریف می‌شود: گراف جهت دار با گنجایش داده شده‌است: ، سنگینی و ارزش تعادل ، را به عنوان یک روند کمترین روند هزینه بیابید، به‌طوری‌که تابع با برای همهٔ ‌های عضو و برای همهٔ ‌های عضو از قبیل که کمترین مقدار یا همان مینیموم می‌باشد مجموعه‌ای از ورودی‌های را تشکیل می‌دهد. واضح است که امکان وجود روند کمترین هزینهٔ مسائل، می‌تواند در برابر محاسبه روند ماکسیموم چک شود ( و در بهترین شرایط روند می‌تواند پیدا شود). مسائل روند ماکسیموم آسانترند و خیلی سریعتر از مسائل روند کمترین هزینه حل می‌شوند. نمونه داده شده از مسئله روند کمترین هزینه و روند با برای همهٔ ، ظرفیت باقی‌ماندهٔ یال به وسیله تعریف می‌شود. علاوه بر این، ما یک یال جدید از به برای هر یال در نظر گرفته ایم و و تعریف کرده ایم. باقی‌مانده گراف شامل همه بال‌ها ( قدیمی و جدید) با ظرفیت باقی‌مانده مثبت می‌باشد. معروف است که روند از بهینه است( کمترین هزینه را دارد) اگر و تنها اگر هیچ جریان مستقیم در وزن منفی نداشته باشد. دیاگراف داده شده با وزن ، یک ذخیره امکانپذیر در است، تابع به این صورت که هزینه کاهش یافته است که برای هر نامنفی عبارت برقرار است. یک ذخیره امکانپذیر وجود دارد اگر و تنها اگر هیچ جریان مستقیمی، وزن کل منفی نداشته باشد. روند داده شده با و ذخیره ، یک گراف مجاز تعریف می‌کنیم که تمام یال‌های که هزینهٔ کاهش یافته منفی را دارند، در بر بگیرد. اگر یک روند بهینه باشد( برای بعضی از ها) و یک ذخیره امکانپذیر در باشد، پس مارپیچ است. 1- مسئله گردش با کمترین هزینه ورودی‌های مسئله عبارتند از: گراف جهت دار هزینه‌ها که اعداد صحیح هستند. هدف: یافته جریان است که را مینیمم می‌کند به‌طوری که: تعریف 1: یک گردش شرایط زیر را ارضا می‌کند. در این تعریف جدید، جریان در قوس اولیه شرط را ارضا می‌کند و هر واحد جریان هزینه را تحمیل می‌کند. بنابراین بهینه‌سازی هزینه کل برای این گراف جدید معادل بهینه‌سازی هزینه کل برای گراف اولیه است. برای یک جریان در گراف گراف باقی‌مانده را گرافی تعریف می‌کنیم که مجموعه یال‌های آن عبارتند از: کران بالای را برای یال تعریف می‌کنیم. واضح است که تعریف 2: یک پتانسیل تابعی است به صورت تعریف 3: فرض کنید تابع پتانسیل داده شده‌است. هزینه کاهش یافته را به صورت زیر تعریف می‌کنیم: آنگاه داریم: تعریف 4: هزینه یک دور برابر است با: تئوری 1: موارد زیر با هم معادلند. تابع پتانسیل موجود است که برای هر داریم 2- الگوریتم حذف یک دور تئوری فوق منجر به الگوریتمی برای محاسبه گردش با کمترین هزینه می‌شود. اگر هزینه‌ها و ظرفیت‌ها، هر دو صحیح باشند، جریان بهینه موجود است به نحوی که برای هر صحیح است. چون حذف یک دور، هزینه گردش را حداقل به اندازه یک واحد کاهش می‌دهد، برای یافتن یک گردش بهینه به حداکثر حذف نیاز است. برای رسیدن به این نتیجه‌گیری که الگوریتم فوق شبه چندجمله‌ای است، به دو مورد زیر نیاز داریم. (این گردش را می‌توان با محاسبه گردش ماکسیمم به دست آورد.) امکان چک کردن وجود دور با هزینه منفی. 3- حذف دور با کمترین هزینه متوسط با انتخاب مناسب دوری که در هر مرحله تکرار الگوریتم باید حذف شود، می‌توان یک الگوریتم با زمان چندجمله‌ای به دست آورد. | ## بخش 2: الگوریتم Goldberg و Tarjan | تعریف 5: فرض کنید که هزینه متوسط دور برابر با باشد که هزینه دور و تعداد یال‌های موجود در است. برای داشتن یک الگوریتم با زمان چندجمله‌ای، باید بتوانیم دور با هزینه متوسط کمینه را در زمان چندجمله‌ای پیدا کنیم. تعریف7: یک گردش ، -بهینه است اگر تابع پتانسیل موجود باشد که برای هر داشته باشیم واضح است که ، 0-بهینه است؛ اگر و تنها اگر یک گردش با کمترین هزینه باشد. آنگاه برای هر دور در داریم: راس را به گراف اضافه کرده و و آن را به همه رئوس ، با یال‌هایی به وزن وصل می‌کنیم. پتانسیل را برای گره به صورت طول کوتاه‌ترین مسیر از به با استفاده از هزینه‌های تعریف می‌کنیم. با استفاده از تعریف کوتاهترین مسیر داریم: که نتیجه می‌دهد: این بدان معنی است که ، - بهینه است. بنابراین فرض کنید گردش داده شده باشد و گردش به دست آمده بعد از بار تکرار الگوریتم حذف دور با کمترین هزینه متوسط روی باشد. آنگاه بنابراین حذف دور، یک یال با را از گراف باقی‌مانده حذف و تنها یال‌هایی با را ایجاد می‌کند. الگوریتم گولبرگ و تارجان یک روند ، -بهینه نامیده می‌شود اگر یک ذخیره مانند برای همهٔ . الگوریتم هزینه پیمایش گولبرگ و تارجان یک روند را محاسبه می‌کند که بهینه برای بعضی از ‌های بزرگ است. ( یک پارامتر ثابت است و حداقل مقدار آن 2 می‌باشد) این روال دستوری( مجموعه کد) به صورت زیر اجرا می‌شود: ابتدا مقدار ممکن ماکسیموم از رونددر طول همهٔ یال‌ها با هزینه کاهش یافته منفی هل داده می‌شود. جنبه‌های پیاده سازی تصمیم اولیه در هنگام پیاده‌سازی الگوریتم فوق مربوط به گراف باقی مانده‌ای است: لازم نیست که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم. اما اگر بدون ذخیره‌سازی عمل شود، لازم است تمام یال‌های همسایهٔ یک راس فعال چک شود قبل از این که بتوان آن را relabel کرد. لذا تصمیم گرفتیم که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم به وجودی که لازم است بعد از هر عمل push آن را به روز کنیم. در حقیقت روند به‌طور صریح مورد نیاز نیست مگر در زمان باز گرداندن خروجی بعد از پایان الگوریتم. هزینه‌های کاهش یافته به‌طور صریح ذخیره نمی‌شوند چون مشخص گردید که به صرفه تر است که هر گاه که مورد نیاز بودند مجدداً محاسبه شوند. اشاره‌گری داریم که برای هر راس فعال عنصر جاری در این لیست را نشانه‌گذاری می‌کند. هرگاه یک push یال جاری را اشباح کند( یا وقتی که الگوریتم مشخص می‌کند که یال جاری دارای هزینه کاهش یافته غیر منفی است) اشاره گر به جلو حرکت می‌کند. این امر متضمن آن است که یک relabel می‌تواند زمانی که اشاره گر به انتهای لیست می‌رسد انجام پذیرد. با توجه به این که تعداد رأس‌های فعال معمولاً کم است لازم است که ساختمان داده‌ای استفاده شود که مجموعه گره‌های فعال را در بر دارد. راه پیچیده تر عبارت است از ذخیره کردن رأس‌های فعال به صورت یک ترتیب مبتنی بر همبندی نسبت به گراف قابل تصدیق ( که غیر چرخه‌ای است). به علاوه انتخاب اولین راس با ترتیب مبتنی بر همبندی پر هزینه تر است حتی موقعی که از کارآمدترین ساختمان داده، دنباله فیبوناچی استفاده شود. با توجه به این ملاحظات تصمیم گرفتیم که رأس‌های فعال را در یک صف ساده ذخیره کنیم. در این صورت ممکن است بتوانیم از بعضی تکرارها بدون اجرای refine صرف نظر کنیم در نتیجه دو سؤال مطرح می‌شود برای بک روند به نام یک یک بالقوه پیدا می‌کنیم مانند برای همه یا یک که بهینه نباشد، تعریف می‌شود. | ## بخش 3: الگوریتم Goldberg و Tarjan | اولین مسئله را می‌توان توسط یک محاسبه کوتاه‌ترین مسیر مبدأ واحد در حل کرد که از روی با اضافه کردن به هر وزن یال به دست می‌آیدو گولدبرگ پیشنهاد کرد که محاسبهٔ کوتاهترین مسیر در هر تکرار انجام گیرد یعنی چک شود که آیا روند جاری بهینه است یا خیر و تنها در صورت منفی بودن جواب refine صدا زده شود. این احتمال گولد برگ و تارجان، و گولدبرگ و همکارانش، مورد اشاره قرار گرفته اما بیشتر دنبال نشده‌است. ملاحظه کنید که ، بهینه است اگر هیچ مدار جهت دار از مجموع وزن منفی در وجود نداشته باشد که در آن برای همه ی . لذا کوچکترین که به ازای آن بهینه می‌شود عبارت است از که در آن عبارت است از کمترین وزن میانگین مدار جهت دار در . این مسئله را می‌توان توسط یک الگوریتم پارامتری کوتاه‌ترین مسیر به‌طور بسیار کارآند حل کرد. برای پیاده‌سازی الگوریتم روند کمترین هزینه، ما مسئله دوم را با استفاده از محاسبه پارامتری کوتاه‌ترین مسیر در هر تکرار حل کردیم. کوچکترین که سبب شود روند جاری بهینه شود را پیدا می‌کنیم و همچنین یک بالقوه مناسب را میابیم. در مقایسه با این که توسط یک محاسبه ساده کوتاه‌ترین مسیر فقط چک شود که آیا روند بهینه است، ما به بهبود زمان اجرا به میزان 40% دست یافتیم. ما الگوریتم را تغییر می‌دهیم و هل دادن را بیش از واحد از روند به راس انجام نمی‌دهیم. 12, 157-198 نیز پیشنهاد می‌دهند که رویه relabel به صورت فوق ذکر به رأس‌های پیش فعال اعمال شود با این فرق که در مواردی که هیچ یال باقی مانده‌ای راس relabel را ترک نمی‌کند، این احتمال به اندازه کاهش یابد. دلیل ما برای انتخاب رویه relabel گسترش یافته آن است که نا را قادر می‌سازد که مقدار بیشینه قدر مطلق مقادیر بالقوه را محدود کنیم. اگر رأس‌های بیش فعال در داخل یک پشته قرار دهیم و همیشه آخرین راس بیش فعال اضافه شده را در نظر داشته باشیم می‌توان این رأس‌ها را با ترتیب سریع بررسی کرد.( توجه شود که گراف قابل تصدیق فاقد چرخه است). به علاوه روند محاسبه شده توسط رویه refine جدید معمولاً بهتر است یعنی برای کوچکتری -بهینه است. اولین سطل به شماره B(v) به هر راس v اختصاص داده می‌شود برای اینکه سطل حاوی v یا ∞را (در صورتی‌که v در هیچ‌کدام از سطل‌ها قرار نگرفته باشد) نشان دهد. در نهایت B(v) شماره عملیات برچسب‌گذاری مجدد خواهد شد که برای راس v به کار برده می‌شود. ابتدا همهٔ رأس‌ها ی منفی در سطل با مقدار صفر قرار می‌گیرند و بقیه سطل‌ها خالی می‌مانند. اگر این بعد از هر n بار عملیات عادی برچسب‌گذاری مجدد استفاده شود، بدترین حالت زمان اجرای بهبود بخشیدن تغییر نمی‌کند. هر چند که این، زمانی می‌تواند درست باشد که فقط در هر مرحله بهبود بخشی به اندازه O(n)، برچسب‌گذاری مجدد داشته باشیم. ابتدا یک مولد، منبعی را تولید می‌کند و سپس یک شبکه یدک شامل لبه‌های با ظرفیت بالا را می‌سازد برای اینکه از امکان ان اطمینان حاصل شود. چون تفاوت‌های ناچیزی در نتایج محاسبه شده بین دو کلاس داریم، باید خودمان را به حالت دوم محدود کنیم چون حالت اول مشکلات بیشتری دارد. هر اکتشافی پیشرفت قابل توجهی از تعداد عملیات برچسب‌گذاری مجدد و pushرا می‌دهد و زمان اجرا به وضوح به این عملیات‌ها بستگی دارد. استفاده زیاد از برچسب‌گذاری مجدد می‌تواند زمان اجرا را برای اعداد بزرگ کاهش دهد (n> 1000). | ## جمع‌بندی | برچسب‌گذاری مجدد از بقیه کم اهمیت تر است اما مواردی هست که با عدم استفاده از هر یک از کشفیات می‌توان زمان اجرا را بسیار بالاتر برد.