مسئله بیشینه جریان

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مثالی از یک شبکه‌ی جریان با بیشینه جریان. مبدأ s و مقصد t است. اعداد نمایانگر جریان و ظرفیت اند.

در تئوری بهینه سازی، مسائل بیشینه جریان شامل پیدا کردن یک جریان عملی بیشینه از داخل یک شبکه‌ی جریان تک-مبدأ و تک-مقصد است.
می‌توان به مسئله‌ی بیشینه جریان، به صورت حالت خاصی از مسائل پیچیده‌تر شبکه‌ی جریان، مانند مسئله‌ی گردش، نگاه کرد. مقدار ماکسیمم یک جریان s-t (جریان از مبدأ به مقصد) برابر حداقل ظرفیت یک برش s-t (برشی که مبدأ را از مقصد جدا می کند) در شبکه است، همان طور که در قضیه‌ی جریان بیشینه-برش کمینه ذکر شده است.

تاریخچه[ویرایش]

مسئله‌‌ی بیشینه‌ی جریان ابتدا توسط T. E. Harris و F. S. Ross در سال 1954 به عنوان مدل ساده شده‌ای از جریان رفت و آمد خط آهن شوروی مطرح شد. در 1955، .Lester R. Ford, Jr و Delbert R. Fulkerson اولین الگوریتم شناخته شده، الگوریتم Ford-Fulkerson را ایجاد کردند.
در طول زمان، تعداد زیادی راه حل بهبود یافته برای مسئله‌‌ی بیشینه‌ی جریان پیدا شده است، به ویژه الگوریتم کوتاه‌ترین راه افزوده از Edmonds و Karp و به صورت مستقل از Dinitz، الگوریتم سد کردن جریان Dinitz، الگوریتم ارسال-برچسب Goldberg و Tarjan، و الگوریتم سد کردن دودویی جریان از Goldberg و Rao. الگوریتم جریان الکتریکی Madry، Kelner، Christano و Spielman یک جریان بیشینه‌ی تقریباً بهینه می‌یابد اما فقط در گراف‌های بدون جهت کار می‌کند.

تعریف[ویرایش]

یک شبکه‌ی جریان با مبدأ s و مقصد t. اعداد کنار یال‌ها ظرفیت هستند.

فرض کنید \scriptstyle N = (V, E) یک شبکه است با \scriptstyle s, t \in V که به ترتیب مبدأ و مقصد هستند.

ظرفیت یک یال، نگاشت \scriptstyle c : E \to \mathbb{R}^+ است که با \scriptstyle c_{uv} یا \scriptstyle c(u, v) نمایش داده می‌شود، و نشان دهنده‌ی بیشینه مقدار جریانی است که می‌تواند از یال بگذرد.
یک جریان، نگاشت \scriptstyle f : E \to \mathbb{R}^+ است که با \scriptstyle f_{uv} یا \scriptstyle f(u, v) نمایش داده می‌شود و دارای دو شرط زیر است:
  1. \scriptstyle f_{uv} \leq c_{uv} به ازای هر \scriptstyle (u, v) \in E (شرط ظرفیت: جریان یک یال نمی‌تواند از ظرفیتش بیشتر باشد)
  2. \scriptstyle \sum_{u:(u, v) \in E} f_{uv} = \sum_{u:(v, u) \in E} f_{vu} به ازای هر \scriptstyle v \in V \setminus \{s, t\} (بقای جریان‌ها: جمع جریان‌های ورودی یک رأس باید با جمع جریان‌های خروجی از آن برابر باشد، به جز در رأس‌های مبدأ و مقصد)
مقدار جریان به صورت \scriptstyle |f| = \sum_{v:(s,v) \in E} f_{sv} تعریف می‌شود که s، مبدأ N است. مقدار جریان، نشان‌دهنده‌ی میزان جریان گذرنده از مبدأ به مقصد است.

مسئله‌ی بیشینه جریان، بیشینه کردن \scriptstyle |f| است، یعنی هدایت بیش‌ترین جریان ممکن از s به t.

راه‌حل‌ها[ویرایش]

