توضیحات
برنامهریزی پویا روشی کارآمد برای حل دستهای از مسائل با استفاده از دو خصیصه زیرمسئلههای هم پوشان و زیر ساختهای بهینه است. این روش با نام برنامهنویسی پویا نیز شناخته میشود ولی نباید با برنامهنویسی کامپیوتری اشتباه گرفته شود. چارچوب استانداردی برای حل عمومی مسائل برنامهریزی پویا وجود ندارد. بلکه برنامه ریزی پویا فقط یک روش برخورد کلی (یا یک دید کلی) جهت حل دستهای از مسائل ارائه میدهد.در این روش همانند روش تقسیم و حل، مسئله اصلی را با ترکیب کردن جواب زیر مسئلهها حل میکنیم. تفاوت این دو روش در این است که در روش تقسیم و حل، مسئله را به تعدادی زیر مسئله مستقل از یکدیگر تقسیم کرده، هرکدام را جداگانه حل میکنیم و در پایان جوابها را با یکدیگر ترکیب میکنیم.
در صورتی که در برنامهریزی پویا مسئلهها نباید کاملا مستقل باشند، یعنی خود زیر مسئلهها، زیر مسئله (یا زیر زیر مسئله) های مشترک دارند. این زیر مسئلههای مشترک با این که از مسیرهای جداگانهای حاصل شدهاند، اما جوابشان در هر دو حالت یکسان است و نیازی به محاسبهی دوبارهی آنها نیست. به همین دلیل در برنامهریزی پویا جواب این زیر مسئلهها را در یک جدول (یا هر ساختار دیگری) نگهداری میکنیم و اگر دوباره به آن نیاز پیدا کردیم، به راحتی جواب را از جدول میخوانیم و نیازی به محاسبهی دوباره آن نیست. این تفاوت شاید بسیار ساده و ناچیز به نظر برسد اما در عمل، با همین راهکار ساده، زمان حل مسائل به طور چشمگیری کاهش پیدا میکند.
تاریخچه برنامه ریزی پویا
این روش در سال ۱۹۵۳ توسط ریاضیدانی به نام ریچارد بلمن معرفی شد. برنامهریزِی پویا در ریاضی و علوم رایانه روشی شناخته شدهاست که از آن در نوشتن الگوریتمهای بهینه با استفاده از حذف اجرای چند بارهٔ یک زیر مسئله یکسان استفاده میشود. تعریف برنامهریزی پویا در ریاضی و علوم رایانه متفاوت است. نشان داده شدهاست که روش علوم رایانهای برای برنامهریزی پویا کارایی بالاتری دارد زیرا محاسبات تکراری را حذف میکند در حالی که در روش ریاضی برنامهریزی پویا امکان کاهش فضای حافظه بیشتر است.
برنامهریزی پویا شبیه روش تقسیم و حل، مسائل را با استفاده از ترکیب کردن جواب زیرمسئلهها حل میکند. الگوریتم تقسیم و حل، مسئله را به زیر مسئلههای مستقل تقسیم میکند و پس از حل زیر مسئلهها به صورت بازگشتی، نتایج را با هم ترکیب کرده و جواب مسئله اصلی را بدست میآورد. به عبارت دقیق تر، برنامهریزی پویا در مواردی قابل استفاده است که زیرمسئلهها مستقل نیستند؛ یعنی زمانی که زیرمسئلهها، خود دارای چندین زیر مسئلهٔ یکسان هستند. در این حالت روش تقسیم و حل با اجرای مکرر زیرمسئلههای یکسان، بیشتر از میزان لازم محاسبات انجام میدهد. یک الگوریتم برنامهریزی پویا زیرمسئلهها را یک بار حل و جواب آنها را در یک جدول ذخیره میکند و با این کار از تکرار اجرای زیرمسئلهها در زمانی که مجدداً به جواب آنها نیاز است جلوگیری میکند.
نقد و بررسیها
هیچ دیدگاهی برای این محصول نوشته نشده است.