نمایش مبدأ برای برنامه‌نویسی پویا

در [[علوم رایانه]] و [[ریاضیات]]، '''برنامه‌ریزی پویا''' یا '''داینامیک،''' روشی کارآمد برای حل مسائل جستجو و [[بهینه‌سازی]] با استفاده از دو ویژگی [[زیرمسئله‌های هم‌پوشان]] و [[زیرساخت‌های بهینه]] است.
برخلاف [[برنامه‌ریزی خطی]]، چارچوب استانداردی برای فرموله کردن مسائل برنامه‌ریزی پویا وجود ندارد. در واقع، آنچه برنامه‌ریزی پویا انجام می‌دهد ارائه روش برخورد کلی جهت حل این نوع مسائل است. در هر مورد، باید [[معادلات]] و روابط ریاضی مخصوصی که با شرایط آن مسئله تطبیق دارد نوشته شود.<ref>هیلیر، ج 2، ص 65</ref>

== تاریخچه ==
این روش در سال ۱۹۵۳ توسط ریاضی‌دانی به نام [[ریچارد بلمن]] معرفی شد. برنامه‌ریزِی پویا در ریاضی و علوم رایانه روشی شناخته شده‌است که از آن در نوشتن الگوریتم‌های بهینه با استفاده از حذف اجرای چند بارهٔ یک زیر مسئله یکسان استفاده می‌شود. تعریف برنامه‌ریزی پویا در ریاضی و علوم رایانه متفاوت است. نشان داده شده‌است که روش علوم رایانه‌ای برای برنامه‌ریزی پویا کارایی بالاتری دارد زیرا محاسبات تکراری را حذف می‌کند در حالی که در روش ریاضی برنامه‌ریزی پویا امکان کاهش فضای حافظه بیشتر است.

برنامه‌ریزی پویا شبیه روش تقسیم و حل، مسائل را با استفاده از ترکیب کردن جواب زیرمسئله‌ها حل می‌کند. [[الگوریتم تقسیم و حل]]، مسئله را به زیر مسئله‌های مستقل تقسیم می‌کند و پس از حل زیر مسئله‌ها به صورت بازگشتی، نتایج را با هم ترکیب کرده و جواب مسئله اصلی را به‌دست می‌آورد. به عبارت دقیق تر، برنامه‌ریزی پویا بهتر است در مسائلی استفاده شود که زیرمسئله‌ها مستقل نیستند؛ یعنی زمانی که زیرمسئله‌ها، خود دارای چندین زیر مسئلهٔ یکسان هستند. در این حالت روش تقسیم و حل با اجرای مکرر زیرمسئله‌های یکسان، بیشتر از میزان لازم محاسبات انجام می‌دهد. یک الگوریتم برنامه‌ریزی پویا زیرمسئله‌ها را یک بار حل و جواب آن‌ها را در یک جدول ذخیره می‌کند و با این کار از تکرار اجرای زیرمسئله‌ها در زمانی که مجدداً به جواب آن‌ها نیاز است جلوگیری می‌کند. مثلا اگر مسئله فیبوناچی با برنامه ریزی پویا حل شود باعث اجرای مکرر یک زیرمسئله نمی شود. مثلا برای محاسبه f(5) مقادیر f(4) و f(3) تنها یک بار محاسبه می شوند. ولی اگر از روش تقسیم و حل استفاده شود. f(3) دو بار محاسبه می شود که سربار محاسباتی است.

== ویژگی‌ها ==
یک مسئله باید دارای دو مشخصهٔ کلیدی باشد تا بتوان برنامه‌نویسی پویا را برای آن به کار برد: [[زیربنای بهینه|زیرساختار بهینه]] و زیرمسئله‌های هم‌پوشان.<ref>{{یادکرد کتاب|عنوان=Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. p. 378}}</ref> در طرف مقابل، به حل یک مسئله با ترکیب جواب‌های بهینهٔ زیرمسئله‌های ناهم‌پوشان، «[[الگوریتم تقسیم و حل|تقسیم و حل]]» گفته‌می‌شود. به همین علت است که [[مرتب‌سازی ادغامی]] و [[مرتب‌سازی سریع|سریع]] به عنوان مسائل برنامه‌نویسی پویا شناخته‌نمی‌شوند.

=== اصل بهینگی ===
اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمسئله‌ها هم باید بهینه باشند. یعنی بهینه بودن مسئله، بهینه بودن زیرمسئله‌ها را ایجاب می‌کند.
پس می‌توان از روش برنامه‌نویسی پویا استفاده کرد.

حل بهینه، سومین مرحله از بسط یک الگوریتم [[برنامه‌نویسی]] پویا برای مسائل [[بهینه‌سازی]] است. مراحل بسط چنین الگوریتمی به شرح زیر است:
# ارائه یک ویژگی بازگشتی که حل بهینهٔ نمونه‌ای از مسئله را به دست می‌دهد.
# محاسبه مقدار حل بهینه به شیوهٔ جزء به کل.
# بنا کردن یک حل نمونه به شیوهٔ جزء به کل.

تمام مسائل بهینه‌سازی را نمی‌توان با برنامه‌نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.

اصل بهینگی در یک مسئله صدق می‌کند اگر یک حل بهینه برای نمونه ای از مسئله، همواره حاوی حل بهینه برای همهٔ زیر نمونه‌ها باشد.

در روش برنامه‌نویسی پویا اغلب از یک آرایه برای ذخیره نتایج جهت استفاده مجدد استفاده شده، و زیرمسائل به صورت جزء به کل حل می‌شوند. در مورد این مسئله، ابتدا زیرمسائلی که تنها از دو ماتریس تشکیل شده‌اند محاسبه می‌شوند. سپس زیرمسائلی که از سه ماتریس تشکیل شده‌اند محاسبه می‌شوند. این دسته از زیرمسائل به زیرمسائلی متشکل از دو ماتریس تجزیه می‌شوند که قبلاً محاسبات آن‌ها صورت گرفته، و نتایج آن‌ها در آرایه ذخیره شده‌اند. در نتیجه نیاز به محاسبه مجدد آن‌ها نیست. به همین ترتیب در مرحله بعد زیرمسائل با چهار ماتریس محاسبه می‌شوند، و الی آخر.

[[درختهای جستجوی دودویی]] بهینه

درخت [[جستجوی دودویی]] یک [[درخت دودویی]] از عناصر است که معمولاً کلید نامیده می‌شوند به قسمی که:
# هر گره حاوی یک کلید است.
# کلیدهای موجود در زیردرخت چپ هر گره، کوچکتر یا مساوی کلید آن گره هستند.
# کلیدهای موجود در زیردرخت راست هر گره، بزرگتر یا مساوی کلید آن گره هستند

