البرمجة الديناميكية

قبل بيلمان، كانت أمثَلَة سلسلة من القرارات تعني استعراض كل توليفة ممكنة. عملية بـ $N$ مرحلة و$M$ خيار في كل مرحلة تُنتج $M^N$ مساراً محتملاً، والأعداد تتضخم بسرعة مخيفة: 10 مراحل × 10 خيارات = 10 مليارات مسار. حتى المسائل الواقعية البسيطة — كسلاسل التوريد ومسارات الطيران وجداول الإنتاج — تتجاوز بسرعة القدرة الحاسوبية لأي آلة.

السبب الجذري لهذا الانفجار هو تكرار الحساب دون داعٍ. في بحث تعاودي ساذج تُعاد زيارة الحالة الوسيطة نفسها مراراً عبر مسارات مختلفة. مسألة من 20 مرحلة قد تُعيد حلّ المسألة الجزئية ذاتها ملايين المرات دون أن تلاحظ أن الإجابة حُسبت من قبل.

الملاحظة المحورية لبيلمان كانت حول بنية الحلول المُثلى، وصاغها في مبدأ واحد:

مبدأ الأمثَلَة. أي سياسة مُثلى تتمتع بالخاصية التالية: مهما كانت الحالة الابتدائية والقرار الأول، فإن القرارات المتبقية يجب أن تشكّل بدورها سياسة مُثلى من الحالة الناتجة فصاعداً.

بعبارة أبسط: أفضل مسار من موقعك الحالي إلى الوجهة لا يعتمد على كيف وصلت إلى موقعك. لو كنت تسافر من المدينة أ إلى المدينة ي عبر المدينة ب، وكان المسار الأمثل أ→ي يمرّ بالمدينة ب، فإن الجزء ب→ي يجب أن يكون بذاته المسار الأمثل من ب إلى ي. ولو لم يكن كذلك، لاستبدلته بمسار أفضل وحسّنت الرحلة كلها — وهذا يناقض فرض أن أ→ي كان أمثل أصلاً.

هذا المبدأ هو ما يجعل التفكيك ممكناً. ما دام الذيل الأمثل لا يعتمد على التاريخ، يمكنك حلّ كل مسألة جزئية مرة واحدة ثم إعادة استخدام حلّها بغضّ النظر عن المسار الذي أوصلك إليها.

يمكن تحويل مبدأ الأمثَلَة مباشرة إلى معادلة تعاودية. قبل الدخول في الرموز، الفكرة ببساطة:

قيمة أي حالة تساوي أفضل ما يمكنك فعله الآن (المكافأة الفورية) مضافاً إليه قيمة الحالة التي سينقلك إليها ذلك الفعل (القيمة المستقبلية).

تخيّل أنك واقف عند مفترق طرق: تختار الفرع الذي يعطيك أعلى عائد فوري بالإضافة إلى أفضل رحلة متبقية. هذا تعريف تعاودي بامتياز — القيمة عند كل مفترق تعتمد على القيمة عند المفترق الذي يليه — وهذا ما يُعرف بـمعادلة بيلمان.

