الگوریتم Goldberg و Tarjan

1- مسئله گردش با کمترین هزینه
ورودی‌های مسئله عبارتند از:
گراف جهت دار
هزینه‌ها که اعداد صحیح هستند.
ظرفیت‌ها که اعداد صحیح هستند.
تقاضاها که اعداد صحیح هستند.
هدف: یافته جریان است که
را مینیمم می‌کند به‌طوری که:
تعریف 1: یک گردش شرایط زیر را ارضا می‌کند.
در این تعریف جدید، جریان در قوس اولیه شرط را ارضا می‌کند و هر واحد جریان هزینه را تحمیل می‌کند. جریان در قوس معکوس شرط را ارضا کرده و هزینه را برای هر واحد جریان تحمیل می‌کند. هزینه کل برای دو یال با جریان
برابر است. بنابراین بهینه‌سازی هزینه کل برای این گراف جدید معادل بهینه‌سازی هزینه کل برای گراف اولیه است.
برای یک جریان در گراف گراف باقی‌مانده را گرافی تعریف می‌کنیم که مجموعه یال‌های آن عبارتند از:
کران بالای را برای یال تعریف می‌کنیم. واضح است که
تعریف 2: یک پتانسیل تابعی است به صورت
تعریف 3: فرض کنید تابع پتانسیل داده شده‌است. هزینه کاهش یافته را به صورت زیر تعریف می‌کنیم:
آنگاه داریم:
تعریف 4: هزینه یک دور برابر است با:
تئوری 1: موارد زیر با هم معادلند.
f یک گردش با کمترین هزینه است.
هیچ دور با هزینه منفی در وجود ندارد.
تابع پتانسیل موجود است که برای هر داریم
2- الگوریتم حذف یک دور
تئوری فوق منجر به الگوریتمی برای محاسبه گردش با کمترین هزینه می‌شود. این الگوریتم به صورت زیر است.
فرض کنید که یک گردش شدنی باشد.
تا وقتی که شامل دور منفی است
را حذف کرده و را به روز رسانی کن.
صحت الگوریتم فوق از تئوری بالا نتیجه می‌شود. اگر هزینه‌ها و ظرفیت‌ها، هر دو صحیح باشند، جریان بهینه موجود است به نحوی که برای هر صحیح است. فرض کنید:
بنابراین هر گردش شدنی دارای هزینه حداکثری و هزینه حداقلی است. چون حذف یک دور، هزینه گردش را حداقل به اندازه یک واحد کاهش می‌دهد، برای یافتن یک گردش بهینه به حداکثر حذف نیاز است.
برای رسیدن به این نتیجه‌گیری که الگوریتم فوق شبه چندجمله‌ای است، به دو مورد زیر نیاز داریم.
یک گردش اولیه. (این گردش را می‌توان با محاسبه گردش ماکسیمم به دست آورد.)
امکان چک کردن وجود دور با هزینه منفی. (این کار را می‌توان با استفاده از الگوریتم bellman-ford در زمان انجام داد. بنابراین ما یک الگوریتم چندجمله‌ای داریم که در زمان اجرا می‌شود.
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 به کاهش می‌دهد.
مکاشفه‌ای
پالایش قیمت
رویه refine یک روند ، -بهینه محاسبه می‌کند. از طرفی بسیار اتفاق میافتد که این روند از قبل برای بعضی از بهینه برای بعضی از . در این صورت ممکن است بتوانیم از بعضی تکرارها بدون اجرای refine صرف نظر کنیم در نتیجه دو سوال مطرح می‌شود
برای بک روند به نام یک یک بالقوه پیدا می‌کنیم مانند برای همه یا یک که بهینه نباشد، تعریف می‌شود.
برای یک روند به نام ، کوچکترین پیدا می‌شود که بهینه است.
اولین مسئله را می‌توان توسط یک محاسبه کوتاه‌ترین مسیر مبدا واحد در حل کرد که از روی با اضافه کردن به هر وزن یال به دست می‌آیدو گولدبرگ پیشنهاد کرد که محاسبه‌ی کوتاهترین مسیر در هر تکرار انجام گیرد یعنی چک شود که آیا روند جاری بهینه است یا خیر و تنها در صورت منفی بودن جواب refine صدا زده شود.
مکاشفه‌ی دیگر توسط راه حل مسئله دوم به دست می‌آید. این احتمال گولد برگ و تارجان ، و گولدبرگ و همکارانش، مورد اشاره قرار گرفته اما بیشتر دنبال نشده است. ملاحظه کنید که ، بهینه است اگر هیچ مدار جهت دار از مجموع وزن منفی در وجود نداشته باشد که در آن برای همه‌ی
. لذا کوچکترین که به ازای آن بهینه می‌شود عبارت است از که در آن عبارت است از کمترین وزن میانگین مدار جهت دار در .
لذا مسئله دوم چیری به جز یک مسئله کمترین چرخه‌ی میانگین نیست. این مسئله را می‌توان توسط یک الگوریتم پارامتری کوتاه‌ترین مسیر به‌طور بسیار کارآند حل کرد. یک نسخه‌ی پایه توسط کارپ و ارلین و اشنایدر توصیف شده و نسخه‌ی بهبود یافته‌ی آن توسط تارجان و ارلین بیان شده‌است. یک پیاده‌سازی کارآمد این الگوریتم توسط بوناگل توصیف شده‌است. زمان اجرا در بدترین حالت عبارت است از .
برای پیاده‌سازی الگوریتم روند کمترین هزینه، ما مسئله دوم را با استفاده از محاسبه پارامتری کوتاه‌ترین مسیر در هر تکرار حل کردیم. کوچکترین که سبب شود روند جاری بهینه شود را پیدا می‌کنیم و همچنین یک بالقوه مناسب را میابیم. سپس refine را به ، و
اعمال می‌کنیم.
این مکاشفه منجر به بهبود قابل ملاحظه‌ای در زمان اجرا شد. در مقایسه با این که توسط یک مخاسبه ساده کوتاه‌ترین مسیر فقط چک شود که آیا روند بهینه است ، ما به بهبود زمان اجرا به میزان 40% دست یافتیم.
سوال دیگر این است که پارامتر چه طور انتخاب شود. ملاحظات تئوری مقدار 4 را پیشنهاد می‌کند،
پیشگویی 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)
1000).
برچسب‌گذاری مجدد از بقیه کم اهمیت‌تر است اما مواردی هست که با عدم استفاده از هر یک از کشفیات میتوان زمان اجرا را بسیار بالاتر برد.
منابع