دسته : پاورپوینت برنامه نويسی پويا (Dynamic Programming) در 52 اسلاید زیبا و قابل ویرایش با فرمت pptx
فهرست مطالب
برنامه نويسی پويا (Dynamic Programming)
ويژگيها
اصل بهينگی principle of optimality
مسأله به دست آوردن ضريب دوجمله ای
به دست آوردن ضريب دوجمله ای با روش تقسيم و حل
به دست آوردن ضريب دوجمله ای با روش برنامه سازی پويا
آرايه B برای محاسبه ضريب دو جمله ای
الگوريتم محاسبه ضريب دوجمله ای با روش برنامه سازی پويا
حل مسأله
جدول زيرمسائل حل شده برای ضرب چهار ماتريس
الگوريتم تعيين تعداد حداقل ضربهای مورد نياز
مسائل قابل بررسی
مسأله کوتاهترین مسیر
تولید جدول D
مراحل حل با استفاده از برنامه نويسی پویا
نحوه اجرای الگوریتم
الگوریتم فلوید برای کوتاهترین مسیرها
نمایش کوتاهترین مسیر
مسأله فروشنده دوره گرد
حل با روش برنامه سازی پویا
تحلیل پیچیدگی زمانی الگوریتم فروشنده دوره گرد
مسأله کوله پشتی
حل کوله پشتی 1-0 با روش برنامه سازی پویا
مراحل حل مسأله
تحلیل پیچیدگی زمان و حافظه
قسمتی از متن
مشابه روش تقسيم و حل, مسأله را به نمونه های کوچکتر تقسيم می کند.
ابتدا نمونه های کوچکتر را حل کرده و نتايج را ذخيره می کند. در صورت نياز به جای محاسبه مجدد آن را بازيابی می کند.
يک روش پايين به بالا است.
برخلاف روش تقسيم و حل, نمونه های کوچکتر به هم مرتبطند.
زمانی که مسأله ها, زيرمسائل مشترکی داشته باشند الگوريتم تقسيم و حل بيشتر از حد نياز کار می کند و زير مسائل مشترک را چندين بار حل می کند.
ويژگيها
بهينه سازی: در اغلب الگوريتمهای برنامه سازی پويا, تنها به دست آوردن جواب مهم نيست و بايد جواب بهينه نيز باشد. مسأله بهينه سازی در حل مسائل کليه سطوح بايد اعمال گردد.
برخلاف مسائل تقسيم و حل که برای حل هر مسأله سطح L تنها از مسائل سطح L-1 استفاده می کند, در روش برنامه سازی پويا می توان از کليه مسائل سطوح پايين تر استفاده کرد.
در هر سطح, کليه مسائل آن سطح حل می گردند و نگهداری می شوند.
اصل بهينگی principle of optimality
اصل بهينگی در صورتی برقرار است که در هر رشته از تصميمات بهينه, هرزير رشته از اين تصميمات نيز بهينه باشند.
مثال: مسأله کوتاهترين مسير در گراف