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

نوع فایل: power point

قابل ویرایش 26 اسلاید

قسمتی از اسلایدها:

در جلسات قبل گفته شد که روش تقسيم و حل يك روش از بالا به پايين است.

در اين روش مسئله با سايز ورودي n را به انواع زير مسائل مي شكنيم ( انواع روش هاي شكستن را آزمايش مي كنيم ) . این شکستن را ادامه می دهیم تا به مرحله ای برسیم که مسئله دیگر قابل شکستن نباشد و یا پاسخ بدیهی به نظر برسد .

  معمولا با كوچك ترين و در نتيجه ساده ترين نمونه حل را آغاز مي كنيم . سپس از تركيب حل نمونه هاي كوچك تر حل نمونه هاي بزرگ تر به دست مي آيد و اين روند ادامه مي يابد تا سرانجام حل نمونه اصلي يا كامل حاصل شود .

  اين روش زماني مفيد است كه معيار حريصانه ای وجود نداشته باشد و مسئله اصلي قابل شكستن باشد .

انواع شكستن مسئله باعث مي شود كه تعدادي زير مسائل تكراري توليد شود . هزينه حل يا محاسبه اين تعداد از مرتبه نمايي است .

در روش برنامه نويسي پويا براي كاهش اين مرتبه زماني هر زير مسئله در حافظه نگهداري شده و در مواقع توليد، زير مسائل تكراري ديگر حل    نمي شوند و تنها عمل واكشي اطلاعات صورت مي گيرد .

تفاوت اصلي بين روش حريصانه و برنامه نويسي پويا آن است كه در روش حريصانه فقط يك مجموعه ي انتخا ب ها ( جوابها ) توليد مي شود در حالي كه در برنامه نويسي پويا ممكن است مجموعه ي زيادي از انتخاب ها  ( جوابها ) توليد شود.هر چند كه مجموعه هاي شامل زير مجموعه هاي بهينه نمي تواند بهينه باشند ( اگر اصل بهينه سازي برقرار باشد ) و  بنا براين تا حد امكان نبايد توليد شوند .

فهرست مطالب و اسلایدها:

حل مسئله به روش برنامه نويسي پويا

ضرب زنجیره ای ماتریس ها

گام  اول : نحوه ی شکستن مسئله یا طرح درخت واره ای

گام دوم : نحوه ترکیب یا محاسبه ی هزینه ضرب در طرح درخت واره ای

گام سوم : جلوگیری از محاسبات تکراری با طراحی جدول

گام چهارم  : پياده سازي

پياده سازي برنامه

گام پنجم: هزينه زماني/ حافظه اي

محاسبه جمله nام دنباله فیبوناتچی

درخت بهينه B.S

هزينه جستجو در درخت جستجوی دودويي با تكرار

نحوه شكستن مسئله (طرح درخت واره اي)

ساختار حافظه ای

نتیجه