Dynamic Programming

البرمجة الديناميكية (DP) هي تقنيّة حلّ مسائل القرار متعدّدة المراحل التي قدّمها Richard Bellman في كتابه عام 1957 (*Dynamic Programming*, Princeton University Press)؛ تحلّل المسألة إلى مسائل فرعيّة متداخلة، تخزّن النتائج الوسيطة في جدول (memoization أو tabulation) وتحلّ عَوديًّا عبر معادلة Bellman V(s) = max_a {r(s, a) + γ V(s')}. مسألة حقيبة الظهر هي المثال الكلاسيكي للبرمجة الديناميكيّة — يقدّم Bellman إطار DP على knapsack في كتاب 1957؛ تعقيد الزمن O(N×W) **شبه متعدّد الحدود** (متعدّد الحدود في قيمة W، أُسّي في طول بتّاتها). تطبيقات كلاسيكيّة أخرى: المسارات الأقصر (Bellman-Ford)، إدارة المخزون (تحجيم الدُّفعات لـWagner-Whitin)، استبدال المعدّات (Bellman 1955)، عمليّات القرار العشوائيّة (Markov Decision Process)، محاذاة المتتاليات (Needleman-Wunsch)، التحليل النحوي (CYK)، ترتيب ضرب سلاسل المصفوفات. للبرمجة الديناميكيّة طوران: **DP حتميّة** (لكلّ مرحلة نتيجة معلومة) و**DP عشوائيّة** (لكلّ مرحلة نتيجة احتماليّة — عمليّات Markov). تتطلّب قابليّة التطبيق بنية فرعيّة مثلى (تتركّب أمثليّات المسائل الفرعيّة في الأمثليّة العامّة) ومسائل فرعيّة متداخلة (تتكرّر). البرمجة الديناميكيّة التقريبيّة (ADP) والبرمجة الديناميكيّة الثنائيّة العشوائيّة (SDDP) توسّعان DP لمسائل عشوائيّة كبيرة. Bellman 1957 + Bellman وDreyfus 1962 + Bertsekas 1995 هي المراجع الكلاسيكيّة.