Dynamic programming — البرمجة الديناميكية

البرمجة الديناميكية (DP) (بالإنجليزية: dynamic programming) هي طريقة لحل مسائل الاستمثال المعقدة، تقوم على تقسيم المسألة الأصلية إلى سلسلة من المسائل الفرعية الأبسط. تُطبَّق هذه الطريقة على عمليات اتخاذ القرار متعددة المراحل، حيث يمكن بناء الحل الأمثل للمسألة بأكملها من الحلول المثلى لمسائلها الفرعية.

صاغ هذا المصطلح عالم الرياضيات الأمريكي ريتشارد بيلمان في خمسينيات القرن العشرين. في هذا السياق، لا تعني كلمة «برمجة» كتابة شيفرة برمجية، بل تشير إلى «التخطيط» أو «وضع خطة عمل مثلى».

الخصائص والمبرهنات الأساسية

تعتمد قابلية تطبيق البرمجة الديناميكية على مسألة ما على توفر خاصيتين أساسيتين فيها.

مبدأ بيلمان للأمثلية

المفهوم المركزي لهذه الطريقة هو مبدأ بيلمان للأمثلية (بالإنجليزية: Bellman's principle of optimality). ينص هذا المبدأ على أنه: مهما كانت الحالة الأولية والقرار الأولي، يجب أن تشكل القرارات اللاحقة استراتيجية مثلى بالنسبة للحالة الناتجة عن القرار الأول.

بعبارة أخرى، أي جزء من مسار أمثل هو بحد ذاته مسار أمثل. تسمح هذه الخاصية بتقسيم المسألة الكلية إلى سلسلة من المسائل الفرعية الأبسط وحلها بشكل عودي (recursively).

المسائل الفرعية المتداخلة

تمتلك المسألة خاصية المسائل الفرعية المتداخلة (بالإنجليزية: overlapping subproblems) إذا كانت الحلول العودية لها تؤدي إلى ظهور نفس المسائل الفرعية بشكل متكرر. تتجنب البرمجة الديناميكية الحسابات المكررة عن طريق تخزين حلول المسائل الفرعية التي تمت مواجهتها بالفعل (تُعرف هذه التقنية بالتحفيظ (memoization) أو الجدولة)، مما يزيد بشكل كبير من الكفاءة مقارنة بالبحث العودي الساذج.

معادلة بيلمان

ينبثق من مبدأ الأمثلية علاقة التكرار الأساسية لهذه الطريقة، وهي معادلة بيلمان. تربط هذه المعادلة «قيمة» (المكسب الأمثل أو التكلفة) للحالة الحالية بقيم الحالات اللاحقة. بشكل عام، لعملية حتمية متعددة المراحل وذات دالة هدف تجميعية، تأخذ المعادلة الشكل التالي:

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

حيث:

• $k$ — رقم الخطوة (من $m$ إلى 1)؛
• $x$ — حالة النظام عند الخطوة $k-1$؛
• $y$ — القرار المتحكَّم به الذي يتم اتخاذه عند الخطوة $k$؛
• ${\phi }_k(x,y)$ — المكسب (أو التكلفة) عند الخطوة k؛
• $f_k(x,y)$ — الدالة التي تحدد الحالة الجديدة للنظام؛
• $V_k(s)$ — القيمة المثلى لدالة الهدف للمسألة الفرعية التي تبدأ عند الخطوة $k$ في الحالة $s$.

تُحل المعادلة بشكل تسلسلي، وعادةً ما يكون ذلك «من النهاية»، أي بالتحرك من الخطوة الأخيرة إلى الأولى.

أمثلة على التطبيقات

• مسألة المسار الأقصر في المخططات: تمتلك هذه المسألة خاصية البنية التحتية المثلى، حيث إن أي جزء من المسار الأقصر هو بحد ذاته مسار أقصر. تعد خوارزمية بلمان-فورد وخوارزمية فلويد-وارشال أمثلة كلاسيكية على تطبيق البرمجة الديناميكية لحل هذه المسألة.
• مسألة حقيبة الظهر: مسألة التعبئة المثلى لحقيبة ظهر ذات سعة محدودة بأغراض لها قيم وأوزان مختلفة. تسمح البرمجة الديناميكية بحل هذه المسألة من خلال فحص العناصر بشكل تسلسلي وحساب القيمة القصوى عند كل خطوة لجميع القيم الممكنة للسعة المتبقية.
• مسألة تخصيص الموارد: توزيع مورد محدود (مثل الاستثمارات) بين عدة مشاريع لتعظيم العائد الإجمالي.

المحددات والقيود

القيد الرئيسي لهذه الطريقة هو لعنة الأبعاد (بالإنجليزية: curse of dimensionality) — وهو مصطلح صاغه بيلمان لوصف النمو الأسي لعدد الحالات، وبالتالي للتعقيد الحسابي، مع زيادة عدد المتغيرات التي تصف حالة النظام. يحد هذا من التطبيق العملي للبرمجة الديناميكية الدقيقة للمسائل ذات الأبعاد الكبيرة جدًا.

مفاهيم ذات صلة

• بحوث العمليات
• نظرية التحكم الأمثل
• عملية ماركوف لاتخاذ القرار (تعميم عشوائي)
• معادلة هاملتون-جاكوبي-بيلمان (نظير للزمن المستمر)