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

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

نوع فایل: power point

فرمت فایل: pptx

قابل ویرایش

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

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

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