حسام حداد

در مورد برنامه نویسی ، الگوریتم نویسی ، نکات ترفند ها

حسام حداد

در مورد برنامه نویسی ، الگوریتم نویسی ، نکات ترفند ها

در این وبلاگ شخصی نکته ها ، راهکار ها و مطالب جدید برنامه نویسی قرار میگیرد.
نویسنده کلیه مطالب شخص حسام حداد میباشد و خواهشمند است حق کپی را رعایت کنید.

آخرین نظرات
  • ۱۸ آبان ۹۵، ۱۲:۵۱ - سامان
    ای ول

۴ مطلب با موضوع «درسنامه الگوریتم ها» ثبت شده است

مقدمه
یکی از الگوریتم های ساده که معمولا در درس ساختمان گسسته، طراحی الگوریتم و ساختمان داده به صورت پایه مطرح می شود الگوریتم فلوید وارشال می باشد. این الگوریتم با مرتبه O(N3) شاید یکی از بدترین انتخاب ها برای حل مسئله به علت کندی بیش از حد باشد. اما وقتی تعداد نود به اندازه کوچکتر از 200 باشد تفاوت قابل توجه ای با الگوریتم های خوب جایگزین ندارد و به علت پیاده سازی ساده و سریع این الگوریتم همیشه اگر در محدودیت های مساله قابل استفاده باشد جایگزین بقیه کاندید ها می شود.
رابرت فلوید و استفان وارشال همزمان باهم در مقالات مختلف در سال 1962 این الگوریتم را منتشر کردند، و به افتخارشان الگوریتم فلوید-وارشال نام گرفت که به اختصار به آن فلوید نیز گفته می شود، رابرت فلوید دارای یک الگوریتم خوب دیگر برای پیدا کردن دور در لیست پیوندی یا روابط بازگشتی بر اساس مقدار قبلی می باشد که باز با اسم الگوریتم فلوید مشهور است اما به اندازه این الگوریتم اعمال تعدی معروف نیست.
دلیل من برای انتخاب این الگوریتم برای بخش درسنامه الگوریتم ها، روزمره و ساده بودن الگوریتم فلوید بود که با توجه به بازدید های وبلاگ بنظر می رسد دانشجو های زیادی در طول ترم نیاز به مطالعه و استفاده از این الگوریتم دارند.

  • حسام حداد

مقدمه مترجم

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


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


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

  • حسام حداد

مقدمه

بسیاری از مسائل برنامه نویسی تنها با استفاده از Dynamic Programming حل میشوند در این نوشتار سعی شده که طرح کلی برنامه نویسی پویا و دلیل و مزایای استفاده از آن با چندین پیاده سازی برای تابع Fibonacci بیان شود. در مطالب آینده مثال های مهم تر و به نسبت پیچیده تری قرار میگیرد.


برنامه نویسی پویا یا Dynamic Programming چیست ؟

همه شما کم و بیش با الگوریتم ها یا برنامه هایی که به صورت بازگشتی عمل میکنند اطلاع دارید. حل یک مسئله با حل کردن یک یا چندین زیر مسئله .

در استفاده از تکنیک برنامه نویسی پویا ما حل مسئله را توسط حل مسئله های کوچکتر بیان میکنیم با این تفاوت که با ذخیره سازی از محاسبه دوباره اجتناب میکنیم.

  • حسام حداد

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

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

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

گراف نمونه

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

  • حسام حداد