سلام دوستان
شباهتی که بین برنامه نویسی پویا و تقسیم و غلبه وجود داره اینه که هر دو نیاز به یک رابطه بازگشتی دارند (بر اساس کتاب پوران پژوهش)
خب نتیجه: برنامه نویسی پویا نیاز به رابطه بازگشتی دارد.
سوال: برای حل سری فیبونانچی به صورت پویا می توانیم مسئله را با مرتبه n انجام دهیم! خب توی اون الگوریتم معروفی که با مرتبه n انجام میشه، رابطه بازگشتی نداریم!!
الان چرا رابطه بازگشتی نداریم؟
(21 بهمن 1393 08:06 ب.ظ)sharareh_moradi نوشته شده توسط: [ -> ]سلام دوستان
شباهتی که بین برنامه نویسی پویا و تقسیم و غلبه وجود داره اینه که هر دو نیاز به یک رابطه بازگشتی دارند (بر اساس کتاب پوران پژوهش)
خب نتیجه: برنامه نویسی پویا نیاز به رابطه بازگشتی دارد.
سوال: برای حل سری فیبونانچی به صورت پویا می توانیم مسئله را با مرتبه n انجام دهیم! خب توی اون الگوریتم معروفی که با مرتبه n انجام میشه، رابطه بازگشتی نداریم!!
الان چرا رابطه بازگشتی نداریم؟
فیبوناچی رو از طریق برنامه نویسی پویا میشه هم به صورت بازگشتی و هم به صورت غیر بازگشتی در زمان n حل کرد. جمله ی اولتون هم تقریبا درسته. در اکثر موارد الگوریتم های پویا ابتدا به صورت بازگشتی حل می شن ولی تو رابطه ی بازگشتی برخی از زیر مساله ها چندین بار محاسبه میشن و برای اینکه این زیر مساله ها چند بار محاسبه نشن، به همین خاطر از راه حل پویا استفاده میکنیم تا هر زیر مساله رو یه بار حل کنیم و در بقیه ی موارد از اون استفاده می کنیم.
(21 بهمن 1393 11:38 ب.ظ)x86 نوشته شده توسط: [ -> ] (21 بهمن 1393 08:06 ب.ظ)sharareh_moradi نوشته شده توسط: [ -> ]سلام دوستان
شباهتی که بین برنامه نویسی پویا و تقسیم و غلبه وجود داره اینه که هر دو نیاز به یک رابطه بازگشتی دارند (بر اساس کتاب پوران پژوهش)
خب نتیجه: برنامه نویسی پویا نیاز به رابطه بازگشتی دارد.
سوال: برای حل سری فیبونانچی به صورت پویا می توانیم مسئله را با مرتبه n انجام دهیم! خب توی اون الگوریتم معروفی که با مرتبه n انجام میشه، رابطه بازگشتی نداریم!!
الان چرا رابطه بازگشتی نداریم؟
فیبوناچی رو از طریق برنامه نویسی پویا میشه هم به صورت بازگشتی و هم به صورت غیر بازگشتی در زمان n حل کرد. جمله ی اولتون هم تقریبا درسته. در اکثر موارد الگوریتم های پویا ابتدا به صورت بازگشتی حل می شن ولی تو رابطه ی بازگشتی برخی از زیر مساله ها چندین بار محاسبه میشن و برای اینکه این زیر مساله ها چند بار محاسبه نشن، به همین خاطر از راه حل پویا استفاده میکنیم تا هر زیر مساله رو یه بار حل کنیم و در بقیه ی موارد از اون استفاده می کنیم.
آخه اون جمله اولی که گفته شباهت ...
بدین معنی میشه که بازگشتی شرط لازم برای برنامه نویسی پویاست
پس اینطور که شما میگین
ما میتونیم برنامه نویسی پویا داشته باشیم که اصن از روابط بازگشتی هم استفاده نکنیم
درسته؟
(22 بهمن 1393 12:09 ق.ظ)sharareh_moradi نوشته شده توسط: [ -> ]آخه اون جمله اولی که گفته شباهت ...
بدین معنی میشه که بازگشتی شرط لازم برای برنامه نویسی پویاست
پس اینطور که شما میگین
ما میتونیم برنامه نویسی پویا داشته باشیم که اصن از روابط بازگشتی هم استفاده نکنیم
درسته؟
بله همین طور هست. مثال های زیادی وجود داره که میتونید بررسی کنید.