DemoVersion
مقدمه مترجم
الگوریتم Maximoum Flow Minimoum Cut یکی از الگوریتم های کاربردی است که معمولا در چالش های متوسط و سطح بالا برنامه نویسی ظاهر میشود از کاربرد های این الگوریتم میتوان به برنامه ریزی خطوط هوایی برای عدم تداخل اشاره کرد و همچنین مسائلی که میتوان با چند مدل سازی از ورودی مسئله را با یک مسئله بیشینه جریان تبدیل کرد در سوالات مسابقات داخلی از جمله مسابقات منطقه ای غرب آسیا (صنعتی شریف) و مسابقه داخلی دانشگاه امیرکبیر دیده شده است. این مقاله از بخش الگوریتم های TopCoder ترجمه شده و اولین مقاله غیر تالیفی منتشر شده در این وبلاگ محسوب میشود. قسمت پیشرفته تر این الگوریتم نیز در اسرع وقت ترجمه شده و منتشر میشود. لینک مقاله انگلیسیمقدمه نویسنده
این مقاله مسئله ای را پوشش میدهد که معمولا در زندگی روزمره و طبق انتظار در چالش های برنامه نویسی رخ میدهد و مسابقات TopCoder نیز در این مورد استثنا نیست. مقاله بیشتر برای برنامه نویسانی که با موضوع آشنایی ندارند نوشته شده اما میتواند برای با تجربه ها نیز مفید واقع شود. مقالات زیادی در این رابطه نوشته شده و الگوریتم های شناخته شده زیادی نیز برای حل این مسئله وجود دارد. الگوریتمی که در اینجا ارائه میشود با اینکه سریعترین نیست اما سودهایی مثل سادگی و کارآمدی دارد. و به خاطر این دو معمولا ترجیح داده میشود. توصیه میشود که خواننده پیش از ادامه مقاله ای را در زمینه نظریه گراف ها مطالعه کند زیرا مفاهیمی که در نظریه گراف ها مطرح میشود پیشنیاز درک مفاهیمی که اینجا مطرح میشود میباشد.
مسئله استاندارد بیشینه جریان Maximum Flow Problem
وقتی به یک مسئله بیشینه جریان بر میخوریم ساده ترین حالت صورت مسئله میتواند به این شکل باشد: " با داشتن لیستی از لوله ها با شدت جریان متفاوت که از انتها به هم وصل شده اند. مقدار بیشینه ای از آب که میتوان از یک نقطه شروع به یک نقطه پایان منتقل کرد چقدر است؟" یا به صورت "شرکتی دارای خط تولیدی در شهر X میباشد که نیاز است محصولاتش به شهر Y منتقل شود. به شما راه های یک طرفه ای داده شده است که هر یک دو شهر از کشور را با یک بیشینه تعداد کامیون عبوری به هم متصل میکند. بیشترین تعداد کامیونی که شرکت میتواند از آنها برای انتقال محصولات استفاده کند چقدر است؟"
