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

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

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

نوع فایل: power point

فرمت فایل: pptx

قابل ویرایش

تعداد اسلاید : 26 صفحه

قسمتی از پاورپوینت :

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