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

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

اسلاید 3 :

برنامه نویسی پویا (Dynamic Programming)
یادآوری: روش تقسیم و حل برای محاسبه جمله n ام فیبوناجی
روش تقسیم و حل، روشی بالا به پایین است.
این روش در مسائلی مانند مرتب سازی ادغامی جواب میدهد چراکه نمونههای کوچکتر به مرتبط نیستند.
ولی در محاسبه جمله nام فیبوناجی، نمونهها کوچکتر به هم مرتبطند

اسلاید 4 :

برنامه نویسی پویا
برنامه نویسی پویا از این نظر که نمونه به نمونههای کوچکتر تقسیم میشود، مشابه روش تقسیم و حل است ولی
1- ابتدا نمونههای کوچکتر را حل میکنیم
2- نتایج را ذخیره میکنیم و
3- بعدا هرگاه به آنها نیاز شد به جای محاسبه مجدد تنها آنها را بازیابی میکنیم

بنابراین روشی پایین به بالا است

اسلاید 5 :

برنامه نویسی پویا
مراحل بسط یک الگوریتم برنامه نویسی پویا:

1- ارائه یک ویژگی بازگشتی برای نمونهای از مسئله
2- حل مسئله به شیوه پایین به بالا با حل نمونههای کوچکتر

اسلاید 6 :

الف) ضریب دوجملهای

اسلاید 7 :

الف) ضریب دوجملهای
حل با استفاده از روش تقسیموحل:
function [result]=binCoef(n,k)
if (k==0 || k==n)
result=1;
else
result=binCoef(n-1,k-1)+binCoef(n-1,k);
end
end

اسلاید 8 :

الف) ضریب دوجملهای
همانند محاسبه جمله nام فیبوناجی، این الگوریتم نیز کارایی کمی دارد.
مثلا binCoef(n-1,k-1) و binCoef(n-1,k) هر دو نیاز به نتیجه
binCoef(n-2,k-1)
دارند و این نمونه در هر فراخوانی بازگشتی به صورت جداگانه محاسبه میشود.

اسلاید 9 :

الف) ضریب دوجملهای
حل با روش پویا:
1- یک ویژگی بازگشتی ایجاد میکنیم



2- مسئله را به صورت پایین به بالا حل میکنیم .

اسلاید 10 :

الف) ضریب دوجملهای
حل با روش پویا:
1- یک ویژگی بازگشتی ایجاد میکنیم

2- مسئله را به صورت..
پایین به بالا حل میکنیم:

اسلاید 11 :

الف) ضریب دوجملهای
حل با روش پویا:
function [result]=binCoef2(n,k)
for i=0:n
for j=0:min([i k])
if ((j==0)||(j==i))
B(i,j)=1;
else
B(i,j)=B(i-1,j-1)+B(i-1,j);
end
end
end
result=B(n,k);
end
تمرین: تابع فوق را به گونهای تغییر دهید که اجرای آن در Matlab صحیح باشد

اسلاید 12 :

الف) ضریب دوجملهای
پیچیدگی محاسباتی و مرتبه آن:
for i=1:n
for j=1:min([i k])
end
end

اسلاید 13 :

الف) ضریب دوجملهای
تمرین:
مسئله ضریب دو جملهای را با برنامهنویسی پویا با آرایه یک بعدی حل کنید

اسلاید 14 :

کوئیز از جلسه قبل)
برای یافتن ضریب kام دوجملهای رابطه زیر برقرار است.



الف) ویژگی بازگشتی ارائه دهید که ضریب kام با روش برنامه نویسی پویا بدست آید.
ب) تابع متناظر با ویژگی بازگشتی در بخش الف را بنویسید

اسلاید 15 :

مسائل بهینه سازی
در ریاضیات و علوم کامپیوتر مساله بهینهسازی به صورت زیر تعریف میشود:
مسالهای است که در آن به دنبال یافتن بهترین راه حل در بین.
تمامی راه حلهای ممکن هستیم.

این مسائل باتوجه متغیرهای موثر در حل مسئله به دو گروه زیر تقسیم میشوند:
متغیرهای پیوسته مساله بهینهسازی پیوسته
متغیرهای گسستهمساله بهینهسازی ترکیبی

اسلاید 16 :

مسائل بهینه سازی
مساله بهینهسازی پیوسته
فرم استاندارد این مسائل به صورت زیر است:
که .
تابع هدفی است که میخواهیم xای را برایش بیابیم که آن را کمینه کند.
محدودیتهایی هستند که به صورت عدم تساوی بیان میشوند.
محدودیتهایی هستند که به صورت تساوی بیان میگردند.

اسلاید 17 :

مسائل بهینه سازی
مسائل بهینهسازی ترکیبی
مانند ..
مساله یافتن کوتاهترین مسیر بین دو شهر
این مسائل به صورت چهارتایی (I, f, m, g) بیان میشوند که ..
I مجموعه نمونهها است مانند .
مجموعه شهرها به صورت دوبهدو
xای که عضو I است را در نظر بگیرید مانند .
(یزد و کرمانشاه)
f(x) مجموعه راه حلهای ممکن برای این x است مانند .
مسیرهای مختلف جادهای بین این دو شهر

اسلاید 18 :

مسائل بهینه سازی
مسائل بهینهسازی ترکیبی (I, f, m, g)
فرض کنید که y، یکی از راه حلهای ممکن باشد مانند.
یزد-ابرکوه-اصفهان-بروجرد-کنگاور-کرمانشاه
m(x,y) تابعی است که اندازه y به ازای x که معمولا عددی مثبت است را برمیگرداند.
g، تابع هدف است که معمولا یا min و یا max است.
هدف در این مسائل بهینهسازی آن است تا ..
برای هر x، .
بهینهترین راه حل (y) با توجه به تابع هدف را پیدا کنیم.

اسلاید 19 :

حل مسائل بهینهسازی ترکیبی با برنامهنویسی پویا
برای حل مسائل بهینهسازی ترکیبی روشهای مختلفی وجود دارد که با رویکردهای حل آنها با روشهای برنامهنویسی پویا، حریصانه، عقبگرد و شاخوحد انشاا. در طول ترم آشنا خواهیم شد.
مسائل بهینهسازی ترکیبی ای را میتوان با برنامه نویسی پویا حل کرد به شرط آنکه
اصل بهینگی در مورد آن برقرار باشد

اسلاید 20 :

اصل بهینگی (Principle of Optimality)
تعریف:
مسالهای شرایط اصل بهینگی را دارد
چنانچه در آن مساله .
زیر راهحلهای یک راهحل بهینه برای هر نمونه مساله .
خودشان راهحلهای بهینه برای زیرمسائلی متناظر باشند.
حل مسائل بهینهسازی ترکیبی با برنامهنویسی پویا