می‌توان گراف باقیمانده را تعریف کرد تا راهی اصولی برای جستجو کردن عملیات‌های جلو-عقب برای یافتن بیشینه جریان فراهم کند.
اگر شبکه‌ی جریان G و جریان f روی G را داشته باشیم، \scriptstyle G_{f}، گراف باقیمانده‌ی G را با توجه به f اینگونه تعریف می‌کنیم:

  1. مجموعه رأس‌های \scriptstyle G_{f} همانند G است.
  2. هر رأس \scriptstyle e = (u, v) از \scriptstyle G_{f}، دارای ظرفیت \scriptstyle c_{e} - f(e) است.
  3. هر رأس \scriptstyle e' = (v, u) از \scriptstyle G_{f}، دارای ظرفیت \scriptstyle f(e) است.

الگوریتم‌های حل مسئله‌ی بیشینه جریان در جدول زیر نشان داده شده‌است.

روش پیچیدگی توضیح
برنامه‌نویسی خطی - شرط‌ها توسط تعریف جریان مجاز داده شده اند. برنامه‌ی خطی را اینجا ببینید.
الگوریتم فورد-فالکرسون O(E\max(|f|)) تا جایی که مسیری باز در گراف باقی مانده وجود دارد، کمینه ظرفیت‌های گراف باقی مانده را به مسیر می‌فرستد.

این الگوریتم فقط زمانی کار می‌کند که همه وزن‌ها عدد صحیح باشند، در غیر این صورت ممکن است مقدار بیشینه برگردانده نشود.

