بخشی از پاورپوینت
اسلاید 1 :
برنامه نويسی پويا (Dy amic Programmi g)
مشابه روش تقسيم و حل, مسأله را به نمونه های کوچکتر تقسيم می کند.
ابتدا نمونه های کوچکتر را حل کرده و نتايج را ذخيره می کند. در صورت نياز به جای محاسبه مجدد آن را بازيابی می کند.
يک روش پايين به بالا است.
برخلاف روش تقسيم و حل, نمونه های کوچکتر به هم مرتبطند.
زمانی که مسأله ها, زيرمسائل مشترکی داشته باشند الگوريتم تقسيم و حل بيشتر از حد نياز کار می کند و زير مسائل مشترک را چندين بار حل می کند.
اسلاید 2 :
ويژگيها
بهينه سازی: در اغلب الگوريتمهای برنامه سازی پويا, تنها به دست آوردن جواب مهم نيست و بايد جواب بهينه نيز باشد. مسأله بهينه سازی در حل مسائل کليه سطوح بايد اعمال گردد.
برخلاف مسائل تقسيم و حل که برای حل هر مسأله سطح L تنها از مسائل سطح L-1 استفاده می کند, در روش برنامه سازی پويا می توان از کليه مسائل سطوح پايين تر استفاده کرد.
در هر سطح, کليه مسائل آن سطح حل می گردند و نگهداری می شوند.
اسلاید 3 :
اصل بهينگی pri ciple of optimality
اصل بهينگی در صورتی برقرار است که در هر رشته از تصميمات بهينه, هرزير رشته از اين تصميمات نيز بهينه باشند.
مثال: مسأله کوتاهترين مسير در گراف
مراحل توليد الگوريتم برنامه نويسی پويا
1- مشخص کردن ساختار جواب بهينه
2- ارائه يک رابطه بازگشتی برای حل مسأله
3- حل يک نمونه مسأله به روش پايين به بالا و با شروع از حل نمونه های کوچکتر
4- ساختن يک جواب بهينه از روی اطلاعات محاسبه شده
اسلاید 4 :
الگوريتم محاسبه ضريب دوجمله ای با روش برنامه سازی پويا
i t bi ( i t , i t k)
{ i t i,k,B[0.. ][0..k];
for (i=0; i<= ; i++)
for (j=0; j<=mi imum(i,k); j++)
if B(j==0) || j==i)
B[i][j]=1;
else
B[i][j]=B[i-1][j-1]+B[i-1][j];
retur B[ ][k];
}
اسلاید 5 :
مسأله زنجيره ضرب ماتريسها
هدف: يافتن روش بهينه ضرب ماتريس:
M=M1*M2*… * M
1- ضرب ماتريسها شرکت پذير است.
2- دو ماتريس در صورتی قابل ضرب هستند که تعداد ستونهای ماتريس اول برابر با تعداد سطرهای ماتريس دوم باشد.
M=M1*M2* M3
M=(M1*M2)* M3
M=M1*(M2* M3)
اسلاید 6 :
فرض: ماتريس Mi i=1,2,…, ,دارای ابعاد ri-1×ri است.
mij حداقل تعداد اعمال ضرب عددی برای محاسبه Mi× Mi+1× …× Mj
mii=0
mij=mi i≤k<j (mik+mk+1,j+ri-1×rk×rj)
mik حداقل تعداد اعمال ضرب عددی برای محاسبه Mi× Mi+1× …× Mj
mk+1,j حداقل تعداد اعمال ضرب عددی برای محاسبه Mk+1× Mk+2× …× Mj
ri-1×rk×rj حداقل تعداد اعمال ضرب عددی لازم برای ضرب دو ماتريس حاصل از عمليات فوق
اسلاید 7 :
حل مسأله:
همه مسائل را از کوچکترين به بزرگترين حل می کنيم.
جواب زيرمسائل برای مراجعات بعدی در جدولی نگهداری می شود.
مراحل:
مرحله صفر: عمل ضربی انجام نمی شود. i=0,1,…, mii=0,
مرحله يک: يک عمل ضرب ماتريسی انجام می شود. همه i=0,1,…, -1 mi,i+1, محاسبه و در جدولی نگهداری می شود.
مرحله دو: دو عمل ماتريسی انجام می شود. همه i=0,1,…, -2 mi,i+2, محاسبه و در جدولی نگهداری می شود.
مرحله -1: -1 عمل ماتريسی انجام می شود. در اين مرحله m1 محاسبه می شود. که تعداد حداقل اعمل لازم برای ضرب ماتريسهاست.
اسلاید 8 :
برای ضرب چهار ماتريس:
M1[10][20],M2[20][50],M3[50][1],M4[1][100]
m11=m22=m33=m44=0
m12=mi (m11+m22+10×20×50)=10000
m23=mi (m22+m33+20×50×1)=1000
m34=mi (m33+m44+50×1×100)=5000
m13=mi (m11+m23+10×20×1, m12+m33+10×50×1)=1200
m24=mi (m22+m34+20×50×100, m23+m44+20×1×100)=3000
m14=mi (m11+m24+10×20×100, m12+m34+10×50×100, m13+m44+10×1×100)=2200
اسلاید 9 :
الگوريتم تعيين تعداد حداقل ضربهای مورد نياز
i t optimum(i t m[][ +1],i t A[][ +1], i t )
{ i t i,j,L;
for(i=1;i<= ;i++) m[i][i]=0;
for(L=0;L< ;L++)
for(i=1;i<= ;i++)
{ j=i+L;
m[i][j]= mi i≤k<j {m[i][k]+m[k+1][j]+ri-1×rk×rj)
A[i][j]=the value of k that gives the mi imum;
}
retur m[1][ ];
}
پيچيدگی زمانی: θ( 3)
اسلاید 10 :
الگوريتم ايجاد مسير بهينه (در x ذخيره خواهد شد)
void order (i t i, i t j, i t x)
{ static i t k=0;
if ( A[i][j]==0)
retur ;
order(i, A[i][j], x);
order(A[i][j]+1,j,x);
x[k]=A[i][j];
k++;
}