=== زیرسازه بهینه ===
زیرساختار بهینه به این معناست که جواب یک [[مسئلهٔ بهینه‌سازی]] را بتوان از ترکیب جواب‌های بهینهٔ زیرمسئله‌های آن به دست آورد. چنین زیرساختارهای بهینه‌ای معمولاً با رویکرد [[بازگشت|بازگشتی]] به دست می‌آیند؛ برای مثال، در گراف ''(G=(V,E''، کوتاه‌ترین مسیرِ م از رأس آ به رأس ب، زیرساختار بهینه از خود نشان می‌دهد: هر رأس میانیِ ث از مسیرِ م را در نظر بگیرید. اگر م واقعاً کوتاه‌ترین مسیر باشد، آنگاه می‌توان آن را به دو زیرمسیر م<sub>۱</sub> از آ تا ث و م<sub>۲</sub> از ث تا ب در نظر گرفت، به نحوی که هر کدام از این‌ها کوتاه‌ترین مسیر بین دو سر خود هستند (به همان طریق برش و چسباندن کتاب [[مقدمه‌ای بر الگوریتم‌ها]]). بر این اساس، می‌توان جواب را به صورت بازگشتی بیان کرد، درست مانند الگوریتم‌های [[الگوریتم بلمن–فورد|بلمن-فورد]] و [[الگوریتم فلوید-وارشال|فلوید-وارشال]].<ref>{{یادکرد کتاب|عنوان=Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. pp. 379-383}}</ref>

استفاده از روش زیرسازه بهینه به این معناست که مسئله را به زیرمسئله‌هایی کوچک‌تر بشکنیم و برای هر یک از این زیرمسئله‌ها پاسخی بهینه بیابیم و پاسخ بهینه مسئلهٔ کلی را از کنار هم قرار دادن این پاسخ‌های بهینهٔ جزئی به دست آوریم. مثلاً در هنگام حل مسئلهٔ یافتن کوتاه‌ترین مسیر از یک [[رأس (نظریه گراف)|رأس]] یک [[گراف (نوع داده‌های انتزاعی)|گراف]] به رأسی دیگر، می‌توانیم کوتاه‌ترین مسیر تا مقصد از همهٔ رئوس مجاور را به دست آوریم و از آن برای جواب کلی استفاده کنیم. به‌طور کلی [[حل مسئله]] از این روش شامل سه مرحله است.
# شکستن مسئله به بخش‌های کوچک‌تر
# حل خود این زیرمسئله‌ها با شکاندن آن‌ها به صورت [[الگوریتم بازگشتی|بازگشتی]]
# استفاده از پاسخ‌های جزئی برای یافتن پاسخ کلی

=== زیرمسئله‌های هم‌پوشان ===
زیرمسئله‌های هم‌پوشان به معنای کوچک بودن فضای زیرمسئله‌هاست، به این معنا که هر الگوریتم بازگشتی برای حل این مسئله، باید به جای ایجاد زیرمسئله‌های جدید، زیرمسئله‌های تکراری را بارها حل کند. برای مثال، به فرمول بازگشی دنبالهٔ فیبوناچی دقت کنید: ''F<sub>i</sub> = F<sub>i−1</sub> + F<sub>i−2</sub>''، با حالات پایهٔ ''F''<sub>1</sub> = ''F''<sub>2</sub> = ۱. آنگاه ''F''<sub>43</sub> = ''F''<sub>42</sub> + ''F''<sub>41</sub>، و ''F''<sub>42</sub> = ''F''<sub>41</sub> + ''F''<sub>40</sub>. اکنون ''F''<sub>41</sub> در زیردرخت‌های هر دوی ''F''<sub>43</sub> و ''F''<sub>42</sub> محاسبه می‌شود. در صورت اتخاذ چنین رویکرد ساده‌انگارانه‌ای، نهایتاً زیرمسئله‌های یکسانی را بارها حل می‌کنیم، در صورتی که تعداد کل زیرمسئله‌ها در واقعیت کم است (تنها ۴۳تا). برنامه‌نویسی پویا به این حقیقت دقت می‌کند و هر زیرمسئله را تنها یک بار حل می‌کند.<ref>{{یادکرد کتاب|عنوان=Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. pp. 384-386}}</ref>

گفته می‌شود مسئله‌ای دارای زیرمسئله‌های هم‌پوشان است، اگر بتوان مسئله را به زیرمسئله‌های کوچکتری شکست که پاسخ هرکدام چند بار در طول فرایند حل مورد استفاده قرار بگیرد.<ref>{{یادکرد وب |url=http://20bits.com/2007/05/08/introduction-to-dynamic-programming/ |title=Introduction to Dynamic Programming {{!}} 20bits<!-- عنوان تصحیح شده توسط ربات --> |accessdate=۲۵ ژوئیه ۲۰۱۱ |archiveurl=https://web.archive.org/web/20081103041312/http://20bits.com/2007/05/08/introduction-to-dynamic-programming/ |archivedate=۳ نوامبر ۲۰۰۸ |dead-url=yes}}</ref> برنامه‌ریزی پویا کمک می‌کند تا هر کدام از این پاسخ‌ها فقط یک بار محاسبه شوند و فرایند حل از بابت دوباره‌کاری هزینه‌ای را متحمل نشود. برای مثال در [[دنباله فیبوناچی]] برای محاسبهٔ عدد چهارم [[دنباله]] به دانستن عدد سوم نیاز داریم. برای محاسبهٔ عدد پنجم هم باز به عدد سوم نیاز داریم. حال اگر مثلاً در شرایطی بخواهیم عدد ششم [[دنبالهٔ فیبوناچی]] را حساب کنیم، در این محاسبه هم مقدار عدد پنجم را می‌خواهیم و هم مقدار عدد چهارم را. اگر تصمیم بگیریم اعداد چهارم و پنجم را به نوبت حساب کنیم در هنگام محاسبهٔ هرکدام به مقدار عدد سوم نیاز پیدا می‌کنیم و باید دوباره آن را محاسبه کنیم.
برای جلوگیری از این محاسبات چندباره، [[الگوریتم|الگوریتمهایی]] که مبتنی بر برنامه‌ریزی پویا هستند، معمولاً یکی از دو راه زیر را استفاده می‌کنند.
* [[طراحی بالا به پایین و پایین به بالا|رویکرد بالا به پایین]]: راه درروی مستقیم از صورت‌بندی بازگشتی هر مسئله‌ای است. اگر جواب مسئله‌ای را بتوان به صورت بازگشتی با جواب زیرمسئله‌های آن به دست آورد، و در صورت هم‌پوشانی زیرمسئله‌ها، می‌توان جواب زیرمسئله‌ها را در یک جدول [[مموایز کردن|به خاطر سپرد]]. هر گاه که برای حل یک زیرمسئله اقدام می‌کنیم، ابتدا بررسی می‌کنیم که آیا این زیرمسئله قبلاً حل شده یا نه؛ اگر جواب آن را داشتیم، می‌توانیم آن را مستقیماً استفاده کنیم؛ در غیر این صورت، زیرمسئله را حل می‌کنیم و جواب آن را به جدول اضافه می‌کنیم. در این رویکرد مسئله به زیرمسئله‌هایی شکسته می‌شود و پاسخ هر زیرمسئله پس از محاسبه در جایی ذخیره می‌شود. در مراحل بعدی هر وقت به آن پاسخ نیاز بود پاسخ از روی حافظه خوانده می‌شود. این فرایند ترکیبی از [[الگوریتم بازگشتی]] و ذخیره‌سازی در حافظه است.
* رویکرد پایین به بالا: پس از آن که جواب یک مسئله را به صورت بازگشتی با استفاده از زیرمسئله‌های آن صورت‌بندی کردیم، می‌توانیم مسئله را از پایین به بالا نگاه کنیم: ابتدا زیرمسئله‌ها را حل می‌کنیم و سپس جواب آن‌ها را برای به دست آوردن جواب زیرمسئله‌های بزرگ‌تر استفاده می‌کنیم تا نهایتاً به مسئلهٔ اصلی برسیم. این روش نیز معمولاً به کمک یک جدول با تولید مرحله به مرحلهٔ زیرمسئله‌های بزرگ‌تر و بزرگ‌تر به کمک جواب زیرمسئله‌های کوچک‌تر انجام می‌شود؛ برای مثال، اگر مقادیر ''F''<sub>41</sub> و ''F''<sub>40</sub> را بدانیم، می‌توانیم مستقیماً مقدار ''F''<sub>42</sub> را به دست آوریم. در این رویکرد همهٔ زیرمسئله‌های مورد نیاز از کوچک به بزرگ حل می‌شوند و از جواب‌ها «بلافاصله» برای محاسبهٔ بعدی‌ها استفاده می‌شود و فرایند محاسبه تا رسیدن به زیرمسئلهٔ مورد نیاز (که در واقع مسئلهٔ اصلی ماست) ادامه می‌یابد. بدیهی است که در این حالت استفاده از [[الگوریتم بازگشتی]] ضروری نیست. مثال زیر این تفاوت‌ها را روشن‌تر می‌کند. برخی از [[زبان برنامه‌نویسی|زبان‌های برنامه‌نویسی]] می‌توانند به‌طور خودکار جواب صدا زدن یک تابع با ورودی‌های مشخص را به خاطر بسپارند تا صدا زدن با نام را سرعت ببخشند (این فرایند با نام صدا زدن با نیاز شناخته‌می‌شود). برخی زبان‌ها به شکل سیار این امکان را در اختیار برنامه‌نویس قرار می‌دهند (مانند Scheme ,Common Lisp ,<ref>{{یادکرد وب|عنوان=Memoize - perldoc.perl.org|نشانی=https://perldoc.perl.org/Memoize.html|وبگاه=perldoc.perl.org|بازبینی=2019-12-05}}</ref>[[پرل|Perl]] و D). برخی زبان‌های نیز به صورت خودکار به‌خاطرسپاری را در خود دارند: مانند Prolog جدول‌دار و J، که به‌خاطرسپاری را با قید .M پشتیبانی می‌کند.<ref>{{یادکرد وب|عنوان=Memoization|نشانی=https://www.metalevel.at/prolog/memoization|وبگاه=www.metalevel.at|بازبینی=2019-12-05}}</ref> در هر صورت، این تنها برای یک تابع با شفافیت ارجاعی امکان دارد. به‌خاطرسپاری به عنوان یک [[الگوی طراحی]] در دسترس نیز در زبان‌های بازنویسی جملات مانند زبان ولفرام یافت‌می‌شود.

== گراف زیرمسئله‌ها ==
[[پرونده:Fibonacci dynamic programming.svg|بندانگشتی|124x124پیکسل|'''تصویر ۱.''' گراف زیرمسئله‌های دنبالهٔ فیبوناچی. درخت نبودن این گراف نشان‌دهندهٔ زیرمسئله‌های هم‌پوشان است.]]
زمانی که به یک مسئلهٔ برنامه‌نویسی پویا می‌اندیشیم، باید مجموعهٔ زیرمسئله‌های موجود و چگونگی وابستگی آن‌ها را درک کنیم.

'''گراف زیرمسئله‌ها''' دقیقاً همین اطلاعات را برای یک مسئله در بر می‌گیرد. تصویر ۱ گراف زیرمسئله‌های دنباله‌های فیبوناچی را نشان می‌دهد. گراف زیرمسئله‌ها یک [[گراف جهت‌دار]]، شامل یک رأس به ازای هر زیرمسئلهٔ متمایز است و در صورتی یک یال جهت‌دار از رأس زیرمسئلهٔ x به رأس زیرمسئلهٔ y دارد که برای تعیین یک جواب بهینه برای زیرمسئلهٔ x مستقیماً نیاز به در نظر گرفتن یک جواب بهینه برای زیرمسئلهٔ y داشته‌باشیم. برای نمونه، گراف زیرمسئله دارای یک یال از x به y است، در صورتی که یک رویهٔ (procedure) بازگشتی بالا به پایین برای حل x، مستقیماً خود را برای حل y صدا بزند. می‌توان گراف زیرمسئله‌ها را یک نسخهٔ کاهش‌یافتهٔ درخت بازگشتی برای روش بازگشتی بالا به پایین در نظر گرفت، به گونه‌ای که همهٔ رئوس مربوط به یک زیرمسئله را یکی کنیم و یال‌ها را از والد به فرزند جهت‌دار کنیم.

روش پایین به بالا برای برنامه‌نویسی پویا رئوس گراف زیرمسئله‌ها را به ترتیبی در نظر می‌گیرد که همهٔ زیرمسئله‌های مجاور یک زیرمسئله، پیش از آن حل شوند. در یک الگوریتم برنامه‌نویسی پویای پایین به بالا، رئوس گراف زیرمسئله‌ها را به صورتی در نظر می‌گیریم که «معکوس مرتب توپولوژیکی» یا «مرتب توپولوژیک وارون» زیرگراف مسئه‌ها است. به زبان دیگر، هیچ زیرمسئله‌ای تا زمانی که همهٔ زیرمسئله‌هایی که به آن‌ها وابسته است حل نشده‌اند، در نظر گرفته‌نمی‌شود. به‌طور مشابه، می‌توانیم رویکرد بالا به پایین (همراه به‌خاطرسپاری) برای برنامه‌نویسی پویا را به شکل [[الگوریتم جستجوی اول عمق|جستجوی ژرفانخست]] گراف زیرمسئله‌ها ببینیم.

اندازهٔ گراف زیرمسئله‌ها می‌تواند ما را در تعیین [[زمان اجرای الگوریتم]] برنامه‌نویسی پویا یاری کند. از آنجایی که هر زیرمسئله را فقط یک بار حل می‌کنیم، زمان اجرا برابر است با مجموع تعداد بارهایی که نیاز است هر زیرمسئله را حل کنیم. به‌طور معمول، زمان محاسبهٔ جواب یک زیرمسئله، متناسب با درجهٔ رأس متناظر در گراف، و تعداد زیرمسئله‌ها برابر با تعداد رئوس گراف است.<ref>{{یادکرد کتاب|عنوان=Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. pp. 367-368}}</ref>

== مثال ==
یک [[پیاده‌سازی]] ساده از یک [[تابع]] برای یافتن عدد [[فیبوناچی]] nام می‌تواند به شکل زیر باشد.
{{چپ‌چین}}
 '''function''' fib(n)
     '''if''' n = 0    
         '''return''' 0        
     '''if''' n = 1    
         '''return''' 1        
     '''return''' fib(n − 1) + fib(n − 2)  
{{پایان چپ‌چین}}
برای مثال اگر از چنین تابعی <code>(fib(5</code> را بخواهیم، تابع‌هایی که صدا می‌شوند به شکل زیر خواهند بود.
{{چپ‌چین}}
# <code>fib(5)</code>
# <code>fib(4) + fib(3)</code>
# <code>(fib(3) + fib(2)) + (fib(2) + fib(1))</code>
# <code>((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))</code>
# <code>(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))</code>

{{پایان چپ‌چین}}

مشخص است که چنین فرایندی پر از محاسبات تکراری است. مثلاً عدد فیبوناچی دوم به تنهایی سه بار حساب شده‌است. در محاسبات بزرگ‌تر چنین تکرارهایی برنامه را به شدت کند می‌کنند. این [[الگوریتم]] دارای [[پیچیدگی زمانی]] [[تابع نمایی|نمایی]] است.
حال فرض کنید ما یک [[آرایه (ساختمان داده‌ها)|آرایه]] دوتایی map داریم که عدد n را به مقدار عدد فیبوناچی nام مربوط کرده و ذخیره می‌کند. [[پیچیدگی زمانی]] چنین الگوریتمی n خواهد بود. همچنین میزان فضای اشغال‌شده‌اش هم از مرتبه n خواهد بود.

{{چپ‌چین}}
 '''var''' m := '''map'''(0 → 1, 1 → 1)
 '''function''' fib(n)
     '''if''' '''map''' m '''does not contain key''' n
         m[n] := fib(n − 1) + fib(n − 2)
     '''return''' m[n]

{{پایان چپ‌چین}}

این نمونه‌ای از فرایند بالا به پایین بود. چون ابتدا مسئله را شکستیم و بعد به محاسبه و ذخیرهٔ پاسخ زیرمسئله‌ها پرداختیم.

در فرایند پایین به بالا برای حل چنین مسئله‌ای از عدد فیبوناچی یکم شروع می‌کنیم تا به عدد خواسته‌شده برسیم. با این کار باز هم پیچیدگی زمانی از مرتبه n است.
{{چپ‌چین}}
 '''function''' fib(n)
      '''var''' previousFib := 0, currentFib := 1
      '''if''' n = 0
          '''return''' 0
      '''if''' n = 1
          '''return''' 1
      '''repeat''' n − 1 '''times'''
          '''var''' newFib := previousFib + currentFib
          previousFib := currentFib
          currentFib := newFib
      '''return''' currentFib

{{پایان چپ‌چین}}

برتری این روش به روش قبلی در این است که در این روش حتی به فضای ذخیره از مرتبه n هم نیازی نیست. فضای ذخیره از مرتبه ۱ کفایت می‌کند. علت این که همیشه از رویکرد پایین به بالا استفاده نمی‌کنیم این است که گاهی از قبل نمی‌دانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبوریم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم.

== تفاوت این روش و روش تقسیم و غلبه (تقسیم و حل) ==
یکی از روش‌های پرکاربرد و مشهور [[طراحی الگوریتم]] روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) است. این روش همچون [[روش تقسیم و حل]] (Divide and Conquer) بر پایه تقسیم مسئله بر زیرمسئله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.

زمانی که یک مسئله به دو یا چند زیرمسئله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:
# داده‌های زیرمسئله‌ها هیچ اشتراکی با هم نداشته و کاملاً مستقل از هم هستند. نمونه چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجهٔ حاصل از آن بخش، اثری ندارند. معمولاً روش تقسیم و حل برای چنین مسائلی کارایی خوبی دارد.
# داده‌های زیرمسئله وابسته به هم بوده یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسئله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله [[اعداد فیبوناچی]] است.
روش برنامه‌نویسی پویا غالباً برای [[الگوریتم]]‌هایی به کار برده می‌شود که در پی حل مسئله‌ای به صورت بهینه می‌باشند.

در روش تقسیم و غلبه ممکن است برخی از زیرمسائلِ کوچکتر، با هم برابر باشند که در این صورت زیرمسائلِ برابر، به‌طور تکراری چندین مرتبه حل می‌شوند که این یکی از معایب روش تقسیم و غلبه است.

ایده‌ای که در فرایِ روش برنامه‌نویسی پویا نهفته‌است، جلوگیری از انجام این محاسبات تکراری است و روشی که معمولاً برای این عمل به کارگرفته می‌شود استفاده از جدولی برای نگهداری نتایج حاصل از حل زیرمسائل است. در این صورت اگر [[الگوریتم]] به زیرمسئله‌ای برخورد کرد که پیش از این [[حل شده]] است، به جای حل مجدد آن، نتیجه محاسبه قبلی را از جدول برداشته و کار را با زیرمسئله بعدی دنبال می‌کند.

روش برنامه‌نویسی پویا یک روش پایین به بالا است (البته همان‌طور که گفته شد، اگر از قبل بدانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبور نباشیم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم) به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. درحالی‌که از نظر ساختاری، روش تقسیم و غلبه روشی است از بالا به پایین، یعنی به‌طور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و به سمت پایین و حل مسائلِ کوچکتر، به پیش می‌رود.

== مجموع زیرمجموعه و کوله پشتی: اضافه کردن یک متغیر ==
ما بیشتر و بیشتر می‌بینیم که مسائل مربوط به برنامه‌ریزی منبع خیلی خوبی از مسایل الگوریتمی را با انگیزهٔ عملی ارائه می‌دهد. تاکنون مشکلاتی را در نظر گرفتیم که در آن درخواست‌ها با فاصلهٔ زمانی مشخص از یک منبع مشخص‌شده و همچنین مشکلاتی که در آن درخواست‌ها دارای مدت و مهلت هستند، اما فواصل خاصی را که در طی آن باید انجام شود تعیین نشده‌است. در این بخش، ما نسخه‌ای از نوع دوم مشکل را با مدت زمان و مهلت در نظر می‌گیریم، که حل مستقیم با استفاده از تکنیک‌هایی که تاکنون دیده‌ایم، دشوار است.

ما برای حل مسئله از برنامه‌نویسی پویا استفاده خواهیم کرد، اما با یک تغییر: مشخص می‌شود مجموعه زیرمسئله‌ها به اندازه کافی نخواهدبود، و بنابراین ما در نهایت به ایجاد یک مجموعه غنی‌تر از زیرمسئله‌ها می‌پردازیم. همان‌طور که خواهیم‌دید، این کار با اضافه کردن یک متغیر جدید به بازگشت در زیربرنامهٔ پویا انجام می‌شود.

=== مسئله ===
در مسئلهٔ برنامه‌ریزی که در اینجا مورد توجه قرار می‌دهیم، ما یک ماشین داریم که می‌تواند دستورها را پردازش کند همچنین یک سری درخواست‌ها <math>1, 2, \ldots, n</math> داریم که می‌توانیم از آن در بازهٔ زمانی <math>0</math> تا <math>W</math> استفاده کنیم. هر درخواست مربوط به یک دستور است که برای پردازش آن به <math>w_i</math> واحد زمانی نیاز داریم. اگر هدف ما این باشد که دستورها را پردازش کنیم به طوری که ماشین را تا زمان <math>W</math> مشغول نگه داریم، کدام دستورها را باید انتخاب کنیم؟

به زبان دقیق تر، فرض کنید که ما آیتم‌های <math>1, 2, \ldots, n</math> را داریم، که هر کدام دارای وزن <math>w_i</math> است. هدف ما انتخاب یک زیرمجموعه از این آیتم‌ها است به طوری که مجموع <math>w_i</math>های آیتم‌های انتخاب شده از <math>W</math> کمتر مساوی باشند و با توجه به این محدودیت، مجموع این وزن‌ها بیشترین مقدار ممکن باشد. ما این مسئله را «مسئلهٔ مجموع زیرمجموعه» می‌نامیم.

این مسئله یک حالت خاص رایج از مسئلهٔ [[کوله پشتی]] است، که هر درخواست <math>i</math> یک ارزش <math>v_i</math> و یک‌وزن <math>w_i</math> دارد. هدف در این مسئلهٔ کلی‌تر این است که زیرمجموعه‌ای با بیشترین مجموع ارزش انتخاب کنیم با توجه به اینکه نباید مجموع وزن‌ها از <math>W</math> بیشتر باشد. به‌طور معمول مسئلهٔ کوله پشتی یک زیرمسئله از مسائل کلی‌تر است. نام «کوله پشی» اشاره به مسئلهٔ پر کردن یک کوله پشتی با ظرفیت <math>W</math> دارد که باید آن را تا جای ممکن با استفاده از مجموعه ای از آیتم‌ها پرکرد. ما از واژهٔ وزن یا زمان برای اشاره به <math>W</math>، <math>w_i</math> استفاده خواهیم کرد.

چون این مسئله، مسائل برنامه‌ریزی دیگری که قبلاً دیده‌ایم را [[شبیه‌سازی]] می‌کند، طبیعی است که از خود بپرسیم آیا الگوریتم حریصانه‌ای برای راه‌حل بهینه وجود دارد یا خیر. به نظر می‌آید که پاسخ خیر باشد، حداقل تا کنون هیچ روش حریصانهٔ کارایی شناخته نشده‌است که آیتم‌ها را به صورت نزولی مرتب کند؛ یا حداقل این کار را برای آیتم‌های با وزن حداکثر <math>W</math> انجام دهد، و سپس ما شروع به انتخاب آیتم‌ها با این ترتیب کنیم تا جایی که مجموع وزن آیتم‌های انتخاب شده کمتر از <math>W</math> باشد. اما اگر <math>W</math> مضرب دو باشد، و ما سه آیتم با وزن‌های <math>\{\frac w 2, \frac w 2, \frac w 2 + 1\}</math> داشته‌باشیم، خواهیم دید که [[الگوریتم حریصانه]] جواب بهینه را تولید نخواهد کرد. به‌طور جایگزین می‌توانستیم آیتم‌ها را بر اساس وزنشان به صورت صعودی مرتب کنیم و کار مشابه را انجام دهیم، ولی این بار در ورودی‌های <math>\{\frac w 2, \frac w 2, 1\}</math> شکست می‌خورد.

هدف ما این است که نشان دهیم که چگونه با استفاده از برنامه‌نویسی پویا این مسئله را حل کنیم. [[اصول اولیه|اصول اولیهٔ]] برنامه‌نویسی پویا را به یاد بیاورید: ما باید تعداد کمی از زیرمسئله‌ها را داشته باشیم به طوری که هر زیرمسئله را بتوان به راحتی با استفاده از زیرمسئله‌های «کوچکتر» حل کرد و پاسخ به مسئلهٔ اصلی به‌راحتی به‌دست می‌آید، هنگامی که ما پاسخ همهٔ زیر مسئله‌ها را بدانیم.

=== طراحی الگوریتم ===
می‌خواهیم از تعداد زیادی زیرمسئله استفاده کنیم. در واقع برای هر مجموعهٔ اولیه <math>\{1, \ldots, i\}</math> از آیتم‌ها و هر مقدار ممکن w برای بیشینه وزن ممکن، زیرمسئله‌ای در نظر می‌گیریم تا با استفاده از آنها بتوانیم سریعتر مسئله را حل کنیم. فرض کنید که <math>W</math> یک [[عدد صحیح]] باشد و همهٔ درخواست‌های <math>i=1, 2, \ldots, n</math> مقادیر صحیح <math>w_i</math> هستند. ما یک زیرمسئله به ازای هر <math>i=1, 2, \ldots, n</math> و هر <math>w \le W</math> داریم. ما <math>opt(i,w)</math> را به عنوان مقدار پاسخ بهینه برای آیتم‌های <math>1, 2, \ldots, i</math> و بیشینه وزن مجاز <math>w</math> تعریف می‌کینم که برابر است با:

<math>opt(i,w) = \max_s \Sigma_s w_j</math>

که <math>\max</math> روی زیرمجموعهٔ <math>s \in \{1,\ldots,i\}</math> است که <math>w_i \le W</math> را ارضا می‌کند. استفاده از این مجموعهٔ جدید از زیرمسئله‌ها، این اجازه را به ما می‌دهد که مقدار <math>opt(i,w)</math> به عنوان یک عبارت ساده بر حسب مقادیر به‌دست آمده از مسائل کوچکتر بیان کرد. علاوه بر این <math>opt(i,w)</math> کمیتی است که ما در انتها به دنبال آن هستیم. فرض کنید که o نمایانگر راه‌حل بهینه برای مسئلهٔ اصلی باشد. دو حالت داریم:

۱- اگر <math>n \notin o</math> آنگاه <math>opt(n,W)= opt(n-1,W)</math> پس به راحتی می‌توانیم عبارت <math>n</math> را نادیده بگیریم.

۲- اگر <math>n \in o</math> آنگاه <math>opt(n,W)=w_n + opt(n-1,W-w_n)</math>، از این به بعد ما به دنبال استفاده از ظرفیت باقی‌ماندهٔ <math>W-w_n</math> هستیم.

هنگامی که آیتم nام بسیار بزرگ است، <math>w_n> W</math> ما باید داشته باشیم <math>opt(n,W)=opt(n-1, W)</math>. در غیر این صورت، ما راه‌حل بهینه را از این طریق با توجه به اینکه برای هر n درخواست کدام یک از گزینه‌های بالا بهتر است به‌دست می‌آوریم. با استفاده از استدلال مشابه برای زیرمسئلهٔ آیتم‌های <math>\{1,\ldots,i\}</math> و بیشینه وزن <math>w</math>، [[رابطه بازگشتی|رابطهٔ بازگشتی]] روبرو را می‌دهد:

(*)

اگر <math>w_i> W</math> آنگاه<math>opt(i,W)=opt(i-1, W)</math>. در غیر اینصورت:<math>opt(i,w) = \max\{opt(i-1,w), w_i + opt(i-1,w-w_i)\}</math>

مانند قبل، ما می‌خواهیم الگوریتمی طراحی کنیم که جدولی از همهٔ مقادیر ممکن <math>opt(i,w)</math> داشته باشیم درحالی که هر کدام از آنها را حداکثر یکبار محاسبه کرده باشیم.

با استفاده از لم (*) می‌توان فوراً ثابت کرد که مقدار برگشتی <math>M[n,W]</math> برای در خواست‌های <math>1, 2, \ldots, n</math> و وزن در دسترس <math>W</math>، پاسخ بهینه‌ای است .(<math>M</math> یک آرایهٔ دو بعدی است که مقادیر <math>opt(i,w)</math> را در خود ذخیره کرده‌است)

=== آنالیز آلگوریتم ===
برای الگوریتمی که در این شرایط طراحی کرده‌ایم، اما به یک جدول دو بعدی نیاز داریم، که بازتاب دو بعدی جدول زیرسوالات است که در حال ساخته شدن هستند. به عنوان یک مثال از اجرای این الگوریتم، به یک نمونه با وزن <math>W=6</math> و <math>n=3</math> و آیتم‌هایی با اندازه <math>w_1 = w_2 = 2</math> ''و'' <math>w_3=3</math> توجه کنید. ما در خواهیم یافت که مقدار بهینه <math>opt(3 , 6) = 6</math> خواهدبود (که با استفاده از سومین آیتم و یکی از دو آیتم اول آن را به‌دست آورده‌ایم).

قبل از آن، در مورد برنامه‌ریزی فواصل زمانی موزون، جدول راه حل‌های <math>M</math> را ساخته‌ایم، و مقادیر <math>M[i,W]</math> را با استفاده از مقادیر قبلی در زمان اجرای <math>\mathcal{O}(1)</math>محاسبه می‌کنیم؛ بنابراین مدت زمان اجرا متناسب با تعداد ورودی‌ها به جدول می‌باشد.

(**)

الگوریتم مجموع زیرمجموعه <math>(n,w)</math> بهینه جواب مسئله را محاسبه می‌کند و زمان اجرای آن <math>\mathcal{O}(nw)</math> است.

توجه کنید که زمان اجرای برنامه تابعی از چندجمله‌ای بر حسب n نیست، در واقع یک تابع [[چندجمله ای]] از <math>n</math> و <math>w</math> است. ما چنین الگوریتم‌هایی را «شبه چندجمله‌ای» می‌نامیم. الگوریتم‌های شبه‌چندجمله‌ای می‌توانند به‌طور قابل توجهی کارا باشند هنگامی که اعداد <math>\{w_i\}</math>ی که به عنوان ورودی دریافت می‌کنیم به‌طور قابل توجهی کوچک باشند. هرچند هنگامی که <math>{w_i}</math>ها بزرگ می‌شوند عملکرد این الگوریتم‌ها کاهش می‌یابد.

برای به‌دست آوردن یک مجموعه بهینه <math>s</math> از آیتم‌ها، می‌توانیم آرایهٔ <math>M</math> را با استفاده از روشی که در قبل گفته شد ردیابی کنیم.

(***)

یک جدول <math>M</math> از بهینه مقدارهای زیرمسئله‌ها داده شده‌است. بهترین مجموعه <math>s</math> را می‌توان در زمان <math>\mathcal{O}(n)</math> پیدا کرد.

=== مسئلهٔ کوله پشتی ===
مسئلهٔ کوله پشتی کمی از مسئلهٔ برنامه‌ریزی که در قبل بحث کردیم سخت‌تر است. شرایطی را در نظر بگیرید که مانند قبل آیتم <math>i</math> یک‌وزن نامنفی <math>{w_i}</math> دارد و همچنین یک ارزش جداگانه <math>{v_i}</math> نیز دارد. هدف ما پیدا کردن مجموعه <math>s</math> با بیشینه ارزش <math>\Sigma v_i</math> با محدودیت مجموع وزن این آیتم‌ها نباید از <math>W</math> بیشتر شود.

سخت نیست که الگوریتم پویای خود را برای این مسئله کلی تر گسترش دهیم. ما از مجموعه زیرمسئله‌های مشابه استفاده می‌کنیم، <math>opt(i,w)</math> تا مقدار راه‌حل بهینه را مشخص کنیم با استفاده از زیرمجموعه از آیتم‌های <math>\{1, \ldots, i\}</math> و بیشینه وزن دردسترس <math>w</math>. ما یک راه‌حل بهینه <math>o</math> در نظرمی‌گیریم و دوحالت را با توجه به اینکه <math>n \in o</math> هست یا خیر، مشخص می‌کنیم:

۱- اگر <math>n \notin o</math> آنگاه <math>opt(n,w)=opt(n-1,w)</math>

۲- اگر <math>n \in o</math> آنگاه <math>opt(n,w) = v_n + opt(n-1, w-w_n)</math>

استفاده از این خط از استدلال برای زیرمسئله‌ها نتیجهٔ مشابه (*) را می‌دهد.

(****)

اگر <math>w<w_i</math> آنگاه <math>opt(i,w)=opt(i-1,w)</math>. در غیر این صورت: <math>opt(i,w)=\max\{opt(i-1,w), v_i +opt(i-1,w-w_i)\}</math>

با استفاده از این روش بازگشت، می‌توانیم یه الگوریتم پویای کاملاً مشابه پیاده‌سازی کنیم، که نتیجهٔ روبرو را می‌دهد:

مسئلهٔ کوله پشتی در زمان اجرای <math>\mathcal{O}(nW)</math> قابل حل است.<ref>{{یادکرد کتاب|عنوان=Kleinberg, Jon; Tardos, Éva (2005). Algorithm Design. Pearson. ISBN 978-0-321-29535-4. pp. 266-272}}</ref>

== الگوریتم ضریب دو جمله‌ای با استفاده از برنامه‌ریزی پویا ==
'''ورودی‌ها :''' [[اعداد صحیح]] و مثبت <math>n</math> و <math>k</math> که در آن <math>k \le n</math> است.

'''خروجی‌ها :''' bin2 ضریب دو جمله‌ای <math>\binom{n}{k}</math><syntaxhighlight lang="c" line="1">
int bin2(int n, int k) 
{ 
    int B[n + 1][k + 1]; 
    for(int i = 0;i <= n;i++) 
        for(int j = 0;j <= min(k, i);j++) 
            if(j == 0 || j == i) 
                B[i][j] = 1; 
            else 
                B[i][j] = B[i - 1][j - 1] + B[i - 1][j]; 
    return B[n][k];
}
</syntaxhighlight>

== محدودیت‌های برنامه‌نویسی پویا: مسئلهٔ فروشندهٔ دوره‌گرد ==
برنامه‌نویسی پویا همیشه جواب نمی‌دهد. خوب است که علت این موضوع را بدانیم تا از اینکه در دام الگوریتم‌های نادرست و نابهینه بیفتیم، خودداری کنیم. ابتدا به بررسی مسئلهٔ زیر می‌پردازیم:

مسئله: بلندترین مسیر ساده

ورودی: یک گراف وزن دار  <math>G</math> با راس‌های شروع و پایان  <math>s,t</math> داریم .

خروجی: مسیری از <math>s</math> به <math>t</math> بیابید که بیشترین وزن را داشته باشد و در آن هیچ رأسی را بیش از یک بار نبینیم.

این مسئله از دو جهت با [[مسئله فروشنده دوره‌گرد|مسالهٔ فروشندهٔ دوره‌گرد]](TSP) متفاوت است. اولاً، این مسئله به دنبال یک مسیر است نه یک تور بسته. این تفاوت قابل توجه نیست: به راحتی با اضافه کردن یال <math>(t,s)</math> یک تور بسته به دست می‌آوریم. ثانیاً این مسئله به دنبال مسیر با بیشترین وزن است به جای مسیر با کمترین وزن. باز هم این تفاوت خیلی مهم نیست: این مسئله ما را تشویق می‌کند تا جایی که می‌توان راس‌ها را بازدید کرد (در حالت ایدئال تمام رئوس) دقیقاً مانند TSP. نکتهٔ مهم در این مسئله این است که ما نیابد از هیچ رأسی بیش از یک بار عبور کنیم.

برای گراف‌های غیر وزندار، بزرگترین مسیر از <math>s</math> به <math>t</math> حداکثر <math>n-1</math> یال دارد. پیدا کردن چنین «مسیرهای همیلتونی» یک مسئلهٔ مهم در نظریه گراف است.

چه زمان‌هایی الگوریتم‌های برنامه‌نویسی پویا درست هستند؟

درستی الگوریتم‌های برنامه‌نویسی پویا وابسته به روابط بازگشتی‌ای است که بر پایه آن بنا شده‌اند. فرض کنید ما تابع <math>LP[i,j]</math> را به عنوان تابعی که نمایانگر طول بلندترین مسیر ساده از <math>i</math> به <math>j</math> است تعریف کنیم. توجه کنید که بلندترین مسیر ساده از <math>i</math> به <math>j</math> باید قبل از رسیدن به <math>j</math>، تعدادی رئوس <math>x</math> را بازید کند؛ بنابراین، آخرین یال بازدید شده باید به صورت <math>(x,j)</math> باشد. این موضوع رابطهٔ بازگشتی روبرو را برای محاسبهٔ طول بلندترین مسیر ساده پیشنهاد می‌کند:

<math>LP[i,j] = \max_{(x,j) \in E} LP[i, x] + c(x,j)</math>

که در آن <math>c(x,j)</math> وزن یال <math>(x,j)</math> است.

ایده به نظر معقول می‌رسد، اما شما می‌توانید مشکلات را ببینید؟ به دو مورد زیر توجه کنید:

اولاً، این رابطهٔ بازگشتی منجر به هیچ‌گونه سادگی نمی‌شود. ما از کجا می‌دانیم که راس <math>j</math> قبلاً در بلندترین مسیر ساده از <math>i</math> به <math>x</math> ظاهر نشده‌است؟ اگر ظاهر شده باشد، آنگاه اضافه کردن یال <math>(x,j)</math> منجر به ایجاد دور در گراف می‌شود. برای جلوگیری از چنین چیزی، ما باید یک [[بازگشت (علوم رایانه)|تابع بازگشتی]] متفاوت تعریف کنیم که صراحتاً ذخیره کند که ما در چه مکان‌هایی حضور داشتیم. شاید بتوانیم <math>LP'[i,j,k]</math> را تعریف کنیم به عنوان تابعی که نمایانگر بلندترین مسیر ساده از <math>i</math> به <math>j</math> است و از راس <math>k</math> عبور نمی‌کند؟ شاید این یک قدم در جهت درست باشد ولی هنوز ما را به یک تابع بازگشتی قابل اطمینان نمی‌رساند.

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

برنامه‌نویسی پویا را می‌توان در هر مسئله‌ای که اصل بهینه بودن را رعایت می‌کند بکار برد. برای مثال، در تصمیم‌گیری اینکه یک تطابق رشته‌ای را به‌وسیلهٔ جابه‌جایی، اضافه کردن یا حذف کردن گسترش دهیم، ما نیازی نداریم که بدانیم کدام دنباله از عملگرها تا آن زمان انجام شده‌است. در واقع، ممکن است دنباله‌های متفاوت ویرایش وجود داشته باشد که هزینهٔ <math>C</math> را بر روی <math>p</math> حرف از الگوی <math>P</math> و <math>t</math> حرف از الگوی <math>T</math> اعمال می‌کند.

مسئله‌ها هنگامی از اصل بهینگی پیروی نمی‌کنند که به جای هزینهٔ عملیات، مشخصهٔ عملیات مهم می‌شود. چنین چیزی می‌تواند شکلی از مسئلهٔ فاصلهٔ ویرایش که در آن مجاز به استفاده از عملگرها با یک ترتیب خاص نیستیم، باشد. هر چند بسیاری از مسائل [[ترکیبیات]] از اصل بهینگی پیروی می‌کنند.

چه زمانی الگوریتم‌های برنامه‌نویسی پویا کارا هستند؟

زمان اجرای الگوریتم‌های برنامه‌نویسی پویا تابع دو چیز است :۱) تعداد زیر مسئله‌هایی که ما باید آنها را بررسی کنیم ۲) چه قدر طول می‌کشد تا هر زیرمسئله را بررسی کنیم. مورد اول – که معمولاً فضای حالات نامیده‌می‌شود – مشکل جدی‌تری است. تاکنون در مسئله‌هایی که بررسی کردیم، زیر مسئله‌ها به‌وسیلهٔٔ مکان‌های توقف در ورودی مشخص می‌شدند. این به این خاطر است که موضوعات ترکیبیاتی که روی آنها کار می‌شده مانند رشته‌ها، دنباله‌های عددی، چندضلعی‌ها و … به صورت ضمنی در عناصر خود دارای یک ترتیب هستند. این ترتیب را نمی‌توان به هم زد مگر با عوض کردن صورت مسئله. هنگامی که ترتیب مشخص شد، مکان‌های توقف یا حالات نسبتاً کمی وجود خواهد داشت، به طوری که ما می‌توانیم الگوریتم‌های بهینه را به‌دست بیاوریم.

هنگامی که اشیا به صورت مشخص دارای یک ترتیب نیستند، ما تعداد نمایی از زیر مسئله‌ها را به‌دست می‌آوریم (برخلاف بالا). فرض کنید حالات زیرمسئله ما شامل کل مسیرها از راس شروع تا مقصد است. پس <math>LP[i,j,P]</math> مشخص کنندهٔ بلندترین مسیر ساده از <math>i</math> تا <math>j</math> است که <math>P</math> دنبالهٔ دقیق رئوس میانی بین <math>i</math> و <math>j</math> است که در مسیر آمده‌است. رابطهٔ بازگشتی روبرو برای محاسبهٔ مقدار بالا است که در آن <math>P+x</math> به معنی اضافه کردن <math>x</math> به انتهای <math>P</math> است:

<math>LP[i, j, P+x] = \max _{(x,j) \in E,x,j \notin P} LP[i,x,P] + c(x,j)</math>

این رابطه درست است اما چه قدر بهینه است؟ مسیر <math>P</math> شامل حداکثر <math>n-3</math> راس با یک ترتیب مشخص است. پس ما <math>(n-3)!</math> از چنین مسیرهایی داریم، در واقع، این الگوریتم واقعاً از جستجوی ترکیبیاتی استفاده می‌کند تا تمامی مسیرهای بین را بسازد.

ما با این ایده می‌توانیم یک کار بهتر انجام دهیم. فرض کنید که <math>LP'[i,j,S]</math> مشخص‌کنندهٔ بلندترین مسیر از <math>i</math> به <math>j</math> است که رأس‌های میانی روی مسیر دقیقاً در مجموعه <math>S</math> قرار دارد. بنابر این اگر <math>S =\{a,b,c\}</math>، دقیقاً ۶ مسیر وجود دارد:

<math>S: iabcj, iacbj, ibacj, ibcaj, icabj, icbaj</math>

این فضای حالت حداکثر <math>2^n</math> حالت دارد، بنابراین کوچکتر از مسیرهای محاسبه شده در قسمت قبل است. علاوه بر این، تابع را می‌توان با رابطه بازگشتی روبرو محاسبه کرد:

<math>LP'[i,j,S \cup \{x\}] = \max_{(x,j) \in E, x,j \notin S} LP[i,x,S] + c(x,j)</math>

پس می‌توان بلندترین مسیر ساده از <math>i</math> به <math>j</math> را با بیشینه کردن روی مجموعهٔ تمام رئوس بین این دو رأس به دست آورد.

<math>LP[i,j] = \max_S LP'[i, j, S]</math>

تنها <math>2^n</math> زیر مجموعه از <math>n</math> راس وجود دارد، پس این یک بهبود چشمگیر روی شمردن تمام <math>n!</math> تور ممکن است. در واقع این روش می‌تواند برای حل TSP هنگامی که بیش از ۳۰ رأس داریم استفاده شود. همچنان برنامه‌نویسی پویا بیشترین تأثیر را بر اشیایی که به صورت مناسب مرتب شده‌اند دارد.<ref>{{یادکرد کتاب|عنوان=Skiena, Steven S. (2008). The Algorithm Design Manual. Springer. ISBN 978-1849967204. pp. 301-304}}</ref>

== الگوریتم‌هایی که از برنامه‌نویسی پویا استفاده می‌کنند ==
* جواب‌های بازگشت‌کننده به مدل‌های مشبک برای به هم پیوستن پروتئین و دی‌ان‌ای
* [[استنتاج معکوس]] به عنوان راه حلی برای مسائل بهینه‌سازی پویای [[زمان پیوسته و زمان گسسته|زمان‌گسسته]] با افق متناهی
* روش ضرایب نامعین را می‌توان برای حل [[معادله بلمن|معادلهٔ بلمن]] در مسائل بهینه‌سازی پویای [[سیستم تغییرناپذیر با زمان|زمان‌تغییرناپذیر]] [[تنزیل]]<nowiki/>یافتهٔ زمان‌گسسته با افق نامتناهی به کار برد.
* بسیاری از الگوریتم‌های [[رشته (علوم رایانه)|رشته]] از جمله [[مسئله بزرگترین زیردنباله مشترک|بلندترین زیردنبالهٔ مشترک]]،<ref>{{یادکرد کتاب|عنوان=Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. pp. 390-396}}</ref> [[طولانی‌ترین زیررشته صعودی|بلندترین زیردنبالهٔ صعودی]]، [[بزرگترین زیررشته مشترک|بلندترین زیررشتهٔ مشترک]]، [[فاصله لون‌اشتاین|فاصلهٔ لونشتاین]]<ref>{{یادکرد کتاب|عنوان=Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. pp. 306-408}}</ref>
* بسیاری از مسائل الگوریتمی [[گراف (ریاضی)|گراف]]<nowiki/>ها را می‌توان به صورت بهینه برای گراف‌هایی با [[عرض درخت]] یا خوشهٔ کران‌دار توسط برنامه‌نویسی پویا روی تجزیهٔ درختی گراف حل کرد.
* [[الگوریتم سی وای کا|الگوریتم کاک-یانگر-کاسامی(CYK)]] که امکان و چگونگی ساخت یک رشته توسط یک [[گرامر مستقل از متن]] را تعیین می‌کند
* الگوریتم کنوث برای شکستن خط که ناهمواری را کمینه می‌کند
* کاربرد جدول جابجایی و تکذیب در شطرنج کامپیوتری
* الگوریتم [[الگوریتم ویتربی|ویتربی]]<ref>{{یادکرد کتاب|عنوان=Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. pp. 408-409}}</ref> (استفاده‌شده برای [[مدل پنهان مارکف|مدل‌های نهان مارکوف]] و به‌طور خاص [[برچسب‌زنی اجزای کلام]])

== پانویس ==
{{پانویس|۲}}

== منابع ==
* هیلیر، فردریک؛ لیبرمن، جرالد. ج (۱۳۸۲). [[تحقیق در عملیات]]، ترجمه محمد مدرس و اردوان آصف‌وزیری، تهران: نشر جوان، چاپ دهم.
* نیپولیتان، ریچارد؛ نعیمی‌پور، کیومرث (۱۳۹۰). طراحی الگوریتم‌ها، ترجمه [[عین‌الله جعفرنژاد قمی]]، بابل: انتشارات علوم رایانه.

== پیوند به بیرون ==
{{چپ‌چین}}
* [https://web.archive.org/web/20081103041312/http://20bits.com/2007/05/08/introduction-to-dynamic-programming/ An Introduction to Dynamic Programming]
* [https://web.archive.org/web/20160117155947/http://dyna.org/ Dyna], a declarative programming language for dynamic programming algorithms
* Wagner, David B. , 1995, "[http://citeseer.ist.psu.edu/268391.html Dynamic Programming.]" An introductory article on dynamic programming in [[متمتیکا]].
* [https://web.archive.org/web/20051202161754/http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch21.html Ohio State University: CIS 680: class notes on dynamic programming], by Eitan M. Gurari
* [http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html A Tutorial on Dynamic programming]
* [http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/LectureNotes/index.htm MIT course on algorithms] - Includes a video lecture on DP along with lecture notes—See lecture 15.
* [http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic More DP Notes]
* King, Ian, 2002 (1987), "[https://web.archive.org/web/20060614082907/http://www.business.auckland.ac.nz/Departments/econ/workingpapers/full/Text230.pdf A Simple Introduction to Dynamic Programming in Macroeconomic Models.]" An introduction to dynamic programming as an important tool in economic theory.
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg Dynamic Programming: from novice to advanced] A TopCoder.com article by Dumitru on Dynamic Programming
* [http://bibiserv.techfak.uni-bielefeld.de/adp/ Algebraic Dynamic Programming] - a formalized framework for dynamic programming, including an [http://bibiserv.techfak.uni-bielefeld.de/dpcourse entry-level course] to DP, University of Bielefeld
* Dreyfus, Stuart, "[https://web.archive.org/web/20070110214657/http://www.eng.tau.ac.il/~ami/cd/or50/1526-5463-2002-50-01-0048.pdf Richard Bellman on the birth of Dynamic Programming.]"
* [https://web.archive.org/web/20080626183359/http://www.avatar.se/lectures/molbioinfo2001/dynprog/dynamic.html Dynamic programming tutorial]
{{پایان چپ‌چین}}
* الگوریتمستان، [http://www.labod.ir/algorithms/post.aspx?no=14 روش برنامه‌نویسی پویا]

== جستارهای وابسته ==
* [[معادلات بلمن]]
* [[برنامه‌ریزی خطی]]
* [[فرایند مارکف]]
* [[ضرب زنجیره‌ای ماتریس]]
* [[مسئله یافتن کوتاهترین مسیر]]

{{الگوریتم‌های بهینه‌سازی}}
{{تجزیه‌کنندگان}}

[[رده:برنامه‌نویسی پویا]]
[[رده:الگوریتم‌ها]]
[[رده:الگوریتم‌های بهینه‌سازی]]
[[رده:بهینه‌سازی]]
[[رده:بهینه‌سازی ریاضی]]
[[رده:تحقیق در عملیات]]
[[رده:روش‌های بهینه‌سازی]]
[[رده:کنترل بهینه]]
[[رده:معادلات]]
[[رده:مهندسی سامانه‌ها]]
[[رده:ویکی‌سازی رباتیک]]