الگوریتم Edmonds Karp O(VE^2) مدل خاصی از الگوریتم فورد-فالکرسون، که با جستجوی سطح اول مسیر‌های اضافه شده را پیدا می‌کند.
الگوریتم سد جریان Dinitz O(V^2E) این الگوریتم در هر مرحله یک گراف لایه‌ای را به وسیله جستجوی سطح اول روی گراف باقیمانده می‌سازد. بیشینه جریان در یک گراف لایه‌ای در (O(VE محاسبه می‌شود، و بیشترین تعداد مرحل n-1 است. الگوریتم دینیک در شبکه‌های دارای ظرفیت‌های واحد، در \scriptscriptstyle  O(E\sqrt{V}) به پایان می‌رسد.
الگوریتم ارسال-برچسب عمومی O(V^2E) الگوریتم ارسال-برچسب از یک پیش‌جریان (یک تابع جریان با امکان افزایش در رأس‌ها) پشتیبانی می‌کند. الگوریتم اجرا تا وقتی که رأسی با افزایش مثبت (یک رأس فعال در گراف) وجود دارد اجرا می‌شود. عمل push جریان را روی یک یال باقیمانده افزایش می‌دهد، و یک تابع ارتفاع روی رأس‌ها کنترل می‌کند که کدام یال باقیمانده می‌تواند push شود. استفاده‌ی درست از این توابع تضمین می‌کنند که جریان به دست آمده یک جریان بیشینه است.
الگوریتم ارسال-برچسب عمومی همراه با قانون انتخاب رأس FIFO O(V^3) این الگوریتم همواره آخرین رأس فعال را انتخاب می‌کند و عمل push را تا زمانی که افزایش مثبت است یا یک یال باقیمانده مجاز از این رأس وجود دارد، انجام می‌دهد.
الگوریتم سد جریان Dinitz به همراه درخت پویا O(VE\log(V)) داده ساختار درخت پویا سرعت محاسبه بیشینه جریان را در گراف لایه‌ای تا \scriptscriptstyle O(E log{V}) افزایش می‌دهد.
الگوریتم ارسال-برچسب عمومی همراه با درخت پویا O(VE\log(V^2/E)) این الگوریتم با توجه به تابع ارتفاع، درختی با اندازه محدود روی گراف باقی‌مانده می‌سازد. این درخت‌ها امکان اعمال push چند‌سطحی را فراهم می‌کنند.
الگوریتم سد جریان دودویی [۱] \scriptscriptstyle O(E\min(V^{2/3},\sqrt{E})\log(V^2/E)\log{U}) مقدار U به بیشینه ظرفیت شبکه وابسته است.
الگوریتم MPM (مخفف Pramodh-Kumar, Malhotra و Maneshwari) O(V^3) به مقاله‌ی اصلی مراجعه کنید.
الگوریتم KRT + Jim Orlin's (مخفف Rao, King و Tarjan) O(VE) الگوریتم Orlin مسئله‌ی بیشینه جریان را در زمان O(VE) برای m\leq O(n^{(16/15)-\epsilon}) حل می‌کند در حالی که KRT آن را در زمان O(VE) برای m > n^{1+\epsilon} حل می‌کند.

قضیه‌ی جریان انتگرال[ویرایش]

قضیه‌ی جریان انتگرال می‌گوید:

اگر هر یال در شبکه‌ی جریان ظرفیت انتگرالی داشته باشد، آنگاه یک جریان ماکسیمال انتگرالی وجود دارد.

کاربرد[ویرایش]

مسئله‌ی بیشینه جریان چند-مبدأ و چند-مقصد[ویرایش]

شکل 4.1.1. تبدیل یک مسئله‌ی بیشینه جریان چند-مبدأ چند-مقصد به یک مسئله‌ی بیشینه جریان تک-مبدأ تک-مقصد.

می خواهیم جریان بیشینه را روی شبکه‌ی N=(V,E) که دارای مجموعه‌ی مبدأهای S=\{s_1,...,s_n\} و مجموعه‌ی مقصدهای T=\{t_1,...,t_n\} (به جای تنها یک مبدأ و یک مقصد) است، پیدا کنیم. می‌توانیم مسئله‌ چند-مبدأ و چند-مقصد را با افزودن یک مبدأ تثبیت شده که به تمام راس‌های S متصل است و یک مقصد تثبیت شده که به تمام راس‌های T متصل است (ابرمبدأ و ابرمقصد) و یال‌های آن‌ها ظرفیت بی‌نهایت دارند، به یک مسئله‌ی بیشینه جریان تبدیل کنیم.

کمینه پوشش مسیر در گراف جهت‌دار بدون دور[ویرایش]

برای پیدا کردن کمینه تعداد مسیر‌ها برای پوشش دادن تمام رأس‌های V در یک گراف جهت‌دار بدون دور G=(V,E)، می‌توانیم یک گراف دوبخشی G'=(V_{out} \in V_{in}, E) از G بسازیم که:

  1. V_{out}=\{v \in V\} که درجه‌ی خروجی هر v مثبت است.
  2. V_{in}=\{v \in V\} که درجه‌ی ورودی هر v مثبت است.
  3. E'=\{(u,v) \in (V_{out},V_{in}:(u,v) \in E\}.

آنگاه می‌توان با استفاده از قضیه‌ی Konig نشان داد که G' یک تطابق با اندازه‌ی m دارد اگر و تنها اگر n-m راه وجود داشته باشد که هر رأس در G را پوشش می‌دهد و n تعداد رأس‌های G است. بنابراین مسئله‌ را می‌توان با پیدا کردن تطابق ماکسیمم در G' حل کرد.

تطابق بیشینه‌ی دوبخشی[ویرایش]

شکل 4.3.1. تبدیل یک مسئله‌ی تطابق بیشینه‌ی دوبخشی به مسئله‌ی بیشینه جریان.

برای پیدا کردن تطابق بیشینه (تطابقی که بیش‌ترین تعداد رأس‌های ممکن را دارد) در یک گراف دو بخشی G=(X \cup Y, E)، می‌توانیم مسئله را با ساختن شبکه‌ی N=(X \cup Y \cup \{s,t\}, E') به یک مسئله‌‌ی بیشینه جریان تبدیل کنیم، که:

  1. E' شامل یال‌هایی از G است که جهتشان از X به Y است.
  2. (s,x) \in E' برای هر x \in X و (y,t) \in E' برای هر y \in Y.
  3. c(e)=1 برای هر e \in E' (شکل 4.3.1 را ببینید).

آنگاه مقدار بیشینه جریان در N برابر اندازه‌ی تطابق ماکسیمم در G است.

مسئله‌‌ی بیشینه جریان با ظرفیت رأس[ویرایش]

شکل 4.4.1. تبدیل یک مسئله‌ی تطابق بیشینه‌ی جریان با شرط ظرفیت رأس‌ها به مسئله‌ی بیشینه جریان اصلی با بخش کردن رأس‌ها.

اگر شبکه‌ی N = (V, E) را داشته باشیم که در آن علاوه بر یال‌ها، هر رأس هم ظرفیت دارد، یعنی نگاشت c: V\mapsto \mathbb{R}^{+} که با c(v) نمایش داده می‌شود به طوری که جریان f علاوه بر شرط ظرفیت و بقای جریان‌ها، شرط ظرفیت رأس را هم داشته باشد:

 \sum_{i\in V} f_{iv} \le c(v) \qquad \forall v \in V \backslash \{s,t\}

به بیان دیگر مقدار جریانی که از یک رأس می‌گذرد نمی‌تواند از ظرفیت آن بیشتر باشد. برای یافتن ماکسیمم جریان در N می‌توان با گسترش N، مسئله را به یک مسئله‌‌ی بیشینه جریان تبدیل کرد. ابتدا هر v\in V با v_{\text{in}} و v_{\text{out}} جایگزین می‌شود که v_{\text{in}} متصل به یال‌هایی است که به V وارد می‌شود و v_{\text{out}} متصل به یال‌هایی است که از آن خارج می‌شوند، سپس ظرفیت c(v) را به یالی نسبت می‌دهیم که v_{\text{in}} و v_{\text{out}} را شامل می‌شود (شکل 4.4.1 را ببینید، ولی در نظر داشته باشید که جای v_{\text{in}} و v_{\text{out}} به اشتباه در آن جا‌به‌جا شده‌است). در این شبکه‌ی گسترش یافته، شرط ظرفیت رأس برداشته‌ شده است؛ بنابراین می‌توان با این مسئله مانند یک مسئله‌‌ی بیشینه جریان برخورد کرد.

بیشینه مسیر مستقل[ویرایش]

دو مسیر از هم مستقل‌ اند اگر به جز s و t رأس مشترکی نداشته باشند. برای پیدا کردن بیشینه تعداد راه‌های مستقل از دو رأس s به t در گراف جهت‌دار G=(V,E)، می‌توان از G دارای ظرفیت رأس، شبکه‌ی N=(V,E) را ساخت به طوری که:

  1. s و t به ترتیب مبدأ و مقصد N اند.
  2. c(v)=1 برای هر v \in V.
  3. c(e)=1 برای هر e \in E.

آنگاه مقدار بیشینه جریان برابر تعداد مسیر‌های مستقل از s به t است.

بیشینه مسیر یال‌مجزا[ویرایش]

برای پیدا کردن بیشینه تعداد مسیر‌های یال‌مجزا از رأس s به رأس t در گراف جهت دار G=(V,E)، می‌توان مسئله را با ساختن شبکه‌ی N=(V,E) از G با مبدأ s و مقصد t و نسبت دادن جریان واحد به هر یال، به یک مسئله‌ی بیشینه جریان تبدیل کرد.

بیشینه مسیر رأس‌مجزا[ویرایش]

برای پیدا کردن بیشینه تعداد مسیر‌های رأس‌مجزا از رأس s به رأس t در گراف جهت‌دار G=(V,E)، می‌توان مسئله را با ساختن شبکه‌ی N=(V,E) به صورت زیر، به یک مسئله‌ی بیشینه جریان تبدیل کرد:

  1. هر رأس v در گراف را به دو رأس v_{in} و v_{out} تقسیم کنید.
  2. برای هر رأس v یالی با ظرفیت یک از v_{in} به v_{out} اضافه کنید.
  3. هر یال (u,v) در گراف را با یالی از u_{out} به v_{in} با ظرفیت یک تعویض کنید.
  4. یک رأس مقصد اختصاصی جدید به نام t اضافه کنید.
  5. برای هر رأس v، یالی از v_{in} به t با ظرفیت یک اضافه کنید.
  6. یک بیشینه جریان از s_{out} به t پیدا کنید. مقدار جریان برابر تعداد مسیر‌های رأس‌مجزا است.

کاربردهای مسئله در دنیای واقعی[ویرایش]

بازی‌های حذفی بیسبال[ویرایش]

تشکیل شبکه‌ی جریان برای مسئله‌ی بازی‌های حذفی بیسبال.

در این مسئله، n تیم در یک لیگ به طور حذفی با یک‌دیگر مسابقه می‌دهند. در یک مرحله‌ی خاص، w_i تعداد برد‌ها، r_i تعداد بازی‌های باقی‌مانده برای تیم iام، و r_{ij} تعداد بازی‌های باقی‌مانده در مقابل تیم jام است. اگر تیمی شانس اول شدن از دست بدهد، از لیگ حذف خواهد شد. هدف این مسئله تعیین کردن تیم‌های حذف شده در هر زمان از فصل است. Schwartz برای این مسئله روشی پیشنهاد داد که این مسئله را به مسئله‌‌ی بیشینه‌ی جریان تبدیل می کند. در این روش شبکه‌ای ساخته می شود که تعیین می‌کند آیا تیم k حذف می‌شود یا نه.
فرض کنید گراف G=(V,E) شبکه‌ای با s,t \in V باشد که s و t به ترتیب مبدأ و مقصد را تعیین می‌کنند. یک رأس \{i,j\} را به طوری که i<j به گراف اضافه می‌کنیم و آن را با یالی با ظرفیت r_{ij} به s وصل می‌کنیم که تعداد بازی‌های بین دو تیم i و j را نشان می‌دهد. هم چنین برای هر تیم i یک رأس ایجاد می‌کنیم و هر رأس \{i,j\} را به رأس‌های i و j وصل می کنیم تا تضمین کنیم یکی از آن‌ها برنده می‌شود. برای این یال‌ها ظرفیتی تعیین نمی‌کنیم. در انتها، وزن یال بین تیم i و مقصد t را wk+rkwi قرار می‌دهیم تا تعداد برد‌های تیم i از wk+rk تجاوز نکند. مجموعه‌ی تیم‌های شرکت‌کننده در لیگ را S می‌نامیم و \scriptstyle r(S - \{k\}) = \sum_{i,j \in \{S-\{k\}\}, i < j} r_{ij}. ادعا می‌کنیم تیم k حذف نمی‌شود اگر و تنها اگر اندازه‌ی جریانی با مقدار r(S - \{k\}) در شبکه‌ی G وجود داشته باشد. در مقاله‌ی مذکور نشان داده شده که این مقدار همان مقدار بیشینه‌ی جریان از s به t است.

برنامه‌ریزی خطوط هوایی[ویرایش]

یکی از مسائل مهم در صنایع خطوط هوایی، برنامه‌ریزی برای خدمه‌ی پرواز است. مسائل برنامه‌ریزی در خطوط هوایی می‌تواند به عنوان کاربردی از تعمیم مسئله‌‌ی بیشینه‌ی جریان مطرح شود. ورودی مسئله، مجموعه‌ای از پرواز‌ها (F) است که شامل مکان و زمان پرواز‌های ورودی و خروجی است. در یک مدل از برنامه‌ریزی، هدف این است که یک برنامه‌ریزی عملی صورت گیرد به طوری که حد‌اکثر k خدمه فعالیت کنند.
برای حل این مسئله، از مدل متفاوتی از مسئله‌ی گردش به نام گردش کراندار استفاده می‌کنیم، که مدل کلی‌ای از مسئله‌‌ی جریان است که در آن برای حداقل جریان منحصر با یال‌ها محدودیت قائل می‌شویم.
G=(V,E) را یک شبکه با مبدأ و مقصد s,t \in V در نظر می‌گیریم. برای هر پرواز i، یک رأس s_i برای مبدأ و یک رأس d_i برای مقصد آن به V اضافه می‌کنیم. هم چنین یال‌های زیر را به E اضافه می‌کنیم:

  1. یال‌هایی با ظرفیت [0,1] بین s و هر s_i
  2. یال‌هایی با ظرفیت [0,1] بین هر d_i و t
  3. یال‌هایی با ظرفیت [0,1] بین هر جفت s_i و d_i
  4. یال‌هایی با ظرفیت [0,1] بین هر d_i و s_j، اگر بتوانیم با صرف هزینه و زمان معقول از d_i به s_j برسیم.
  5. یالی با ظرفیت [∞,0] بین s و t

در روش ذکر شده، ادعا و اثبات می‌شود که پیدا کردن یک جریان با مقدار k بین s و t در G، همان پیدا کردن برنامه‌ای عملی برای مجموعه‌ی پرواز‌های F با حداکثر k خدمه است.
نوع دیگری از برنامه‌ریزی خطوط هوایی، پیدا کردن حداقل خدمه برای انجام شدن تمامی پروازهاست. برای پیدا کردن جواب این مسئله، یک گراف دو قسمتی G'=(A \cup B, E) می‌سازیم که هر پرواز یک کپی در مجموعه‌ی A و مجموعه‌ی B دارد. اگر یک هواپیما بتواند پرواز j را بعد از پرواز i انجام دهد، i \in A به j \in B وصل می‌شود. یک تطابق در G' شامل یک برنامه برای F است و بدیهی است که حداکثر تطابق دوقسمتی در این گراف، یک برنامه‌ی هوایی با حداقل تعداد خدمه را نشان می‌دهد. همان‌طور که در قسمت کاربرد‌های این مقاله ذکر شد، پیدا کردن تطابق بیشینه دوبخشی یکی از کاربردهای مسئله‌ی بیشینه‌ی جریان است.

مسئله‌ی تقاضای گردش[ویرایش]

تعدادی کارخانه هستند که کالا تولید می‌کنند و تعدادی دهکده هستند که باید به آن‌ها کالا برسد. آن‌ها با شبکه‌ای از جاده‌ها به هم متصل اند که هر جاده ظرفیت c برای بیشینه کالایی که می‌تواند از آن بگذرد دارد. مسئله‌ یافتن این است که آیا گردشی وجود دارد که تقاضا را برآورده کند یا خیر. این مسئله‌ می‌تواند به یک مسئله‌‌ی بیشینه جریان تبدیل شود:

  1. یک رأس مبدأ (s) اضافه کنید و یال‌هایی از آن به هر رأس کارخانه ( f_i ) با ظرفیت تولید  p_i اضافه کنید، که  p_i آهنگ تولید کارخانه‌ی  f_i است.
  2. یک رأس مقصد (t) اضافه کنید و یال‌هایی از هر رأس دهکده ( v_i ) با ظرفیت  d_i به آن اضافه کنید، که  d_i میزان تقاضای دهکده است.

G=(V,E) این شبکه‌ی جدید است. گردشی وجود دارد که تقاضا را برآورده کند اگر و تنها اگر:
 Maximum flow value(G) =  \sum_{i \in v} d_i
اگر یک گردش وجود داشته باشد، مسئله‌‌ی بیشینه جریان جواب این که چه مقدار کالا برای برآورده شدن تقاضا باید از طریق یک جاده‌ی خاص فرستاده شود را به ما می‌دهد.

عدالت در اشتراک اتومبیل[ویرایش]

مسئله‌‌ این است که N نفر از یک ماشین در k روز به صورت اشتراکی استفاده می‌کنند. هر شرکت کننده می‌تواند در هر روز انتخاب کند که شرکت می‌کند یا خیر. هدف ما این است که عادلانه تصمیم بگیریم که در یک روز مشخص، چه کسی رانندگی می‌کند. راه حل به این صورت است:
می‌توانیم بر اساس تعداد افرادی که از ماشین استفاده می‌کنند تصمیم بگیریم، یعنی اگر m نفر از ماشین در یک روز استفاده می‌کنند، هر نفر به مقدار  1/m مسئولیت دارد؛ بنابراین برای هر شخص i، اجبار رانندگی ( D_i ) به صورتِ ذکر شده است. بنابراین، شخص i فقط باید  [D_i] بار در k روز رانندگی کند.
هدف این است که پی ببریم آیا چنین وضعیتی امکان‌پذیر است یا خیر. برای این منظور همان طور که در شکل نشان داده شده است، سعی می‌کنیم مسئله را به یک شبکه تبدیل کنیم.
حال می‌توان ثابت کرد که اگر جریان k وجود داشته باشد، آنگاه چنین وضعیت عادلانه‌ای و چنین جریانی با مقدار k همواره وجود دارد.

منابع[ویرایش]

  • مشارکت‌کنندگان ویکی‌پدیا، «Maximum flow problem»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۵ مه ۲۰۰۹).

جستارهای وابسته[ویرایش]

  • بیشینه جریان