پاورپوینت کامل بررسی برنامه‌نویسی پویا (Dynamic Programming) و کاربرد آن در حل مسائل بهینه‌سازی

توجه : این پروژه به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل بررسی برنامه‌نویسی پویا (Dynamic Programming) و کاربرد آن در حل مسائل بهینه‌سازی دارای ۵۲ اسلاید می باشد و دارای تنظیمات کامل در Power Point می باشد و آماده پرینت یا چاپ است

فایل پاور پوینت پاورپوینت کامل بررسی برنامه‌نویسی پویا (Dynamic Programming) و کاربرد آن در حل مسائل بهینه‌سازی  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

---

لطفا به نکات زیر در هنگام خرید

دانلودپاورپوینت کامل بررسی برنامه‌نویسی پویا (Dynamic Programming) و کاربرد آن در حل مسائل بهینه‌سازی

توجه فرمایید.

۱-در این مطلب، متن اسلاید های اولیه 

دانلودپاورپوینت کامل بررسی برنامه‌نویسی پویا (Dynamic Programming) و کاربرد آن در حل مسائل بهینه‌سازی

قرار داده شده است

۲-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید

۳-پس از پرداخت هزینه ، حداکثر طی ۱۲ ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد

۴-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد

۵-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار داده نشده است

---

بخشی از متن پاورپوینت کامل بررسی برنامه‌نویسی پویا (Dynamic Programming) و کاربرد آن در حل مسائل بهینه‌سازی :

اسلاید ۱ :

برنامه نویسی پویا (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 ik<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 ik<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++;

}