مبانی برنامه نویسی پویا


سطح دشواری ساده
اغلب در Infosys در MAQ
برنامه نویسی پویا نظریه

در مبانی برنامه نویسی پویا ، اصول DP و تفاوت های آن را با روش Greedy ، Divide and Conquer و Recursion بررسی خواهیم کرد.

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

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

برخی از مشکلات اساسی DP

  • مشکل اعداد زشت
  • تغییر سکه
  • اعداد فیبوناچی
  • مشکل اعداد زنگ
  • برج هانوی
  • اعداد زنگ
  • مشکل کوله پشتی

برنامه نویسی پویا (DP) در مقابل روش حریص

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

اگرچه روشهای حریصانه معمولاً سریعتر از DP هستند و همچنین از نظر حافظه کارآمد هستند زیرا مقادیر محاسبه شده قبلی را برای استفاده در آینده ذخیره نمی کند ، اما اطمینان از راه حل بهینه را نمی دهد.

برنامه نویسی پویا (DP) در مقابل روش تقسیم و تسخیر

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

(یادآوری به تکنیک ذخیره سازی نتایج محاسبه شده قبلی به طور کلی در نقشه هش برای جلوگیری از محاسبه مشکلات مشابه به طور مکرر اشاره دارد).

برنامه نویسی پویا (DP) در مقابل روش بازگشت

DP راه حلهای محاسبه شده قبلی را ذخیره می کند تا از آنها در آینده و برای جلوگیری از محاسبات مجدد به عنوان مورد نیاز استفاده کند. با این وجود ، در بازگشت ، امکان محاسبه مجدد وجود دارد که غیر ضروری است زیرا مقادیر را ذخیره نمی کند.

بازگشت منجر به محاسبه مجدد مشکلات چندین بار می شود ، بنابراین در چنین مواردی پیچیدگی زمان بازگشت همیشه بیشتر از محلول DP است.

در این مقاله ، ما در مورد برنامه نویسی پویا اصول اولیه در مقالات بعدی ، برخی از مشکلات اساسی DP را بیان خواهیم کرد.

ارجاع سوالات مصاحبه