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

در علوم رایانه و ریاضیات، برنامه ریزی پویا یا داینامیک، روشی کارآمد برای حل مسائل جستجو و بهینه سازی با استفاده از دو ویژگی زیرمسئله های هم پوشان و زیرساخت های بهینه است. برخلاف برنامه ریزی خطی، چارچوب استانداردی برای فرموله کردن مسائل برنامه ریزی پویا وجود ندارد. در واقع، آنچه برنامه ریزی پویا انجام می دهد ارائه روش برخورد کلی جهت حل این نوع مسائل است. در هر مورد، باید معادلات و روابط ریاضی مخصوصی که با شرایط آن مسئله تطبیق دارد نوشته شود. [ ۱]
این روش در سال ۱۹۵۳ توسط ریاضی دانی به نام ریچارد بلمن معرفی شد. برنامه ریزِی پویا در ریاضی و علوم رایانه روشی شناخته شده است که از آن در نوشتن الگوریتم های بهینه با استفاده از حذف اجرای چند بارهٔ یک زیر مسئله یکسان استفاده می شود. تعریف برنامه ریزی پویا در ریاضی و علوم رایانه متفاوت است. نشان داده شده است که روش علوم رایانه ای برای برنامه ریزی پویا کارایی بالاتری دارد زیرا محاسبات تکراری را حذف می کند در حالی که در روش ریاضی برنامه ریزی پویا امکان کاهش فضای حافظه بیشتر است.
برنامه ریزی پویا شبیه روش تقسیم و حل، مسائل را با استفاده از ترکیب کردن جواب زیرمسئله ها حل می کند. الگوریتم تقسیم و حل، مسئله را به زیر مسئله های مستقل تقسیم می کند و پس از حل زیر مسئله ها به صورت بازگشتی، نتایج را با هم ترکیب کرده و جواب مسئله اصلی را به دست می آورد. به عبارت دقیق تر، برنامه ریزی پویا بهتر است در مسائلی استفاده شود که زیرمسئله ها مستقل نیستند؛ یعنی زمانی که زیرمسئله ها، خود دارای چندین زیر مسئلهٔ یکسان هستند. در این حالت روش تقسیم و حل با اجرای مکرر زیرمسئله های یکسان، بیشتر از میزان لازم محاسبات انجام می دهد. یک الگوریتم برنامه ریزی پویا زیرمسئله ها را یک بار حل و جواب آن ها را در یک جدول ذخیره می کند و با این کار از تکرار اجرای زیرمسئله ها در زمانی که مجدداً به جواب آن ها نیاز است جلوگیری می کند. مثلا اگر مسئله فیبوناچی با برنامه ریزی پویا حل شود باعث اجرای مکرر یک زیرمسئله نمی شود. مثلا برای محاسبه f ( 5 ) مقادیر f ( 4 ) و f ( 3 ) تنها یک بار محاسبه می شوند. ولی اگر از روش تقسیم و حل استفاده شود. f ( 3 ) دو بار محاسبه می شود که سربار محاسباتی است.
یک مسئله باید دارای دو مشخصهٔ کلیدی باشد تا بتوان برنامه نویسی پویا را برای آن به کار برد: زیرساختار بهینه و زیرمسئله های هم پوشان. [ ۲] در طرف مقابل، به حل یک مسئله با ترکیب جواب های بهینهٔ زیرمسئله های ناهم پوشان، «تقسیم و حل» گفته می شود. به همین علت است که مرتب سازی ادغامی و سریع به عنوان مسائل برنامه نویسی پویا شناخته نمی شوند.