بخشی از پاورپوینت
اسلاید 1 :
در جلسات قبل گفته شد که روش تقسيم و حل يك روش از بالا به پايين است.
در اين روش مسئله با سايز ورودي n را به انواع زير مسائل مي شكنيم ( انواع روش هاي شكستن را آزمايش مي كنيم ) . این شکستن را ادامه می دهیم تا به مرحله ای برسیم که مسئله دیگر قابل شکستن نباشد و یا پاسخ بدیهی به نظر برسد .
معمولا با كوچك ترين و در نتيجه ساده ترين نمونه حل را آغاز مي كنيم . سپس از تركيب حل نمونه هاي كوچك تر حل نمونه هاي بزرگ تر به دست مي آيد و اين روند ادامه مي يابد تا سرانجام حل نمونه اصلي يا كامل حاصل شود .
اين روش زماني مفيد است كه معيار حريصانه ای وجود نداشته باشد و مسئله اصلي قابل شكستن باشد .
اسلاید 2 :
انواع شكستن مسئله باعث مي شود كه تعدادي زير مسائل تكراري توليد شود . هزينه حل يا محاسبه اين تعداد از مرتبه نمايي است .
در روش برنامه نويسي پويا براي كاهش اين مرتبه زماني هر زير مسئله در حافظه نگهداري شده و در مواقع توليد، زير مسائل تكراري ديگر حل نمي شوند و تنها عمل واكشي اطلاعات صورت مي گيرد .
تفاوت اصلي بين روش حريصانه و برنامه نويسي پويا آن است كه در روش حريصانه فقط يك مجموعه ي انتخا ب ها ( جوابها ) توليد مي شود در حالي كه در برنامه نويسي پويا ممكن است مجموعه ي زيادي از انتخاب ها ( جوابها ) توليد شود.هر چند كه مجموعه هاي شامل زير مجموعه هاي بهينه نمي تواند بهينه باشند ( اگر اصل بهينه سازي برقرار باشد ) و بنا براين تا حد امكان نبايد توليد شوند .
اسلاید 3 :
حل مسئله به روش برنامه نويسي پويا
گام اول : مشخص كردن انواع روش هاي شكستن مسئله و ارائه اين موضوع در يك طرح درخت واره اي
اين فاز يكي از مهمترين فازها مي باشد و يك طرح واحد نيست ولي بهينه ترين در نظر گرفته مي شود .
گام دوم : كشف بهترين نوع تركيب زير مسائل كوچكتر
گام سوم : جلوگيري از محاسبات تكراري ، با طراحي يك جدول و ثبت جواب هر زير مسئله در آن در ادامه كار اگر آن زير مسئله دوباره تكرار شد از جدول استفاده مي كنيم .
گام چهارم : پياده سازي برنامه
گام پنجم : تحليل زماني / حافظه اي
اسلاید 4 :
ضرب زنجیره ای ماتریس ها
مسئله اینست که ماتريس هاي زير را به چه روشي با یکدیگر ضرب كنيم تا كمترين هزينه ضرب و جمع را بپردازيم ؟
M1 × M2 × M3 × … × Mn
مثال
فرض می کنیم چهار ماتريس داريم به طوري كه سطر و ستون آن به ترتيب زير باشد :
اسلاید 5 :
روشن است که روش هاي مختلف محاسبه ، هزينه هاي مختلف را در بر دارد .
به عنوان مثال :
((M1 × M2) × M3) × M4 = (2 × 5 × 3) + (2 × 3 × 8) +(2 × 8 × 1)
= 30 + 48 + 16 = 94
(M1 × M2) ×(M3 × M4) = (2 × 5 × 3) +(3 × 8 × 1) + (2 × 3 × 1)
= 30 + 24 + 6 = 60
با توجه به مثال بالا تعداد كل حالات ضرب n ماتريس از رابطه ی بازگشتی ذیل محاسبه می شود :
رياضيات رابطه بازگشتي بالا را حل كرده است.
اسلاید 6 :
اگر n برابر 4 باشد آنگاه عدد كاتالان برابر 5 است. به عبارت ديگر تعداد كل حالات ممكن ضرب زنجيره اي 4 ماتريس برابر 5 است .
( (M1 × M2) × M3 ) × M4
( M1 × (M2 × M3) ) × M4
( M1 × M2 ) × ( M3 × M4 )
M1 × ( (M2 × M3) × M4 )
M1 × ( M2 × (M3 × M4) )
در این مسئله هدف یافتن بهینه ترین حالت ضرب است از نظر کمترین تعداد اعمال محاسباتی
اسلاید 7 :
گام دوم : نحوه ترکیب یا محاسبه ی هزینه ضرب در طرح درخت واره ای
M11=M22=M33=M44=0
M12 = min ( M11 + M22 + 2 × 5 × 3)=30
M23 = min ( M22 + M33 + 5 × 3 × 8)=120
M34 = min ( M33 + M44 +3 × 8 × 1)=24
M13 = min ( M11 + M23 + 2 × 5 × 8 , M12 + M33 + 2 × 3 × 8)
= min (120+80 , 30+48) = min(200 , 78)=78
M24 = min ( M22 + M34 + 5 × 3 × 1 , M23 + M44 + 5 × 8 × 1)
= min ( 24+15 , 120+40)=min(39 , 160)=39
M14 = min(M11 + M24 + 2×5×1,M12+M34 +2×3×1,M13+M44+ 2×8 ×1) = min (39+10 , 30+24+6 , 78+16)=min(49,60,94)=49
اسلاید 8 :
گام چهارم : پياده سازي
براي پياده سازي طرح و ساختار حافظه اي مطرح شده ( براي نگهداري عناصر تكراري ) نياز به يك آرايه دو بعدي جهت ذخيره كردن حالت بهينه در هر گذر و همچنين نياز به يك آرايه يك بعدي جهت نگهداري ابعاد ماتريس ها داريم :
به عنوان مثال داريم :
آرايه ابعاد ماتريس ها :
A :
اسلاید 9 :
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;
}
}
اسلاید 10 :
گام پنجم: هزينه زماني/ حافظه اي
هزينه حافظه اي :
با توجه به ساختارهاي حافظه اي استفاده شده داريم :
هزينه حافظه اي = هزينه آرايه دوبعدي ساختار حافظه اي + حافظه يك بعدي ابعاد ماتريس ها
هزينه زماني:
با توجه به حلقه هاي for استفاده شده در كد پياده سازي برنامه هزينه زماني برابر است با
