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

في مصطلح الأمثل الرياضي البرمجة الديناميكية تشير ببساطة إلى تفكيك القرار إلى سلسلة من خطوات القرار على مدار الوقت. يتم فعل ذلك عن طريق القيام بتعريف قيم الدوال بف1, ف2........ف ن بمتغير x الذي يعبر عن حالة النظام في فترات زمنية a من 1 الي n. تعريف (f n (x بأنها القيمة التى يتم الحصول عليها من الحلة ص عند آخر وقت n.

قيم فا في أوقات أبكر في ن-1, ن- 2,....... 2, 1 يمكن الحصول عليها عن طريق الحساب للخلف باستخدام علاقات متكررة مسماه بمعادلة Bellman لكل أ=2,.... ن ف أ-1 عند كل قيمه ل ستحسب من ف أ عن طريق الحصول على أكبر قيمة لدالة بسيطه (غالباً عن طريق الجمع) للربح من القرار عند وقتا-1 ودالة ف أ عند الحلة الجديدة النظام إذا تم اتخاذ القرار. حيث أن قيمة ف أ تم حسابها للحالة المطلوبة فان العملية السابقة ينتج عنها قيمة ف أ-1 لهذه الحالات. اخيراً فان قيمة ف1 للحالة الابتدائية هي قيمة الحل الأمثل للمسألة. القيم المثلى للمتغيرات الخاصة بالقرار ممكن إيجادها عن طريق الرجوع إلى الحسابات التي تمت بالفعل.

تستخدم البرمجة الديناميكية بشكل واسع في المعلوماتية الحيوية في كثير من المهام مثل تسلسل المحاذاة ووطي البروتين وتوقع بناء RNA وروابط بروتين ال DNA. اولا فان خوارزميات البرمجة الديناميكية استخدمت بشكل منفصل في روابط بروتين الـ DNA في عام 1970 عن طريق CHarlesDelisis في الولايات المتحدة الأمريكية وGeorgii Gurskii و Alexander Zasedetelv في الاتحاد السوفييتي السابق.

حاليا، أصبحت هذه الخوارزميات معروفة في المعلوماتية الحيوية وعلم الأحياء الحسابي خاصة في الدراسات المختصة بالمواقع جسيم نووي وعامل النسخ ملزمة.

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

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

المسائل الثانوية المتداخلة مقصود بها ان المساحة المسموحة للمسائل الثانوية يجب أن تكون صغيرة لذا فإن أي خوارزميات متكررة لحل هذه المسألة يجب أن تحل هذه المسائل الثانوية بدلا من إيجاد مسائل ثانوية جديدة. علي طريق المثال: إعتبر الصيغة المتكررة لإنشاء متسلسلات Fibonacci ف أ = ف أ-1 + ف أ-2 بحالة أساسية ف1=ف2=1 وبالتالي فإن ف34= ف24+ف14 و ف24= ف14+ف04 الآن فإن ف14 تم حلها باستخدام شجرة ثانوية من كلا ف 34 وف 24 بالرغم من أن العدد الكلي للمسائل الثانوية صغير بالفعل (فقط 43) فإننا يمكننا إنهاء حل نفس المسائل مرارا وتكرارا إذا تمكنا من الوصول إلى حل متكرر ساذج مثل ذلك، لأن البرمجة الديناميكية أخذت ذلك في الإعتبار هذه الحقيقة تقوم بحل المسائل الثانوية لمرة واحدة. وذلك ممكن أن يتحقق بطريقتين: طريقه من الأعلى إلى أسفل:

هي عبارة عن إسقاط مباشر لأي صيغة رجعية لأي مسألة. إذا كان الحل لأي مسألة يمكن أن يتكون بشكل رجعي باستخدام الحل لمسائل الثانوية له فإنه يمكن تسجيل أو تخزين الحل لهذه المسائل الثانوية في جدول. لذا عند حل أي مسائل ثانوية جديدة نبحث اولاً في الجدول إذا كانت تم حلها بالفعل. إذا كان الحل مسجل فإننا يمكننا استخدامه مباشرةً غير ذلك فإنه يتم حل المسألة وإضافاتها في الجدول. طريقه من أسفل إلى أعلى: بمجرد تكوين الحل للمسألة بطريقة رجعية في صيغة مسائلها الثانويه نقوم بإعادة تكوين المسألة من أسفل إلى أعلى: عن طريق محاولة إيجاد حل للمسائل الثانوية ومن ثم إيجاد الحل للمسائل الأكبر. هذه أيضا يتم تكوينها في صيغة جدولية عن طريق تكوين الحل للمسائل الأكبر فالأكبر باستخدام الحلول للمسائل الأصغر. عن طريق المثال إذا تم الوصول لحل ف 14 و ف04 يمكن إيجاد حل ل ف 24 بعض لغات البرمجة ممكن أن تقوم بتخزين النتائج بطريقة أوتوماتيكية كدالة ممكن مناداتها باستخدام عدد من الأوامر وذلك لكي يتم تسريع تقييم المناداة بالاسم (هذه الطريقة التي تسمي المناداة حسب الحاجة) بعض اللغات تجعل من الممكن تنقلنا. بعض اللغات لديها آلية التحفيظ في بني مثل جداول Prolog and J والتي تدعم التخزين باستخدام M adverb 2-مثال: اقتصاد أمثل

كتطبيق مسألة الأمثل رياضيا التي تستخدم غالبا في تعليم البرمجة الديناميكية متعلقة بمستهلك يعيش على فترات زمنية t=1,2,3,.....T والمطلوب أن تقرر مقدار الذي يجب أن يستهلكه المستهلك وكم يجب أن يوفره. نفرض أن " Ct" تمثل الاستهلاك عند زمن "t" مع افتراض أن الاستهلاك يؤدي إلى فائدة U(t)=ln Ct طالما المستهلك على قيد الحياة. مع افتراض أن المستهلك غير صبور فهو يريد أن يعد فوائد المستقبل بمعامل "b" لكل فترة حيث ان 1 <b <0↵افترض Kt رأس مال عند فترة زمنية t . افترض أن الراس مال الابتدائي <k0مع افتراض أن هذا الرأس مال مع الاستهلاك يمكن أن يحددوا الرأس مال في الفترة الزمنية المقبلة

حيث A هو ثابت موجب و1 <a< 0 نفتر ان الرأس مال لايمكن ان يكون سالب. لذا فإن مسألة اتخاذ قرار للمستهلك يمكن ان تكتب:

بهذه الطريقة فإن المسألة تبدو معقدة حيث انه يجب ايجاد الحلول لكل المتغيرات المتاحة C0,C1,C2,………Ct

استخدام نهج البرمجة الديناميكية حيث يتم تفكيك المسألة إلى سلسلة قرارات أصغر. لفعل ذلك نقوم بتعريف قيمة دالة Vt(K) لكل t=0,1,2,….T,T+1 والتي تمثل قيمة ما نمتلك من رأس مال عند كل فترة زمنية t . لاحظ أنه VT+1(K)=0 حيث انه بالافتراض لا يوجد فائدة من امتلاك رأس مال بعد الموت. قيمة الرأس مال عند أي فترة زمنية سابقة يمكن أن تحسب عن طريق الحث للوراء باستخدام معادلة Bellman. لهذه المسألة تكون معادلة Bellman كالآتي

هذه المسألة أسهل بكثير من المسائل المكتوبة سابقا لأنها تحتوي فقط على متغيرين للقرار فقط Ct, Kt+1 وبالتالي انه بدل ان يقوم المستهلك بوضع خطة لحياته بأكملها عند الولادة هو يأخذ كل خطوة على حده. لذا عند كل فترة زمنية t يكون الرأس مال معطي ومعروف للمستهلك فكل ما عليه هو أن يحسب استهلاكه Ct وبحسب ما يدخره Kt+1

لحل المسألة بالضبط فإننا نرجع للخلف. كتبسيط مستوى الرأس مال عند هذه النقط يعرف ب K قيمة VT+1(K) معروفة لذا باستخدام معادلة Bellman يمكن حساب VT(K) ونستمر كذلك حتى يتم حساب V0(K) والتي تمثل القيمة للقرار الابتدائي للمسألة على مدار حياته

بالعمل للخلف واضح أن قيمة الدالة لفترة زمنية t=T-j

حيث كل VT-j ثابت لذا الكمية المثلى للاستهلاك عند فترة زمنية t=T-j

ويمكن أن تبسط إلى^[مبهم]

كما هو واضح فإنه يتم استهلاك كمية أكبر من الصحة كلما يكبر في العمر ويقوم باستهلاك كل الصحة عند وقت T أي عند الوفاة.