مسئله بیشینه جریان
در تئوری بهینهسازی، مسائل بیشینه جریان شامل پیدا کردن یک جریان عملی بیشینه از داخل یک شبکهٔ جریان تک-مبدأ و تک-مقصد است.
میتوان به مسئلهٔ بیشینه جریان، به صورت حالت خاصی از مسائل پیچیدهتر شبکهٔ جریان، مانند مسئلهٔ گردش، نگاه کرد. مقدار ماکسیمم یک جریان s-t (جریان از مبدأ به مقصد) برابر حداقل ظرفیت یک برش s-t (برشی که مبدأ را از مقصد جدا میکند) در شبکه است، همانطور که در قضیهٔ جریان بیشینه-برش کمینه ذکر شده است.
تاریخچه
مسئلهٔ بیشینهٔ جریان ابتدا توسط T. E. Harris و F. S. Ross در سال ۱۹۵۴ به عنوان مدل ساده شدهای از جریان
رفت و آمد خط آهن شوروی مطرح شد. در ۱۹۵۵، .Lester R. Ford, Jr و Delbert R. Fulkerson اولین الگوریتم شناخته شده، الگوریتم فورد–فالکرسون را ایجاد کردند.
در طول زمان، تعداد زیادی راه حل بهبود یافته برای مسئلهٔ بیشینهٔ جریان پیدا شده است، به ویژه الگوریتم کوتاهترین راه افزوده از Edmonds و Karp و به صورت مستقل از Dinitz، الگوریتم سد کردن جریان Dinitz، الگوریتم ارسال-برچسب Goldberg و Tarjan، و الگوریتم سد کردن دودویی جریان از Goldberg و Rao. الگوریتم جریان الکتریکی Madry، Kelner، Christano و Spielman یک جریان بیشینهٔ تقریباً بهینه مییابد اما فقط در گرافهای بدون جهت کار میکند.
تعریف
فرض کنید
- ظرفیت یک یال، نگاشت است که بایانمایش داده میشود، و نشان دهندهٔ بیشینه مقدار جریانی است که میتواند از یال بگذرد.
- یک جریان، نگاشت است که بایانمایش داده میشود و دارای دو شرط زیر است:
- به ازای هر(شرط ظرفیت: جریان یک یال نمیتواند از ظرفیتش بیشتر باشد)
- به ازای هر(بقای جریانها: جمع جریانهای ورودی یک رأس باید با جمع جریانهای خروجی از آن برابر باشد، به جز در رأسهای مبدأ و مقصد)
- مقدار جریان به صورت تعریف میشود که، مبدأاست. مقدار جریان، نشاندهندهٔ میزان جریان گذرنده از مبدأ به مقصد است.
مسئلهٔ بیشینه جریان، بیشینه کردن
راهحلها
میتوان گراف باقیمانده را تعریف کرد تا راهی اصولی برای جستجو کردن عملیاتهای جلو-عقب برای یافتن بیشینه جریان فراهم کند.
اگر شبکهٔ جریان
- مجموعه رأسهای هماننداست.
- هر رأس از، دارای ظرفیتاست.
- هر رأس از، دارای ظرفیتاست.
الگوریتمهای حل مسئلهٔ بیشینه جریان در جدول زیر نشان داده شدهاست.
روش | پیچیدگی | توضیح |
---|---|---|
برنامهنویسی خطی | - | شرطها توسط تعریف جریان مجاز داده شدهاند. برنامهٔ خطی را اینجا ببینید. |
الگوریتم فورد-فالکرسون | تا جایی که مسیری باز در گراف باقی مانده وجود دارد، کمینه ظرفیتهای گراف باقی مانده را به مسیر میفرستد. این الگوریتم فقط زمانی کار میکند که همه وزنها عدد صحیح باشند، در غیر این صورت ممکن است مقدار بیشینه برگردانده نشود. | |
الگوریتم Edmonds Karp | مدل خاصی از الگوریتم فورد-فالکرسون، که با جستجوی سطح اول مسیرهای اضافه شده را پیدا میکند. | |
الگوریتم سد جریان Dinitz | این الگوریتم در هر مرحله یک گراف لایهای را به وسیله جستجوی سطح اول روی گراف باقیمانده میسازد. بیشینه جریان در یک گراف لایهای در (O(VE محاسبه میشود، و بیشترین تعداد مرحل n-1 است. الگوریتم دینیک در شبکههای دارای ظرفیتهای واحد، در | |
الگوریتم ارسال-برچسب عمومی | الگوریتم ارسال-برچسب از یک پیشجریان (یک تابع جریان با امکان افزایش در رأسها) پشتیبانی میکند. الگوریتم اجرا تا وقتی که رأسی با افزایش مثبت (یک رأس فعال در گراف) وجود دارد اجرا میشود. عمل push جریان را روی یک یال باقیمانده افزایش میدهد، و یک تابع ارتفاع روی رأسها کنترل میکند که کدام یال باقیمانده میتواند push شود. استفادهٔ درست از این توابع تضمین میکنند که جریان به دست آمده یک جریان بیشینه است. | |
الگوریتم ارسال-برچسب عمومی همراه با قانون انتخاب رأس FIFO | این الگوریتم همواره آخرین رأس فعال را انتخاب میکند و عمل push را تا زمانی که افزایش مثبت است یا یک یال باقیمانده مجاز از این رأس وجود دارد، انجام میدهد. | |
الگوریتم سد جریان Dinitz به همراه درخت پویا | داده ساختار درخت پویا سرعت محاسبه بیشینه جریان را در گراف لایهای تا | |
الگوریتم ارسال-برچسب عمومی همراه با درخت پویا | این الگوریتم با توجه به تابع ارتفاع، درختی با اندازه محدود روی گراف باقیمانده میسازد. این درختها امکان اعمال push چندسطحی را فراهم میکنند. | |
الگوریتم سد جریان دودویی | مقدار U به بیشینه ظرفیت شبکه وابسته است. | |
الگوریتم MPM (مخفف Pramodh-Kumar, Malhotra و Maneshwari) | به مقالهٔ اصلی مراجعه کنید. | |
الگوریتم KRT + Jim Orlin's (مخفف Rao, King و Tarjan) | الگوریتم Orlin مسئلهٔ بیشینه جریان را در زمان |
قضیهٔ جریان انتگرال
قضیهٔ جریان انتگرال میگوید:
- اگر هر یال در شبکهٔ جریان ظرفیت انتگرالی داشته باشد، آنگاه یک جریان ماکسیمال انتگرالی وجود دارد.
کاربرد
مسئلهٔ بیشینه جریان چند-مبدأ و چند-مقصد
میخواهیم جریان بیشینه را روی شبکهٔ
کمینه پوشش مسیر در گراف جهتدار بدون دور
برای پیدا کردن کمینه تعداد مسیرها برای پوشش دادن تمام رأسهای
- که درجهٔ خروجی هرمثبت است.
- که درجهٔ ورودی هرمثبت است.
- .
آنگاه میتوان با استفاده از نظریه کونیگ نشان داد که
تطابق بیشینهٔ دوبخشی
برای پیدا کردن تطابق بیشینه (تطابقی که بیشترین تعداد رأسهای ممکن را دارد) در یک گراف دو بخشی
- شامل یالهایی ازاست که جهتشان ازبهاست.
- برای هروبرای هر.
- برای هر(شکل ۴٫۳٫۱ را ببینید).
آنگاه مقدار بیشینه جریان در
مسئلهٔ بیشینه جریان با ظرفیت رأس
اگر شبکهٔ
به بیان دیگر مقدار جریانی که از یک رأس میگذرد نمیتواند از ظرفیت آن بیشتر باشد. برای یافتن ماکسیمم جریان در
بیشینه مسیر مستقل
دو مسیر از هم مستقل اند اگر به جز
- وبه ترتیب مبدأ و مقصداند.
- برای هر.
- برای هر.
آنگاه مقدار بیشینه جریان برابر تعداد مسیرهای مستقل از
بیشینه مسیر یالمجزا
برای پیدا کردن بیشینه تعداد مسیرهای یالمجزا از رأس
بیشینه مسیر رأسمجزا
برای پیدا کردن بیشینه تعداد مسیرهای رأسمجزا از رأس
- هر رأس در گراف را به دو رأسوتقسیم کنید.
- برای هر رأس یالی با ظرفیت یک ازبهاضافه کنید.
- هر یال در گراف را با یالی ازبهبا ظرفیت یک تعویض کنید.
- یک رأس مقصد اختصاصی جدید به نام اضافه کنید.
- برای هر رأس ، یالی ازبهبا ظرفیت یک اضافه کنید.
- یک بیشینه جریان از به t پیدا کنید. مقدار جریان برابر تعداد مسیرهای رأسمجزا است.
کاربردهای مسئله در دنیای واقعی
بازیهای حذفی بیسبال
در این مسئله،
فرض کنید گراف
برنامهریزی خطوط هوایی
یکی از مسائل مهم در صنایع خطوط هوایی، برنامهریزی برای خدمهٔ پرواز است. مسائل برنامهریزی در خطوط هوایی میتواند به عنوان کاربردی از تعمیم مسئلهٔ بیشینهٔ جریان مطرح شود. ورودی مسئله، مجموعهای از پروازها (
برای حل این مسئله، از مدل متفاوتی از مسئلهٔ گردش به نام گردش کراندار استفاده میکنیم، که مدل کلیای از مسئلهٔ جریان است که در آن برای حداقل جریان منحصر با یالها محدودیت قائل میشویم.
- یالهایی با ظرفیت [۰٬۱] بین و هر
- یالهایی با ظرفیت [۰٬۱] بین هر و
- یالهایی با ظرفیت [۰٬۱] بین هر جفت و
- یالهایی با ظرفیت [۰٬۱] بین هر و، اگر بتوانیم با صرف هزینه و زمان معقول ازبهبرسیم.
- یالی با ظرفیت [∞,۰] بین و
در روش ذکر شده، ادعا و اثبات میشود که پیدا کردن یک جریان با مقدار
نوع دیگری از برنامهریزی خطوط هوایی، پیدا کردن حداقل خدمه برای انجام شدن تمامی پروازهاست. برای پیدا کردن جواب این مسئله، یک گراف دو قسمتی
مسئلهٔ تقاضای گردش
تعدادی کارخانه هستند که کالا تولید میکنند و تعدادی دهکده هستند که باید به آنها کالا برسد. آنها با شبکهای از جادهها به هم متصل اند که هر جاده ظرفیت
- یک رأس مبدأ () اضافه کنید و یالهایی از آن به هر رأس کارخانه () با ظرفیت تولیداضافه کنید، کهآهنگ تولید کارخانهٔاست.
- یک رأس مقصد () اضافه کنید و یالهایی از هر رأس دهکده () با ظرفیتبه آن اضافه کنید، کهمیزان تقاضای دهکده است.
اگر یک گردش وجود داشته باشد، مسئلهٔ بیشینه جریان جواب این که چه مقدار کالا برای برآورده شدن تقاضا باید از طریق یک جادهٔ خاص فرستاده شود را به ما میدهد.
عدالت در اشتراک اتومبیل
مسئله این است که
میتوانیم بر اساس تعداد افرادی که از ماشین استفاده میکنند تصمیم بگیریم، یعنی اگر
هدف این است که پی ببریم آیا چنین وضعیتی امکانپذیر است یا خیر. برای این منظور همانطور که در شکل نشان داده شده است، سعی میکنیم مسئله را به یک شبکه تبدیل کنیم.
حال میتوان ثابت کرد که اگر جریان
منابع
جستارهای وابسته
- بیشینه جریان