لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت برنامه نويسي پويا Dynamic programming توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت برنامه نويسي پويا Dynamic programming قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

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

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

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

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

ü

اسلاید ۲ :

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

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

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

اسلاید ۳ :

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

گام اول : مشخص كردن انواع روش هاي شكستن مسئله و ارائه اين موضوع در يك طرح درخت واره اي

ü اين فاز يكي از مهمترين فازها مي باشد و يك طرح واحد نيست ولي بهينه ترين در نظر گرفته مي شود .

گام دوم : كشف بهترين نوع تركيب زير مسائل كوچكتر

گام سوم : جلوگيري از محاسبات تكراري ، با طراحي يك جدول و ثبت جواب هر زير مسئله در آن در ادامه كار اگر آن زير مسئله دوباره تكرار شد از جدول استفاده مي كنيم .

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

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

اسلاید ۴ :

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

 مسئله اینست که ماتريس هاي زير را به چه روشي با یکدیگر ضرب كنيم تا كمترين هزينه ضرب و جمع را بپردازيم ؟

 M1 ×  M2 × M3 × … × Mn

مثال

فرض می کنیم چهار ماتريس داريم به طوري كه سطر و ستون آن به ترتيب زير باشد :

اسلاید ۵ :

 روشن است که روش هاي مختلف محاسبه ،  هزينه هاي مختلف را در بر دارد .

    به عنوان مثال :

((M1 × M2) × M3) × M4 =   (۲ × ۵ × ۳) + (۲ × ۳ × ۸) +(۲ × ۸ × ۱)

                                    =  ۳۰ + ۴۸ + ۱۶ = ۹۴

(M1 × M2) ×(M3 × M4)  =  (۲ × ۵ × ۳) +(۳ × ۸ × ۱) + (۲ × ۳ × ۱)

                                    =  ۳۰ + ۲۴ + ۶ = ۶۰

با توجه به مثال بالا تعداد كل حالات ضرب n ماتريس از رابطه ی بازگشتی ذیل محاسبه   می شود :

رياضيات رابطه بازگشتي بالا را حل كرده است.

اسلاید ۶ :

اگر n برابر ۴ باشد آنگاه عدد كاتالان برابر ۵ است. به عبارت ديگر تعداد كل حالات ممكن ضرب زنجيره اي ۴ ماتريس برابر ۵ است .

( (M1 × M2) × M3 ) × M4

( M1 × (M2 × M3) ) × M4

( M1 × M2 ) × ( M3 × M4 )

M1 × ( (M2 × M3) × M4 )

M1 × ( M2 × (M3 × M4) )

ü در این مسئله هدف یافتن بهینه ترین حالت ضرب است از نظر کمترین تعداد اعمال محاسباتی

اسلاید ۷ :

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

M11=M22=M33=M44=0

M12 = min ( M11 + M22 + 2 × ۵ × ۳)=۳۰

M23 = min ( M22 + M33 + 5 × ۳ × ۸)=۱۲۰

M34 = min ( M33 + M44 +3 × ۸ × ۱)=۲۴

M13 = min ( M11 + M23 + 2 × ۵ × ۸ , M12 + M33 + 2 × ۳ × ۸)

        = min (120+80 , 30+48) = min(200 , 78)=78

M24 = min ( M22 + M34 + 5 × ۳ × ۱ , M23 + M44 + 5 × ۸ × ۱)

        = min ( 24+15 , 120+40)=min(39 , 160)=39

 

M14 = min(M11 + M24 + 2×۵×۱,M12+M34 +2×۳×۱,M13+M44+ 2×۸ ×۱)          = min (39+10 , 30+24+6 , 78+16)=min(49,60,94)=49

اسلاید ۸ :

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

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

به عنوان مثال داريم :

آرايه ابعاد ماتريس ها :

A :

اسلاید ۹ :

 for (i=1 ; i<= n ; i++)

  m[i][i] = 0;

for (r=2 ; r<= n ; r++)

  for(c=r-1 ; c>=1 ; c–)

  {

  min = 99999 ; // +∞

  for (k=c ; k<r ; k++)

  {

        if (m[c][k]+m[k+1][r]+ A[c-1]*A[k]*A[r] < min)

  min = m[c][k]+m[k+1][r]+ A[c-1]*A[k]*A[r];

  m[c][r]= min;

  }

  }

اسلاید ۱۰ :

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

هزينه حافظه اي :

—با توجه به ساختارهاي حافظه اي استفاده شده داريم :

هزينه حافظه اي = هزينه آرايه دوبعدي ساختار حافظه اي + حافظه يك بعدي ابعاد ماتريس ها

 

هزينه زماني:

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