بخشی از پاورپوینت
اسلاید 1 :
nبرنامه نویسی پویا، از این لحاظ که نمونه به نمونه های کوچکتر تقسیم می شود ، مشابه روش تقسیم و حل است ولی در این روش ، نخست نمونه های کوچک تر را حل می کنیم ، نتایج را ذخیره می کنیم و بعدا هر گاه به یکی از آن ها نیاز پیدا شد، به جای محاسبه دوباره کافی است آن را بازیابی کنیم.
اسلاید 2 :
nمراحل بسط یک الگوریتم برنامه نویسی پویا به شرح زیر است:
1- ارائه یک ویژگی بازگشتی برای حل نمونه ای از مسئله .
2- حل نمونه ای از مسئله به شیوه جزء به کل با حل نمونه های کوچک تر.
اسلاید 3 :
3-3 برنامه نویسی پویا و مسائل بهینه سازی
n
nحل بهینه ، سومین مرحله از بسط یک الگوریتم برنامه نویسی پویا برای مسائل بهینه سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:
اسلاید 4 :
1- ارائه یک ویژگی بازگشتی که حل بهینه ی نمونه ای از مسئله را به دست می دهد.
2- محاسبه مقدار حل بهینه به شیوه ی جزء به کل.
3- بنا کردن یک حل نمونه به شیوه ی جزء به کل.
n
اسلاید 5 :
n
nهر مسئله بهینه سازی را نمی توان با استفاده از برنامه نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.
n
nاصل بهینگی در یک مسئله صدق می کند اگریک حل بهینه برای نمونه ای از مسئله ، همواره حاوی حل بهینه برای همه ی زیر نمونه ها باشد.
اسلاید 6 :
4-3 ضرب زنجیره ای ماتریس ها
nهدف بسط الگوریتمی است که ترتیب بهینه را برای n ماتریس معین کند.
nترتیب بهینه فقط به ابعاد ماتریس ها بستگی دارد.
nعلاوه بر n ، این ابعاد تنها ورودی های الگوریتم هستند.
nاین الگوریتم حداقل به صورت نمایی است.
n
اسلاید 7 :
5-3 درخت های جست و جوی دودویی بهینه
n
nدرخت جست و جوی دودویی یک دودویی از عناصر( که معمولا کلید نامیده می شوند)است که از یک مجموعه مرتب حاصل می شود، به قسمی که:
1- هر گره حاوی یک کلید است.
اسلاید 8 :
2- کلید های موجود در زیردرخت چپ یک گره مفروض، کوچک تر یا مساوی کلید آن گره هستند.
3- کلیدهای موجود درزیردرخت راست یک گره مفروض، بزرگ تر یا مساوی کلید آن گره هستند.
n