تفاوت میان نسخه‌های «برنامه‌نویسی پویا»

جز
 
== تاریخچه ==
این روش در سال ۱۹۵۳ توسط ریاضی‌دانی به نام [[ریچارد بلمن]] معرفی شد. برنامهریزِی پویا در ریاضی و علوم رایانه روشی شناخته شده استشده‌است که از آن در نوشتن الگوریتم‌های بهینه با استفاده از حذف اجرای چند بارهٔ یک زیر مسئله یکسان استفاده می‌شود. تعریف برنامه ریزِی پویا در ریاضی و علوم رایانه متفاوت است. نشان داده شده استشده‌است که روش علوم رایانه ای برای برنامه ریزِی پویا کارایی بالاتری دارد زیرا محاسبات تکراری را حذف می‌کند در حالی که در روش ریاضی برنامه ریزِی پویا امکان کاهش فضای حافظه بیشتر است.
 
برنامه ریزِی پویا شبیه روش تقسیم و حل مسائل را با استفاده از ترکیب کردن جواب زیرمسأله‌ها حل می‌کند. [[الگوریتم تقسیم و حل]]، مسئله را به زیر مسئله‌های مستقل تقسیم می‌کند و پس از حل زیر مسئله‌ها به صورت بازگشتی،نتایج را با هم ترکیب کرده و جواب مسألهاصلی را بدست می‌آورد. به عبارت دقیق تر، برنامه ریزِی پویا در مواردی قابلاستفاده است که زیرمسأله‌ها مستقل نیستند؛ یعنی زمانی که زیرمسأله‌ها دارای زیر-زیر مسئله‌های یکسان هستند. دراین حالت روش تقسیم و حل با اجرای مکرر زیرمسأله‌های یکسان، بیشتر از میزان لازم محاسبات انجام می‌دهد. یکالگوریتم برنامه ریزِی پویا زیرمسأله‌ها را یک بار حل و جواب آنها را در یک جدول ذخیره می‌کند و با این کار از تکراراجرای زیرمسأله‌ها در زمانی که مجددًا به جواب آنها نیاز است جلوگیری می‌کند.
حل بهینه، سومین مرحله از بسط یک الگوریتم [[برنامه‌نویسی]] پویا برای مسائل [[بهینه‌سازی]] است. مراحل بسط چنین الگوریتمی به شرح زیر است:
 
۱-# ارائه یک ویژگی بازگشتی که حل بهینهٔ نمونه ای از مسئله را به دست می‌دهد.
۳-# بنامحاسبه کردن یکمقدار حل نمونهبهینه به شیوهی جزء به کل.
 
۲-# محاسبهبنا مقدارکردن یک حل بهینهنمونه به شیوهی جزء به کل.
 
۳- بنا کردن یک حل نمونه به شیوهی جزء به کل.
 
تمام مسائل بهینهسازی را نمی‌توان با برنامه‌نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.
 
درخت [[جستجوی دودویی]] یک [[درخت دودویی]] از عناصر است که معمولاً کلید نامیده می‌شوند به قسمی که:
 
۱-# هر گره حاوی یک کلید است.
۳-# کلیدهای موجود در زیردرخت راستچپ هر گره، بزرگترکوچکتر یا مساوی کلید آن گره هستند.
 
۲-# کلیدهای موجود در زیردرخت چپراست هر گره، کوچکتربزرگتر یا مساوی کلید آن گره هستند.
 
۳- کلیدهای موجود در زیردرخت راست هر گره، بزرگتر یا مساوی کلید آن گره هستند
 
=== زیرسازه بهینه ===
استفاده از روش زیرسازه بهینه به این معناست که مسئله را به زیرمسئله‌هایی کوچک‌تر بشکانیم و برای هر یک از این زیرمسئله‌ها پاسخی بهینه بیابیم و پاسخ بهینه مسئلهٔ کلی را از کنار هم قرار دادن این پاسخ‌های بهینهٔ جزئی به دست آوریم. مثلاً در هنگام حل مسئلهٔ یافتن کوتاه‌ترین مسیر از یک [[رأس]] یک [[گراف]] به رأسی دیگر، می‌توانیم کوتاه‌ترین مسیر تا مقصد از همهٔ رئوس مجاور را به دست آوریم و از آن برای جواب کلی استفاده کنیم. به طوربه‌طور کلی [[حل مسئله]] از این روش شامل سه مرحله است.
# شکاندن مسئله به بخش‌های کوچک‌تر
# حل خود این زیرمسئله‌ها با شکاندن آن‌ها به صورت [[الگوریتم بازگشتی|بازگشتی]]
زمانی که یک مسئله به دو یا چند زیرمسئله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:
 
۱-# داده‌های زیرمسئله‌ها هیچ اشتراکی با هم نداشته و کاملاً مستقل از هم هستند. نمونه چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجه حاصل از آن بخش اثری ندارند. معمولاً روش تقسیم و حل برای چنین مسائلی کارایی خوبی دارد.
۲-# داده‌های زیرمسئله وابسته به هم بوده یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسئله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله [[اعداد فیبوناچی]] است.
 
۲- داده‌های زیرمسئله وابسته به هم بوده یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسئله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله [[اعداد فیبوناچی]] است.
 
روش برنامه‌نویسی پویا غالباً برای [[الگوریتم|الگوریتمهایی]] بکار برده می‌شود که در پی حل مسئله‌ای بصورت بهینه می‌باشند.
 
در روش [[تقسیم]] و غلبه ممکن است برخی از زیرمسائل کوچکتر با هم برابر باشند که در این صورت زیرمسائل برابر بطور تکراری چندین مرتبه حل می‌شوند که این یکی از معایب روش [[تقسیم]] و غلبه است.
 
ایده‌ای که در فرای روش برنامه‌نویسی پویا نهفته استنهفته‌است جلوگیری از انجام این محاسبات تکراری است و روشی که معمولاً برای این عمل بکارگرفته می‌شود استفاده از جدولی برای نگهداری نتایج حاصل از حل زیرمسائل است. در این صورت اگر [[الگوریتم]] به زیرمسئله‌ای برخورد کرد که پیش از این [[حل شده]] است، بجای حل مجدد آن، نتیجه محاسبه قبلی را از جدول برداشته و کار را با زیرمسئله بعدی دنبال می‌کند.
 
روش برنامه‌نویسی پویا یک روش پایین به بالا است به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. در حالیکه از نظر ساختاری روش تقسیم و غلبه روشی است از بالا به پایین، یعنی بطور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و بسمت پایین و حل مسائل کوچکتر به پیش می‌رود.
*هیلیر، فردریک؛ لیبرمن، جرالد.ج (۱۳۸۲). تحقیق در عملیات، ترجمه محمد مدرس و اردوان آصف‌وزیری، تهران: نشر جوان، چاپ دهم.
*نیپولیتان، ریچارد؛ نعیمی‌پور، کیومرث (۱۳۹۰). طراحی الگوریتم‌ها، ترجمه عین‌الله جعفرنژاد قمی، بابل: انتشارات علوم رایانه.
 
== پیوند به بیرون ==
{{چپ‌چین}}