اقرأ المعادلة كوصفة: لتقييم جودة الحالة $s$، جرّب كل فعل $a$ واحسب ما تحصل عليه فوراً $r(s,a)$ مضافاً إليه القيمة المخصومة للحالة التالية $\gamma V^*(s')$، ثم اختر الفعل الذي يعطي أعلى مجموع. في المسائل الحتمية يختفي الجمع على $s'$ لأن كل فعل يقود إلى حالة واحدة محدّدة. أما في المسائل العشوائية فنأخذ القيمة المستقبلية المتوقعة، مرجّحة باحتمالات الانتقال $P(s'|s,a)$.

قوة البرمجة الديناميكية تأتي من خاصية بنيوية موجودة في كثير من مسائل الأمثَلَة: المسائل الجزئية المتداخلة. حين تفكّك مسألة تعاودياً، تحتاج فروع مختلفة من الشجرة إلى الإجابة الجزئية ذاتها. وبدون حفظ النتائج يتكرّر حسابها عدداً أسّياً من المرات.

المثال الكلاسيكي هو متتالية فيبوناتشي: $F(n) = F(n-1) + F(n-2)$. شجرة الاستدعاءات الساذجة لحساب $F(5)$ تحسب $F(2)$ ثلاث مرات و$F(3)$ مرتين. وعند $F(40)$ تتجاوز الشجرة مليار عقدة — رغم أن المسائل الجزئية الفريدة لا تزيد عن 41 فقط. الحفظ المُسبق — أي تخزين كل $F(k)$ عند حسابه لأول مرة — يختزل العمل من أسّي إلى خطّي.

النمط نفسه يظهر في مسائل بيلمان كتوزيع الموارد وإدارة المخزون وأقصر المسارات: الحالات تُزار من سلاسل قرارات مختلفة، وحلّ كل حالة مرة واحدة هو ما يجعل معادلة بيلمان قابلة للحلّ عملياً.

هناك طريقتان لتفادي تكرار الحساب في البرمجة الديناميكية:

من الأعلى إلى الأسفل بـالحفظ المُسبق — تكتب الحلّ التعاودي الطبيعي، لكن قبل حساب أي مسألة جزئية تتحقّق من ذاكرة مؤقتة: هل حُسبت من قبل؟ إن كانت الإجابة موجودة تُعيدها فوراً. الميزة هنا أنك لا تحلّ إلا المسائل الجزئية المطلوبة فعلاً، وتحافظ على أسلوب التفكير التعاودي. يبدأ الحلّ من المسألة الأصلية وينزل تدريجياً.

من الأسفل إلى الأعلى بـالجدولة — تحدّد جميع المسائل الجزئية، ترتّبها حسب الحجم، وتحلّها من الأصغر في حلقة تكرارية تملأ جدولاً صفّاً تلو صف. حين تصل إلى المسألة الأصلية تكون كل ما تعتمد عليه محلولاً في الجدول. هذا الأسلوب يتجنّب عبء التعاود كلياً، وغالباً يستهلك ذاكرة أقل لأنك تحتاج فقط إلى الاحتفاظ بالصف السابق.

كلتا الطريقتين تصلان إلى الإجابة المُثلى ذاتها. الفرق عملياً بين المقروئية والأداء: الحفظ المُسبق يتوافق طبيعياً مع الصياغة التعاودية لمعادلة بيلمان، بينما الجدولة عادةً أسرع وأسهل في تقليل استهلاك الذاكرة.

وضع كتاب بيلمان إطاراً عامّاً لمسائل القرار التتابعي يتكرّر في بحوث العمليات والاقتصاد والذكاء الاصطناعي. عناصر هذا الإطار:

• الحالات ($s$): الوصف الكامل للنظام عند مرحلة معيّنة — كالمخزون المتوفر أو الموقع على الخريطة أو الأموال المتبقية.
• المراحل ($t$): الخطوات الزمنية أو نقاط اتخاذ القرار. كل مرحلة هي فرصة للتصرّف.
• الأفعال ($a$): الخيارات المتاحة في كل حالة — كمية الطلب، أو الطريق المختار، أو كيفية توزيع الموارد.
• الانتقال: كيف تتغيّر الحالة بعد اتخاذ فعل — إما حتمياً ($s' = T(s, a)$) أو عشوائياً ($s' \sim P(\cdot|s,a)$).
• المكافأة / التكلفة: العائد الفوري أو الكلفة عند اختيار الفعل $a$ في الحالة $s$.
• السياسة ($\pi$): قاعدة تحدّد الفعل المناسب لكل حالة. الهدف إيجاد السياسة المُثلى $\pi^*$ التي تُعظّم إجمالي المكافآت (أو تُقلّل إجمالي التكاليف) عبر جميع المراحل.

معادلة بيلمان تربط هذه العناصر ببعضها: نبدأ من المرحلة الأخيرة حيث القيمة هي ببساطة المكافأة النهائية، ثم نعمل عكسياً. عند كل مرحلة تعتمد القيمة المُثلى فقط على الحالة الراهنة وعلى المرحلة التالية التي حُلّت مسبقاً. هذا الاستقراء العكسي هو محرّك البرمجة الديناميكية.

بيلمان نفسه حدّد القيد الجوهري لأسلوبه. إذا كانت الحالة متّجهاً من $d$ متغير مستمر وكلٌّ منها مقسَّم إلى $m$ نقطة شبكية، فإن جدول الحالات يحتوي على $m^d$ مُدخلة. عند $d = 5$ و$m = 100$ يعني ذلك 10 مليارات مُدخلة — ممكن بالكاد على العتاد الحديث. أما عند $d = 20$ فحجم الجدول يفوق عدد ذرات الكون المرصود.

سمّى بيلمان هذه الظاهرة لعنة الأبعاد: النمو الأسّي لفضاء الحالات كلما زاد عدد المتغيرات. ليس هذا عيباً في الخوارزمية، بل هو خاصية أصيلة في المسائل عالية الأبعاد.

لعنة الأبعاد تفسّر لماذا تعمل البرمجة الديناميكية الجدولية بكفاءة على مسائل ذات فضاء حالات صغير ومنفصل (كأقصر المسارات أو المخزون بمنتجات قليلة)، لكنها تعجز عن التعامل مباشرة مع مدخلات حسّية خام كالصور أو اللغة. التعلم المعزز العميق يتجاوز هذه العقبة بتقريب دالة القيمة بشبكة عصبية بدلاً من تخزينها في جدول — لكن معادلة بيلمان في الصميم تبقى هي ذاتها.

كتاب 1957 لم يكن أطروحة نظرية مجرّدة، بل قدّم حلولاً فعلية لمسائل واقعية صِيغت جميعها كعمليات قرار متعددة المراحل:

• توزيع الموارد: كيف تُوزّع ميزانية على $N$ نشاط لتعظيم العائد الكلّي. معادلة بيلمان لهذه المسألة بأبسط صورها: $f_N(x) = \max_{0 \le y \le x}[g_N(y) + f_{N-1}(x-y)]$.
• إدارة المخزون: السياسة المُثلى للطلب في مستودع يواجه طلباً غير مؤكد. أصبح هذا ركيزة أمثَلَة سلاسل التوريد الحديثة.
• مسائل عنق الزجاجة: تقليل أسوأ تأخير عبر مراحل الإنتاج — وهو شكل تصغير-أقصى (minimax) من مسألة التعظيم المعتادة.
• عمليات ماركوف لاتخاذ القرار: حين يكون الانتقال إلى الحالة التالية عشوائياً ويتوقّف فقط على الحالة والفعل الحاليين دون التاريخ السابق. هذا الفصل تحديداً أصبح الأصل المباشر للتعلم المعزز الحديث.
• حساب التغيرات: بيّن بيلمان أن مسائل الأمثَلَة المستمرة (إيجاد مسار أمثل لا مجرد سلسلة قرارات مُثلى) يمكن صياغتها كمعادلات دالّية، وبذلك ربط بين الفيزياء الكلاسيكية والأمثَلَة المنفصلة.

كتاب بيلمان عام 1957 لم يقدّم مجرّد تقنية، بل أرسى أسلوب تفكير: فكِّك، احفظ، أعِد الاستخدام. كلما سمعت عبارة «حُلّ المسألة الجزئية مرة واحدة» أو «الاستقراء العكسي» أو «معادلة بيلمان»، فأنت تسمع صدى هذه الفكرة التأسيسية الواحدة.