بخشی از پاورپوینت
اسلاید 1 :
طراحي الگوريتم ها
Computer algorithms
برنامه ریزی پویا
اسلاید 2 :
فصل ششم
روش برنامه ریزی پویا در طراحی الگوریتم
اسلاید 3 :
Computer algorithms
مساله ضریب چند جمله ای
مساله فلوید
مساله فروشنده دورگرد
مساله درختهای جستجوی دودویی بهینه
مساله کوله پشتی صفر و یک
اسلاید 4 :
برنامه نویسی پویا،
نمونه به نمونه های کوچکتر تقسیم می شود
مشابه روش تقسیم و حل است
با این تفاوت نسبت به تقسیم وحل که: نخست نمونه های کوچک تر را حل می کنیم ، نتایج را ذخیره می کنیم و بعدا هر گاه به یکی از آن ها نیاز پیدا شد، به جای محاسبه دوباره کافی است آن را بازیابی کنیم.
اسلاید 5 :
نمایی
روش بالا به پایین
اسلاید 6 :
در مسائل بهینه سازی اگر مسئله را به روش تقسیم وحل و یا با روش بررسی تمام حالات انجام دهیم پیچیدگی نمایی و حتی در بعضی از مسائل بدتر از نمایی(n!) خواهد بود ولی با یافتن راه حل برنامه ریزی پویا زمان به n2 یا n3 تقلیل میکند اما در عوض باید از یک آرایه کمکی استفاده کرد
اسلاید 7 :
سه مولفه اصلی روش DP
رابطه بازگشتی موجود در مساله(به کمک این رابطه مقداری برای راه حل بهینه تعریف میکنیم)
ارائه یک ویژگی بازگشتی برای حل نمونه ای از مسئله
محاسبات جدولی
ردیابی جواب(برای چاپ راه حل بهینه)
اسلاید 8 :
مساله فیبوناتچی
استفاده از جدول برای کاهش میزان محاسبات مجدد
اسلاید 9 :
مساله فیبوناتچی به روش برنامه نویسی پویا
آرایه ذخیره نتایج
اسلاید 10 :
مساله ضریب دوجمله ای
اسلاید 11 :
روش تقسیم و حل مساله ضریب دوجمله ای
اسلاید 12 :
محاسبه C(5,2)
اسلاید 13 :
روش برنامه نویسی پویا مساله ضریب دوجمله ای
اسلاید 14 :
مساله ضریب دوجمله ای
آرایه B
اسلاید 15 :
مساله ضریب دوجمله ای
اسلاید 16 :
پیچیدگی زمان مساله ضریب دوجمله ای
اسلاید 17 :
مساله ضرب زنجیره ای از ماتریس ها
اسلاید 19 :
مساله ضرب زنجیره ای از ماتریس ها
پیچیدگی روش معمولی که بررسی تمام حالات است نمایی می باشد
tn : تعداد ترتیب های مختلف ضرب n ماتریس
اسلاید 20 :
ایده بهینه سازی مساله
