بخشی از پاورپوینت

اسلاید 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++;

}    

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید