پاورپوینت برنامه نویسی پویا (Dynamic Programming)

لینک دانلود و خرید پایین توضیحات

دسته بندی : پاورپوینت

نوع فایل :  .ppt ( قابل ویرایش و آماده پرینت )

تعداد اسلاید : 52 اسلاید

 قسمتی از متن .ppt : 

dynamic programming

1

برنامه نویسی پویا (Dynamic Programming)

مشابه روش تقسیم و حل, مسأله را به نمونه های کوچکتر تقسیم می کند.

ابتدا نمونه های کوچکتر را حل کرده و نتایج را ذخیره می کند. در صورت نیاز به جای محاسبه مجدد آن را بازیابی می کند.

یک روش پایین به بالا است.

برخلاف روش تقسیم و حل, نمونه های کوچکتر به هم مرتبطند.

زمانی که مسأله ها, زیرمسائل مشترکی داشته باشند الگوریتم تقسیم و حل بیشتر از حد نیاز کار می کند و زیر مسائل مشترک را چندین بار حل می کند.

dynamic programming

2

ویژگیها

بهینه سازی: در اغلب الگوریتمهای برنامه سازی پویا, تنها به دست آوردن جواب مهم نیست و باید جواب بهینه نیز باشد. مسأله بهینه سازی در حل مسائل کلیه سطوح باید اعمال گردد.

برخلاف مسائل تقسیم و حل که برای حل هر مسأله سطح L تنها از مسائل سطح L-1 استفاده می کند, در روش برنامه سازی پویا می توان از کلیه مسائل سطوح پایین تر استفاده کرد.

در هر سطح, کلیه مسائل آن سطح حل می گردند و نگهداری می شوند.

dynamic programming

3

اصل بهینگی principle of optimality

اصل بهینگی در صورتی برقرار است که در هر رشته از تصمیمات بهینه, هرزیر رشته از این تصمیمات نیز بهینه باشند.

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

مراحل تولید الگوریتم برنامه نویسی پویا

1- مشخص کردن ساختار جواب بهینه

2- ارائه یک رابطه بازگشتی برای حل مسأله

3- حل یک نمونه مسأله به روش پایین به بالا و با شروع از حل نمونه های کوچکتر

4- ساختن یک جواب بهینه از روی اطلاعات محاسبه شده

dynamic programming

4

مسأله به دست آوردن ضریب دوجمله ای

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

k

n-1 + n-1 0<k<n

n = k-1 k

k

1 k=0 یا k=n