آموزش طراحی و تحلیل الگوریتم قسمت پنجم

--- 1395/1/18 1595

آموزش طراحی و تحلیل الگوریتم قسمت پنجم

در جلسه ی گذشته ، درباره ی روش و روند تقسیم و حل صحبت کردیم و چند الگوریتم مهم در این روش رو با هم دیدیم . اما قصد داریم در این جلسه ، درباره ی برنامه ریزی پویا با هم صحبت کنیم .

تکنیک برنامه ریزی پویا تا حدی شبیه روش تقسیم و حل هست . چون میاد یک نمونه از مسئله رو به نمونه های کوچک تر تبدیل میکنه .. ولی توی این روش ، اول از همه نمونه های کوچیک رو حل میکنیم و سپس نتایج اونهارو ذخیره می کنیم و به این ترتیب در صورت نیاز به اونها در مراحل بعدی ، از اونها استفاده میکنیم . در برنامه ریزی پویا ، حل یک مسئله به صورت پایین به بالا هست در صورتی که در روش تقسیم و حل ، مسائل به صورت بالا به پایین بررسی می شدند . پس ما در برنامه ریزی پویا باید یک ویژگی بازگشتی در نمونه ی مسئله پیدا کنیم و سپس با استفاده از اون و به روش پایین به بالا کل مسئله رو حل کنیم .

رای اینکه بهتر با این روش آشنا بشیم ، میریم سراغ یک الگوریتم کاربردی .

این الگوریتم ضریب دو جمله ای هست . ضریب دو جمله ای به صورت زیر هست :

C(n,k)= n!/k!(n-k)!          0<= k =< n

البته این تعریف نسبتا خوبی از ضریب دو جمله ای هست ولی خب اگه n و  k خیلی بزرگ باشن ، شاید خیلی سخت بشه از این فرمول استفاده کرد . برای همین میتونیم از روابط دیگری هم استفاده کنیم .

آموزش قسمت پنجم طراحی و تحلیل الگوریتم

این رابطه ی بالا ، اساس الگوریتم بازگشتی برای محاسبه  ی ضریب دو جمله ای هست . این الگوریتم جزء روش تقسیم و حل محسوب میشه :

الگوریتم ضریب دو جمله ای به روش بازگشتی

کارایی این الگوریتم بسیار کم هست .. دقیقا شبیه الگوریتم بازگشتی برای محاسبه ی جمله ی n ام دنباله ی فیبوناچی که دارای پیچیدگی زمانی نامناسبی بود . مشکل هم تا حدی مشابه هست . توی چنین الگوریتم هایی ممکنه یک نمونه چندین بار به طور جداگانه محاسبه بشه . و همین امر میتونه باعث کاهش شدید کارایی الگوریتم بشه .

اما حالا همین رو میخوایم با استفاده از برنامه ریزی پویا توضیح بدیم . ایده ی ما تقریبا مثل الگوریتم بازگشتی هست ولی سعی میکنیم ماتریسی تعریف کنیم مثل M به طوریکه M[i][j] حاوی C(i,j) باشه .

پس اول یک ویژگی بازگشتی تعریف می کنیم . دقیقا همون ویژگی که در الگوریتم بازگشتی دیده شد .

آموزش قسمت پنجم طراحی و تحلیل الگوریتم

حالا کافیه ماتریس رو به شیوه ی پایین به بالا پر کنیم . یعنی با شروع از سطر صفرم . اگر دقت کنیم در این ماتریس میبینم که مثلت خیام _پاسکال در حال شکل گیری هست . هرکدوم از سطر ها هم از روی سطر قبلیشون در حال ساخته شدن هستن . اگر ماتریس خودمون رو nXk در نظر بگیریم ، عنصر M[n][k] همون C(n,k)  خواهد بود . برای اینکه این موضوع رو متوجه بشیم یک مثال میگیم و بعد میریم سراغ الگوریتمش .

مثلا فرض کنید که بخوایم C(3,2) رو حساب کنیم . خب میایم شروع میکنیم به  دست آوردن درایه های ماتریس از سطر صفرم .

M[0][0]= 1

M[1][0]=1

M[1][1]=1

M[2][0]=1

M[2][1]=M[1][0]+M[1][1]=1+1=2

M[2][2]=1

M[3][0]=1

M[3][1]=M[2][0]+M[2][1]=1+2=3

M[3][2]=M[2][1]+M[2][2]=2+1=3

 

پس جواب برابر با 3 هست .

 

البته دو نکته رو باید گفت:

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

نکته ی دیگه هم اینکه ما گفتیم ماتریس باید تشکیل بدیم . اما احتم

الا متوجه شدید که این ماتریس کاملا پر نمیشه . این یک ماتریس تقریبا پایین مثلثی هست . و ما اصلا با برخی از درایه ها کاری نداریم .

بریم سراغ الگوریتم :

الگوریتم ضریب دو جمله ای برنامه ریزی پویا

در این روش هر نمونه ی کوچکتر فقط یکبار محاسبه میشه و راه رو برای محاسبه ی نمونه های بزرگتر هموار میکنه . پیچیدگی این الگوریتم از مرتبه ی nk هست .

یک الگوریتم معروف برای روش برنامه ریزی پویا هم الگوریتمی به نام "فلوید " هست .  هدف این الگوریتم یافتن کوتاهترین مسیر بین دو نقطه هست . یکی از کاربرد های این الگوریتم هم در زمینه ی حمل و نقله و یکی از بهترین موضوعاتی هم که میشه از اون برای فهم بهتر این الگوریتم استفاده کرد ، مبحث گرافه . ما اینجا فقط به بیان الگوریتم و پیچیدگی اون می پردازیم.

الگوریتم فلوید

الگوریتم فلوید

پیچیدگی این الگوریتم هم به واسطه ی وجود 3 حلقه ی تو در تو برابر با n به توان 3 خواهد بود .

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

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

بهینگی رو به صورت یک اصل هم بیان میکنن که مفهومش اینه :

اصل بهینگی در یک مسئله صدق می کند اگر یک حل بهینه برای نمونه ای از مسئله ، همواره حاوی حل بهینه برای همه ی زیر نمونه ها باشد .

خب دوستان عزیز برای جلسه ی امروز کافیه

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

ممنون از توجه شما و خدانگهدار

قسمت بعدی قسمت قبلی