برنامه‌نویسی پویا
محدودیت‌های برنامه‌نویسی پویا: مسئلهٔ فروشندهٔ دوره‌گرد

برنامه‌نویسی پویا همیشه جواب نمی‌دهد. خوب است که علت این موضوع را بدانیم تا از اینکه در دام الگوریتم‌های نادرست و نابهینه بیفتیم، خودداری کنیم. ابتدا به بررسی مسئلهٔ زیر می‌پردازیم:
مسئله: بلندترین مسیر ساده
ورودی: یک گراف وزن دار   G با راس‌های شروع و پایان   s,t داریم .
خروجی: مسیری از  s به  t بیابید که بیشترین وزن را داشته باشد و در آن هیچ رأسی را بیش از یک بار نبینیم.
این مسئله از دو جهت با مسالهٔ فروشندهٔ دوره‌گرد(TSP) متفاوت است. اولاً، این مسئله به دنبال یک مسیر است نه یک تور بسته. این تفاوت قابل توجه نیست: به راحتی با اضافه کردن یال  (t,s) یک تور بسته به دست می‌آوریم. ثانیاً این مسئله به دنبال مسیر با بیشترین وزن است به جای مسیر با کمترین وزن. باز هم این تفاوت خیلی مهم نیست: این مسئله ما را تشویق می‌کند تا جایی که می‌توان راس‌ها را بازدید کرد (در حالت ایدئال تمام رئوس) دقیقاً مانند TSP. نکتهٔ مهم در این مسئله این است که ما نیابد از هیچ رأسی بیش از یک بار عبور کنیم.
برای گراف‌های غیر وزندار، بزرگترین مسیر از  s به  t حداکثر  n-1 یال دارد. پیدا کردن چنین «مسیرهای همیلتونی» یک مسئلهٔ مهم در نظریه گراف است.
چه زمان‌هایی الگوریتم‌های برنامه‌نویسی پویا درست هستند؟
درستی الگوریتم‌های برنامه‌نویسی پویا وابسته به روابط بازگشتی‌ای است که بر پایه آن بنا شده‌اند. فرض کنید ما تابع  LP[i,j] را به عنوان تابعی که نمایانگر طول بلندترین مسیر ساده از  i به  j است تعریف کنیم. توجه کنید که بلندترین مسیر ساده از  i به  j باید قبل از رسیدن به  j، تعدادی رئوس  x را بازید کند؛ بنابراین، آخرین یال بازدید شده باید به صورت  (x,j) باشد. این موضوع رابطهٔ بازگشتی روبرو را برای محاسبهٔ طول بلندترین مسیر ساده پیشنهاد می‌کند:
LP[i,j]=\max _{(x,j)\in E}LP[i,x]+c(x,j)
که در آن  c(x,j) وزن یال  (x,j) است.
ایده به نظر معقول می‌رسد، اما شما می‌توانید مشکلات را ببینید؟ به دو مورد زیر توجه کنید:
اولاً، این رابطهٔ بازگشتی منجر به هیچ‌گونه سادگی نمی‌شود. ما از کجا می‌دانیم که راس  j قبلاً در بلندترین مسیر ساده از  i به  x ظاهر نشده‌است؟ اگر ظاهر شده باشد، آنگاه اضافه کردن یال  (x,j) منجر به ایجاد دور در گراف می‌شود. برای جلوگیری از چنین چیزی، ما باید یک تابع بازگشتی متفاوت تعریف کنیم که صراحتاً ذخیره کند که ما در چه مکان‌هایی حضور داشتیم. شاید بتوانیم  LP'[i,j,k] را تعریف کنیم به عنوان تابعی که نمایانگر بلندترین مسیر ساده از  i به  j است و از راس  k عبور نمی‌کند؟ شاید این یک قدم در جهت درست باشد ولی هنوز ما را به یک تابع بازگشتی قابل اطمینان نمی‌رساند.
مشکل دوم مربوط به دستورالعمل ارزیابی است. ابتدا چه چیزی را ارزیابی می‌کنید؟ چون هیچ ترتیب چپ به راست یا بزرگ به کوچکی از رئوس وجود ندارد، واضح نیست که زیرمسئله‌های کوچکتر چه هستند. بدون داشتن چنین ترتیبی، ما در یک دور بینهایت می‌افتیم تا زمانی که بخواهیم کاری انجام دهیم.
برنامه‌نویسی پویا را می‌توان در هر مسئله‌ای که اصل بهینه بودن را رعایت می‌کند بکار برد. برای مثال، در تصمیم‌گیری اینکه یک تطابق رشته‌ای را به‌وسیلهٔ جابه‌جایی، اضافه کردن یا حذف کردن گسترش دهیم، ما نیازی نداریم که بدانیم کدام دنباله از عملگرها تا آن زمان انجام شده‌است. در واقع، ممکن است دنباله‌های متفاوت ویرایش وجود داشته باشد که هزینهٔ  C را بر روی  p حرف از الگوی  P و  t حرف از الگوی  T اعمال می‌کند.
مسئله‌ها هنگامی از اصل بهینگی پیروی نمی‌کنند که به جای هزینهٔ عملیات، مشخصهٔ عملیات مهم می‌شود. چنین چیزی می‌تواند شکلی از مسئلهٔ فاصلهٔ ویرایش که در آن مجاز به استفاده از عملگرها با یک ترتیب خاص نیستیم، باشد. هر چند بسیاری از مسائل ترکیبیات از اصل بهینگی پیروی می‌کنند.
چه زمانی الگوریتم‌های برنامه‌نویسی پویا کارا هستند؟
زمان اجرای الگوریتم‌های برنامه‌نویسی پویا تابع دو چیز است :۱) تعداد زیر مسئله‌هایی که ما باید آنها را بررسی کنیم ۲) چه قدر طول می‌کشد تا هر زیرمسئله را بررسی کنیم. مورد اول – که معمولاً فضای حالات نامیده‌می‌شود – مشکل جدی‌تری است. تاکنون در مسئله‌هایی که بررسی کردیم، زیر مسئله‌ها به‌وسیلهٔٔ مکان‌های توقف در ورودی مشخص می‌شدند. این به این خاطر است که موضوعات ترکیبیاتی که روی آنها کار می‌شده مانند رشته‌ها، دنباله‌های عددی، چندضلعی‌ها و … به صورت ضمنی در عناصر خود دارای یک ترتیب هستند. این ترتیب را نمی‌توان به هم زد مگر با عوض کردن صورت مسئله. هنگامی که ترتیب مشخص شد، مکان‌های توقف یا حالات نسبتاً کمی وجود خواهد داشت، به طوری که ما می‌توانیم الگوریتم‌های بهینه را به‌دست بیاوریم.
هنگامی که اشیا به صورت مشخص دارای یک ترتیب نیستند، ما تعداد نمایی از زیر مسئله‌ها را به‌دست می‌آوریم (برخلاف بالا). فرض کنید حالات زیرمسئله ما شامل کل مسیرها از راس شروع تا مقصد است. پس  LP[i,j,P] مشخص کنندهٔ بلندترین مسیر ساده از  i تا  j است که  P دنبالهٔ دقیق رئوس میانی بین  i و  j است که در مسیر آمده‌است. رابطهٔ بازگشتی روبرو برای محاسبهٔ مقدار بالا است که در آن  P+x به معنی اضافه کردن  x به انتهای  P است:
LP[i,j,P+x]=\max _{(x,j)\in E,x,j\notin P}LP[i,x,P]+c(x,j)
این رابطه درست است اما چه قدر بهینه است؟ مسیر  P شامل حداکثر  n-3 راس با یک ترتیب مشخص است. پس ما  (n-3)! از چنین مسیرهایی داریم، در واقع، این الگوریتم واقعاً از جستجوی ترکیبیاتی استفاده می‌کند تا تمامی مسیرهای بین را بسازد.
ما با این ایده می‌توانیم یک کار بهتر انجام دهیم. فرض کنید که  LP'[i,j,S] مشخص‌کنندهٔ بلندترین مسیر از  i به  j است که رأس‌های میانی روی مسیر دقیقاً در مجموعه  S قرار دارد. بنابر این اگر  S=\{a,b,c\}، دقیقاً ۶ مسیر وجود دارد:
S:iabcj,iacbj,ibacj,ibcaj,icabj,icbaj
این فضای حالت حداکثر  2^{n} حالت دارد، بنابراین کوچکتر از مسیرهای محاسبه شده در قسمت قبل است. علاوه بر این، تابع را می‌توان با رابطه بازگشتی روبرو محاسبه کرد:
LP'[i,j,S\cup \{x\}]=\max _{(x,j)\in E,x,j\notin S}LP[i,x,S]+c(x,j)
پس می‌توان بلندترین مسیر ساده از  i به  j را با بیشینه کردن روی مجموعهٔ تمام رئوس بین این دو رأس به دست آورد.
LP[i,j]=\max _{S}LP'[i,j,S]
تنها  2^{n} زیر مجموعه از  n راس وجود دارد، پس این یک بهبود چشمگیر روی شمردن تمام  n! تور ممکن است. در واقع این روش می‌تواند برای حل TSP هنگامی که بیش از ۳۰ رأس داریم استفاده شود. همچنان برنامه‌نویسی پویا بیشترین تأثیر را بر اشیایی که به صورت مناسب مرتب شده‌اند دارد.