بخشی از مقاله
الگوریتم های یافتن جریان بیشینه درگراف های مسطح
چکیده
مسئله یافتن جریان بیشینه در یک گراف یا یک شبکه، مسئله ای شناخته شده با کاربردهای متفاوت مانند محصولات نفتی دریک شبکه لوله ای، خودروها دریک شبکه جاده ای وغیره است. در شبکه شار ما به دنبال ارسال بیشترین مقدار جریان از یک رأس مبدأ به یک رأس مقصد در یک گراف هستیم، با در نظر گرفتن این محدودیت که جریان در هیچ یالی نمی تواند از ظرفیت آن یال فراتر رود. هدف در جریان بیشینه باید بتوان با استفاده از الگوریتم های بهینه حداکثر استفاده ممکن از ظرفیت یال را انجام نمود. و دراین زمینه الگوریتم های از جمله فورد-فالکرسون، دموندکارپ، جستجوی اول سطح، چپ ترین مسیر و بسیاری دیگر وجود دارند. که در این مقاله به جریان بیشینه درگراف های مسطح و مقایسه بهینه ترین الگوریتم پرداخته می شود.
مقدمه
درمسئله جریان بیشینه به هر یال ظرفیتی نسبت داده می شود که جریان عبوری از آن را محدود می کند وما را در جستجوی راهی برای ارسال بیشترین میزان جریان از یک گره مبدأ S به یک گره مقصد t با در نظر گرفتن این محدودیت ها هستیم. در شبکه ها با حالتی از مسئله روبرو هستیم که در آن علاوه بر یالها، رئوس شبکه نیز دارای ظرفیت هستند، یعنی میزان جریانی که می تواند به هر رأس وارد شود دارای محدودیت است. این حالت برای نمونه در هنگام محاسبه ی مسیرهای مجزا در گراف ها (یافتن مسیر هایی بین یک مبدأ و مقصد مشخص به گونه ای که این مسیرها به جز مبدأ ومقصد، رأس مشترکی نداشته باشند)، ویا در مسئله دیگری که رئوس، مدلی از اشیای دارای ظرفیت هستند پایدار می شود. جریان بیشینه کاربردهای متفاوتی دارد که یکی از اینها می تواند طراحی مدارهای VLSIٌ با کلاس خاصی از گراف ها یعنی گراف های مسطح است. ما در این مقاله میخواهیم به مقایسه کارایی الگوربتم ها وتشخیص بهینه ترین الگوریتم بپردازیم. در ابتدا به شرح مختصری از الگوریتم ها پرداخته می شود. و در بخش بعدی، الگوریتم های که برای حل مسئله جریان بیشینه در گراف مسطح استفاده می شوند تحلیل ومقایسه خواهند شد. (روچویدهاری وهمکاران،(0991
تعا ریف مسئله جریان بیشینه
مسئله جریان بیشینه مسئله یافتن بیشترین جریان عبوری (از نظر ارزش جریان) از یک منبع واحد به یک مقصد واحد است.
گراف مسطح
در نظریه گرافها، گراف مسطح گرافی است که میتواند در یک صفحه محاط شود. برای مثال یک گراف مسطح را میتوان به گونهای رسم کرد که یالهایش یکدیگر را تنها در راسها قطع کنند.
الگوریتم ها
در این بخش به معرفی الگوریتم ها پرداخته می شود.
الگوریتم فورد- فالکرسون
این الگوریتم مسئله جریان بیشینه را در شبکههای جریان حل میکند. این الگوریتم در سال 1956 منتشر شد. ایده اصلی این الگوریتم بسیار ساده است. تا جایی که راهی از منبع (گره شروع) به چاهک (گره پایانی)، با یال وزن دار وجود دارد، میتوان جریان را از یکی از این مسیرها عبور داد. سپس مسیر دیگری پیدا می شود و همین طور الگوریتم ادامه پیدا میکند. این الگوریتم فقط زمانی کار میکند که همه وزن ها عدد صحیح باشند. در غیر این صورت این الگوریتم مقدار بیشینه را بر نمیگرداند]کامپیر و همکاران،.[2102
الگوریتم ادموندز کارپ
این الگوریتم از الگوریتم ارسال _ برچسب که در زمان O(V3) انجام می شود سریع تر است. این الگوریتم اولین بار توسط دانشمند شوروی یوفیم چایمٍ در سال 1970 منتشر شد. و به طور مستقل توسط Jack Edmond و Richard Karp در سال 1972 با کاهش زمان الگوریتم قبلی به(O(VE2 انتشار یافتهاست. ورودی این الگوریتم یک گراف است که یک راس مبدا s دارد و یک راس مقصد t و روی همه یالها ظرفیت هر یال نوشته شده است. خروجی الگوریتم بیشترین جریان از s به t تا زمانی که مسیر افزایشی وجود دارد.
الگوریتم جستجوی اول سطح
یکی از الگوریتمهای پیمایش گراف است. استراتژی جستجوی اول سطح برای پیمایش گراف، همانطور که از نامش پیدا است »جستجوی سطح به سطح گراف« است. الگوریتم از ریشه شروع میکند (در گرافها و یا درختهای بدون ریشه رأس دلخواهی به عنوان ریشه انتخاب می شود) و آن را در سطح یک قرار میدهد. سپس در هر مرحله همه همسایههای رئوس آخرین سطح دیده شده را که تا به حال دیده نشدهاند بازدید میکند و آنها را در سطح بعدی میگذارد. این فرایند زمانی متوقف میشود که همه همسایههای رئوس آخرین سطحقبلاًدیده شده باشند . همچنین در مسائلی که حالات مختلف متناظر با رئوس یک گرافاند و حل مسئله مستلزم یافتن رأس هدف با خصوصیات مشخصی است که در عین حال در بین همه رئوس هدف با آن خصوصیات به ریشه نزدیکترین باشد، جستجوی اول سطح به صورت غیرخلاق عمل میکند. بدین ترتیب که الگوریتم هر دفعه همه همسایههای یک رأس را بازدید کرده و سپس به سراغ رأس بعدی می رود و بنابراین گراف سطح به سطح پیمایش خواهد شد. این روند تا جایی ادامه می یابد که رأس هدف پیدا شود و یااحتمالاًهمه گراف پیمایش شود ]کامپیر و همکاران،. [2102
الگوریتم چپ ترین مسیر
الگوریتم چپ ترین مسیر، تعمیم مستقیمی از الگوریتم بالاترین مسیر فورد و فولکرسون است ؛ الگوریتم بالاترین مسیر، در گراف _stمسطحی که رأس s آن در سمت چپ و رأس آن t آن در سمت راست رسم شده باشد بالاترین جریان را می یابد ؛ جریانی که در آن هیچ جریان دیگری نمی تواند از بالای جریان حاضر فرستاده شود. در این تعمیم به جای بالاترین مسیر،چپ ترین جریان یافته می شود (که با توجه به این که گراف لزوماً _stمسطح نیست، می تواند بالاترین مسیر نباشد)]گرو وهمکاران ،.[2112
روش جریان بیشینه در هرکدام از الگوریتم ها
الگوریتم فورد- فالکرسون
در گراف داده شده G با ظرفیت c و جریان ، برای یالی ازu به v میخواهیم بیشترین جریان از منبع s به چاهک t را پیدا کنیم. بعد از هر مرحله در الگوریتم موارد زیر پیش میآید:
جریانی u به v از ظرفیت بیشتر نمیشود.
شبکه جریان بین uو vرا نگهداری می کند.
به ازای هر گره u به جز چاهک و منبع مقدار جریان ورودی گره برابر جریان خروجی گره است.
در صورت برقراری این سه شرط، شبکه یک جریان قانونی بعد از هر مرحله خواهد داشت. ما شبکه پسماند را اینگونه تعریف میکنیم، شبکه پسماند شبکه ایست که ظرفیتش اینگونه بدست میآید:
توجه کنید که ممکن است جریانی از vبه uوجود داشته باشد، که در شبکههای پسماند قانونی است ولی در شبکه اصلی غیر مجاز است. اگر ، آنگاه ، و است. و ورودی الگوریتم گراف G با ظرفیت c ، یک منبع s و یک چاه t و خروجی آن بیشترین جریان f از s به t میباشد. که مراحل زیر وجود دارند :
را پیدا کن. برای هر یال عضو برای پیدا کردن مسیر در مرحله 2
میتوان از الگوریتمهای َBFS یا ُDFS استفاده نمود. وقتی که مسیر دیگری در مرحله 2 پیدا نشود، s به t در شبکه پسماند نمیرسد. اگر S مجموعهای از گرههای قابلدسترسی برای s در شبکه پسماند باشد، آنگاه مجموع ظرفیت در شبکه اصلی یالها از S به V در یک طرف برابر است با مجموع جریانهایی از s به t پیدا کردهایم. این نشان میدهد که بیشترین جریان پیدا شده است. زمان اجرای این الگوریتم به این بستگی دارد که مسیر P چگونه انتخاب شود . اگر بد انتخاب شده باشد ممکن است الگوریتم خانمه نیابد و مقدار جریان با تکمبل کردنهای پیاپی افزایش خواهد یافت، لزوماً به مقدار ماکزیمم جریان همگرایی پیدا نمیکند. هر چند اگر مسیر تکمیلی با استفاده از الگوریتم جستجوی اول سطح انتخاب شود الگوریتم با مرتبه زمانی چند جملهای اجرا می گردد. در حالت کلی زمان اجرا از O(E*f) است، که E یالهای گراف و f بیشترین جریان است . چون پیدا کردن هر مسیر از O(E) طول میکشد، همچنین از(O(1 طول میکشد تا جریانی اضافه شود. نمونه ای از الگوریتم در زیر نوشته شده است.
الگوریتم ادموندز کارپ
در این اگوریتم میخواهیم بیشینه شاره را از مبدا s تا مقصد t پیدا کنیم این الگوریتم شبیه به الگوریتم الگوریتم فورد– فالکرسون است و تفاوتش این است که در این الگوریتم محدودیت الگوریتم فورد– فالکرسون بهبود مییابد چرا که که محاسبه مسیر افزایشی را با BFS
