الگوریتم حریصانه :: حسام حداد

فیلتر مطالب ۴ مطلب با کلمه‌ی کلیدی «الگوریتم حریصانه» ثبت شده است حذف فیلتر

الگوریتم بیشینه جریان و کمینه برش Maximoum Flow Minimoum Cut

مقدمه مترجم

الگوریتم Maximoum Flow Minimoum Cut یکی از الگوریتم های کاربردی است که معمولا در چالش های متوسط و سطح بالا برنامه نویسی ظاهر میشود از کاربرد های این الگوریتم میتوان به برنامه ریزی خطوط هوایی برای عدم تداخل اشاره کرد و همچنین مسائلی که میتوان با چند مدل سازی از ورودی مسئله را با یک مسئله بیشینه جریان تبدیل کرد در سوالات مسابقات داخلی از جمله مسابقات منطقه ای غرب‌ آسیا (‌صنعتی شریف)‌ و مسابقه داخلی دانشگاه امیرکبیر دیده شده است. این مقاله از بخش الگوریتم های TopCoder ترجمه شده و اولین مقاله غیر تالیفی منتشر شده در این وبلاگ محسوب میشود. قسمت پیشرفته تر این الگوریتم نیز در اسرع وقت ترجمه شده و منتشر میشود. لینک مقاله انگلیسی

مقدمه نویسنده
این مقاله مسئله ای را پوشش میدهد که معمولا در زندگی روزمره و طبق انتظار در چالش های برنامه نویسی رخ میدهد و مسابقات TopCoder نیز در این مورد استثنا نیست. مقاله بیشتر برای برنامه نویسانی که با موضوع آشنایی ندارند نوشته شده اما میتواند برای با تجربه ها نیز مفید واقع شود. مقالات زیادی در این رابطه نوشته شده و الگوریتم های شناخته شده زیادی نیز برای حل این مسئله وجود دارد. الگوریتمی که در اینجا ارائه میشود با اینکه سریعترین نیست اما سودهایی مثل سادگی و کارآمدی دارد. و به خاطر این دو معمولا ترجیح داده میشود. توصیه میشود که خواننده پیش از ادامه مقاله ای را در زمینه نظریه گراف ها مطالعه کند زیرا مفاهیمی که در نظریه گراف ها مطرح میشود پیشنیاز درک مفاهیمی که اینجا مطرح میشود میباشد.

مسئله استاندارد بیشینه جریان Maximum Flow Problem
وقتی به یک مسئله بیشینه جریان بر میخوریم ساده ترین حالت صورت مسئله میتواند به این شکل باشد: " با داشتن لیستی از لوله ها با شدت جریان متفاوت که از انتها به هم وصل شده اند. مقدار بیشینه ای از آب که میتوان از یک نقطه شروع به یک نقطه پایان منتقل کرد چقدر است؟" یا به صورت "شرکتی دارای خط تولیدی در شهر X میباشد که نیاز است محصولاتش به شهر Y منتقل شود. به شما راه های یک طرفه ای داده شده است که هر یک دو شهر از کشور را با یک بیشینه تعداد کامیون عبوری به هم متصل میکند. بیشترین تعداد کامیونی که شرکت میتواند از آنها برای انتقال محصولات استفاده کند چقدر است؟"

ادامه مطلب

آموزش DP Bitmask با حل UVA 10911

مقدمه
پیش از این برنامه نویسی پویا را مطرح کرده بودیم، امروز یک سبک از برنامه نویسی پویا به اسم Bitmask را به همراه حل مسئله شماره 10911 از UVA مطرح میکنیم، که به نسبت مسئله ساده ای هست. وقتی که بحث پیاده سازی مجموعه ها در میان باشد Bit Mask ها مطرح میشوند.

خلاصه مسئله
در این مسئله که میتوانید جزیاتش را از اینجا بخوانید تعدادی دانشجو برای انجام یک تمرین میبایست به تیم های دوتایی تقسیم بشوند، ورودی مسئله N با شرط کوچک تر بودن از 9، و همچنین موقعیت 2N دانشجو هست هدف مسئله مینیمم سازی مجموع فاصله دو عضو هر تیم هست. ابتدا ممکن است راه حل های حریصانه در شرایط این مسئله درست به نظر برسند. برای مثال هر دانشجو را با نزدیک ترین دانشجو انتخاب نشده جفت کنیم. اما به راحتی میتوان با مثال های نقض پاسخگویی الگوریتم حریصانه را زیر سوال برد. همچنین تبدیل این گراف به یک گراف دو بخشی اشتباه بوده زیرا محدودیتی برای انتخاب همکار یک دانشجو وجود ندارد.
ادامه مطلب

The Importance of Algorithms

Guilan Faculty of Engineering
Hesam Haddad

Today we are going to be talking about the Importance of Algorithms in Programming and providing their usage, optimization after definitions.
The main propose of this is to help you have a clear view of algorithms or some basic knowledge.

What’s An Algorithm?
Algorithms are sets of rules to be followed in calculation or other problem solving by computer.

Runtime Analysis
After The correctness of an algorithm to solve all the test cases, the most important thing is runtime.
Computer Scientists typically talk about the runtime relative to the size of input. If the input consists of N integers, an algorithm witch has a runtime proportion to N² represent as O(N²) means that this algorithm terminate and complete after doing N² operations.

ادامه مطلب

الگوریتم حریصانه چیست؟ ( همراه با حل نمونه مثال ICPC ACM)

الگوریتم حریصانه چیست؟
الگوریتم حریصانه یا آزمند الگوریتمی است که مبنای آن بر انتخاب عنصر یا مسیری که در هر مرحله بهترین به نظر میرسد بدون توجه به انتخاب های قبل یا بعد میباشد. قبل پیاده سازی این الگوریتم باید ابتدا اثبات کنیم که بهترین انتخاب در هر مرحله به طور کلی بهترین انتخاب میباشد در غیر این صورت به جواب نادرستی میرسیم برای مثال نمیتوانیم در مسئله کوتاه ترین فاصله بین دو گره در گراف از الگوریتم حریصانه استفاده کنیم .

کجا نمیتوان از الگوریتم حریصانه استفاده کرد؟

گراف بدون جهت زیر را در نظر بگیرید.

برای پیدا کردن کوتاه ترین مسیر بین گره A و D اگر به صورت حریصانه عمل کنیم یال A-C از یال A-B دارای وزن کمتری میباشد پس یال A-C را در نظر میگیریم ولی در ادامه مجبوریم از تنها انتخاب یعنی C-D استفاده کنیم و به گره D برسیم. طول مسیر 9 + 15 یعنی 24 میباشد اما در صورتی که در ابتدا یال A-B را انتخاب کرده بودیم با اینکه نسبت به A-C در مرحله اول انتخاب بدتری بود اما در ادامه مسیر بهینه تر و کوتاه تری را داشتیم.
پس نمیتوان از الگوریتم حریصانه در پیدا کردن کوتاه ترین میسر بین دو گره استفاده کرد برای اینکار میتوان از الگوریتم هایی مثل Dijkstra استفاده کرد که به این مقاله مربوط نمیشود.
اما باید بدانیم که اگر در مسئله ای الگوریتم حریصانه درست باشد بی شک بهترین راه حل برای آن مسئله حریصانه است چون نسبت به بقییه الگوریتم ها دارای پیچیده گی زمانی کمتری میباشد.
ما بنا بر روال همیشگی امروز یک مسئله ICPC – ACM را برای مثال انتخاب کرده ایم که در حل آن از الگوریتم حریصانه میتوان استفاده کرد.
ابتدا متن سوال را مرور میکنیم

ادامه مطلب