درس ششم - برنامه نویسی پویا PDF

‫به نام آنکه جان را فکرت آموخت‬ ‫مباحثی در الگوريتمها‬ ‫‪Topics in Algorithms‬‬ ‫درس ششم ‪ :‬برنامه نویسی پویا ‪Dynamic Programming‬‬ ‫‪1‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫برنامه نویسی...

‫به نام آنکه جان را فکرت آموخت‬ ‫مباحثی در الگوريتمها‬ ‫‪Topics in Algorithms‬‬ ‫درس ششم ‪ :‬برنامه نویسی پویا ‪Dynamic Programming‬‬ ‫‪1‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫برنامه نویسی پویا (‪)Dynamic Programming‬‬ ‫در برنامه نویسی پویا‪ ،‬معموال از یک آرایه یا یک جدول استفاده‬ ‫◼‬ ‫میشود‪ ،‬بدین صورت که یک نمونه به نمونه های کوچکتر‬ ‫تقسیم می شود‪ ،‬مشابه روش تقسیم و حل است ولی در این‬ ‫روش ‪ ،‬نخست نمونه های کوچکتر را حل می کنیم ‪ ،‬سپس نتایج‬ ‫را ذخیره می کنیم و هر زمان به یکی از آن ها نیاز پیدا شد‪ ،‬به‬ ‫جای محاسبه دوباره کافی است آن را بازیابی کنیم‪.‬‬ ‫‪2‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫مراحل بسط یک الگوریتم برنامه نویسی پویا‬ ‫‪ -1‬ارائه یک ویژگی بازگشتی برای حل نمونه ای از مسئله ‪.‬‬ ‫‪ -2‬حل نمونه ای از مسئله به شیوه جزء به کل با حل نمونه‬ ‫های کوچک تر‪.‬‬ ‫نکته‌‪ :‬هر مسئله بهینه‌سازی ‌را با استفاده از برنامه‌نویسی پویا نمی توان حل‬ ‫نمود بهینه بودن باید در مسئله صدق بکند بهینگی در یک مسئله صدق‬ ‫می‌کند اگر یک حل بهینه برای نمونه مسئله همواره حاوی حل بهینه برای‬ ‫همه زیر نمونه‌ها باشد‪.‬‬ ‫‪3‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫ویژگی های برنامه نویسی پویا‬ ‫مسئله معموال بهینه (مینیمم یا ماکزیمم) ا ست‪.‬‬ ‫◼‬ ‫برای حل مسئله باید زیر مسائل نیز بهینه حل شوند‪.‬‬ ‫◼‬ ‫حل به روش استقرائی و تقسیم وحل موجب حل تکراری‬ ‫◼‬ ‫یک زیر مسئله دلخواه خواهد شد‪.‬‬ ‫‪4‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫الگوریتم هایی که بااستفاده از برنامه نویسی پویا حل می شوند‬ ‫دنباله‌فیبوناچی‬ ‫◼‬ ‫ضریب‌دو‌جمله‌ای‬ ‫◼‬ ‫ضرب‌زنجیره‌ای‌‌ماتریس‌ها‬ ‫◼‬ ‫درخت‌های‌جستجوی‌دودوئی‌بهینه‬ ‫◼‬ ‫کوله‌پشتی‌صفر‌و‌یک‬ ‫◼‬ ‫فلوید‬ ‫◼‬ ‫فروشنده‌دوره‌گرد‬ ‫◼‬ ‫‪5‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫الگوریتم بازگشتی محاسبه دنباله فیبوناچی‬ ‫‪6‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫تعداد جمالت محاسبه شده توسط الگوریتم بازگشتی فیبوناچی برای جمله ‪ n‬ام بزرگتر از‪2n/2‬‬ ‫تعداد جمالت محاسبه شده توسط این الگوریتم خوب نیست‪ ،‬برابر ‪2n/2‬‬ ‫}‬ ‫‪7‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫بهبود الگوریتم بازگشتی فیبوناچی که مرتبه آن ‪ 2n/2‬می باشد را می خواهیم به خطی تبدیل کنیم‬ ‫‪3+5+1=9‬‬ ‫‪5+9+1=15‬‬ ‫‪9+15+1=25‬‬ ‫تعداد جمالت محاسبه شده توسط این الگوریتم خوب نیست ‪2n/2‬‬ ‫𝟏‪K 𝒏 =𝑲 𝐧−𝟏 +𝐤 𝐧−𝟐 +‬‬ ‫‪8‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫الگوریتم محاسبه جمله ‪ n‬ام فیبوناچی با استفاده از برنامه نويسی پويا‬ ‫معموال از یک آرایه یا یک جدول استفاده‬ ‫میکنیم‪ ،‬سپس نتایج را ذخیره می کنیم و هر‬ ‫زمان به یکی از آن ها نیاز پیدا شد‪ ،‬به جای‬ ‫محاسبه دوباره کافی است آن را بازیابی کنیم‪.‬‬ ‫توسط الگوریتم بازگشتی فیبوناچی برای جمله‬ ‫‪ n‬ام بزرگتر از‪2n/2‬‬ ‫و الگوریتم تکرار محاسبه جمله ‪ n‬ام فیبوناچی‬ ‫با استفاده از برنامه نویسی پویا از مرتبه خطی‬ ‫)‪O(n‬‬ ‫‪9‬‬ ‫مباحثی در الگوریتم ها ‪ -‬درس ششم – برنامه نویسی پویا‬ ‫‪By:Takbiri‬‬  ‫الگوریتم ترکیب و تحلیل پیچیدگی زمانی برای تعداد عملیات جمع‬ ‫)‪Combination (n,m‬‬ ‫الگوریتم‬ ‫عملیات ترکیب در آمار و ریاضی‬ ‫{‬ ‫)‪If (n==m||m==0‬‬ ‫ترکیب با‬ ‫‪𝑛−1‬‬ ‫‪𝑛−1‬‬ ‫;‪return 1‬‬ ‫استفاده از‬ ‫تقسیم و حل‬ ‫از‬ ‫‪+‬‬ ‫از‬ ‫‪Else‬‬ ‫𝑚‬ ‫;)‪return combination(n-1,m-1)+combination(n-1,m‬‬ ‫‪𝑚−1‬‬ ‫}‬ ‫‪T(n-m,m-1)+T(n-1,m)+1‬‬ ‫‪0