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

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

اسلاید ۱ :

برنامه نويسی پويا (Dynamic Programming)

nمشابه روش تقسيم و حل, مسأله را به نمونه های کوچکتر تقسيم می کند.

nابتدا نمونه های کوچکتر را حل کرده و نتايج را ذخيره می کند. در صورت نياز به جای محاسبه مجدد آن را بازيابی می کند.

nيک روش پايين به بالا است.

nبرخلاف روش تقسيم و حل, نمونه های کوچکتر به هم مرتبطند.

nزمانی که مسأله ها, زيرمسائل مشترکی داشته باشند الگوريتم تقسيم و حل بيشتر از حد نياز کار می کند و زير مسائل مشترک را چندين بار حل می کند.

اسلاید ۲ :

ويژگيها

nبهينه سازی: در اغلب الگوريتمهای برنامه سازی پويا, تنها به دست آوردن جواب مهم نيست و بايد جواب بهينه نيز باشد. مسأله بهينه سازی در حل مسائل کليه سطوح بايد اعمال گردد.

nبرخلاف مسائل تقسيم و حل که برای حل هر مسأله سطح L تنها از مسائل سطح L-1 استفاده می کند, در روش برنامه سازی پويا می توان از کليه مسائل سطوح پايين تر استفاده کرد.

nدر هر سطح, کليه مسائل آن سطح حل می گردند و نگهداری می شوند.

اسلاید ۳ :

اصل بهينگی principle of optimality

n   اصل بهينگی در صورتی برقرار است که در هر رشته از تصميمات بهينه, هرزير رشته از اين تصميمات نيز بهينه باشند.

  مثال: مسأله کوتاهترين مسير در گراف

n   مراحل توليد الگوريتم برنامه نويسی پويا

   ۱- مشخص کردن ساختار جواب بهينه

  ۲- ارائه يک رابطه بازگشتی برای حل مسأله

  ۳- حل يک نمونه مسأله به روش پايين به بالا و با شروع از حل نمونه های کوچکتر

  ۴- ساختن يک جواب بهينه از روی اطلاعات محاسبه شده

اسلاید ۴ :

الگوريتم محاسبه ضريب دوجمله ای با روش برنامه سازی پويا

int bin ( int n , int k)

{  int i,k,B[0..n][0..k];

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

       for (j=0; j<=minimum(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];

    return B[n][k];

}  

اسلاید ۵ :

مسأله زنجيره ضرب ماتريسها

هدف: يافتن روش بهينه ضرب n ماتريس:

M=M1*M2*… * Mn

۱- ضرب ماتريسها شرکت پذير است.

۲- دو ماتريس در صورتی قابل ضرب هستند که تعداد ستونهای ماتريس اول برابر با تعداد سطرهای ماتريس دوم باشد.

M=M1*M2* M3

M=(M1*M2)* M3

 M=M1*(M2* M3)

اسلاید ۶ :

nفرض: ماتريس Mi  i=1,2,…,n ,دارای ابعاد ri-1×ri است. 

           mij حداقل تعداد اعمال ضرب عددی برای محاسبه Mi× Mi+1× …× Mj

mii=0

mij=min 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 حداقل تعداد اعمال ضرب عددی لازم برای ضرب دو ماتريس حاصل از عمليات فوق

اسلاید ۷ :

حل مسأله:

nهمه مسائل را از کوچکترين به بزرگترين حل می کنيم.

nجواب زيرمسائل برای مراجعات بعدی در جدولی نگهداری می شود.

nمراحل:

   مرحله صفر: عمل ضربی انجام نمی شود. i=0,1,…,n mii=0,

   مرحله يک: يک عمل ضرب ماتريسی انجام می شود. همه i=0,1,…,n-1 mi,i+1, محاسبه و در جدولی نگهداری می شود.

   مرحله دو: دو عمل ماتريسی انجام می شود. همه i=0,1,…,n-2 mi,i+2, محاسبه و در جدولی نگهداری می شود.

   مرحلهn-1: n-1 عمل ماتريسی انجام می شود. در اين مرحله m1n محاسبه می شود. که تعداد حداقل اعمل لازم برای ضرب ماتريسهاست.

اسلاید ۸ :

برای ضرب چهار ماتريس:

M1[10][20],M2[20][50],M3[50][1],M4[1][100]

m11=m22=m33=m44=0

m12=min(m11+m22+10×۲۰×۵۰)=۱۰۰۰۰

m23=min(m22+m33+20×۵۰×۱)=۱۰۰۰

m34=min(m33+m44+50×۱×۱۰۰)=۵۰۰۰

m13=min(m11+m23+10×۲۰×۱, m12+m33+10×۵۰×۱)=۱۲۰۰

m24=min(m22+m34+20×۵۰×۱۰۰, m23+m44+20×۱×۱۰۰)=۳۰۰۰

m14=min(m11+m24+10×۲۰×۱۰۰, m12+m34+10×۵۰×۱۰۰, m13+m44+10×۱×۱۰۰)=۲۲۰۰

اسلاید ۹ :

الگوريتم تعيين تعداد حداقل ضربهای مورد نياز

int optimum(int m[][n+1],int A[][n+1], int n)

{ int i,j,L;

   for(i=1;i<=n;i++) m[i][i]=0;

   for(L=0;L<n;L++)

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

      { j=i+L;

        m[i][j]= min i≤k<j {m[i][k]+m[k+1][j]+ri-1×rk×rj)

        A[i][j]=the value of k that gives the minimum;

      }

   return m[1][n];

}

پيچيدگی زمانی: θ(n3)

اسلاید ۱۰ :

الگوريتم ايجاد مسير بهينه (در x ذخيره خواهد شد)

void order (int i, int j, int x)

{  static int k=0;

    if ( A[i][j]==0)

        return;

    order(i, A[i][j], x);

    order(A[i][j]+1,j,x);

    x[k]=A[i][j];

    k++;

}