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

في الرياضيات وعلم الحاسوب، البرمجة الديناميكية (Dynamic programming)‏ هي طريقة لحل مسائل معقدة عن طريق تقسيمها لمسائل فرعية أبسط.^[1][2][3]

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

عندما تطبق هذه الطريقة فإنها تستغرق وقت أقل مما تستغرقه الطرق الأخرى التي ليس لها ميزة حل المسائل الثانوية المتداخلة( مثل بحث العمق أولا).

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

تستخدم خوارزميات البرمجة الديناميكية لتعظيم الاستفادة ( مثلا للحصول علي أقصر طريق بين نقطتين أو أسرع طريقة لضرب مصفوفات). خوارزميات البرمجة الديناميكية ستدرس الحلول السابقة للمسائل الثانويه وتقوم بدمجها للحصول على أفضل حل للمسألة المراد حلها.

يوجد هناك بدائل كثيرة لهذه الطريقة مثل خوارزمية جشعة والتي بها يتم الحصول على الخيار الأمثل الموضعي في كل فرع في الطريق. الخيار الأمثل الموضعي ممكن أن يكون حل سيئ للمسألة بالكامل. بالرغم ان greedy algorithm لا تضمن الحل الامثل فإنها في كثير من الأحيان تقدم حسابات أسرع. لحسن الحظ فان بعض من greedy algorithm (minimum spanning trees )اثبت انها تقدم الحل الأفضل.

على سبيل المثال، إذا كنا نريد الوصول من النقطة a إلى النقطة b في ساعة الذروة فإن البرمجة الديناميكية سوف تبحث عن النقاط القريبة من النقطة و a ثم يتم استخدامها للحصول على أقرب طريق إلى النقطة b على الجانب الآخر فإنك سوف تبدأ بالسواقة ومن ثم يتم البحث عن الطريق الأسرع عند كل تقاطع. كل ان تتخيل ان في هذه الطريقة قد لا تؤدي الي اسرع وقت للوصول حيث انه ممكن ان تختار طريق ظنا بأنه الطريق الاسرع ثم تجد أنك وقعت في أزمة مرورية.

2- مثال: اقتصاد امثل

نظرة عامة

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

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

البرمجة الديناميكية في الأمثل الرياضي

في مصطلح الأمثل الرياضي البرمجة الديناميكية تشير ببساطة إلى تفكيك القرار إلى سلسلة من خطوات القرار على مدار الوقت. يتم فعل ذلك عن طريق القيان بتعريف قيم الدوال ب ف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 في USSR.

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

البرمجة الديناميكية في برمجة الحاسوب

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

يقصد بالبناء الامثل ان الحل للمسالة الامثل المعطا يمكن الحصول عليها عن طريق دمج الحلول المثلى للمسائل الثانوية. لذلك فان أول خطوة لاعطاء حل للبرمجة الديناميكية هو التاكد من وجود مثل ذلك البناء الامثل لهذه المسالة. مثل هذا البناء الامثل يتم وصفه عادة عن طريق التكرار. عن طريق المثال :لرسم معين ج(ف، ي) فان أقصر طريق ب من النقطة ف لنقطة ك له بناء امثل إذا: يمكن ان نختار نقطة في منتصف الطريق بين النقطتبن "و " حيث انه إذا كان الطريق ب هو الطريق الامثل فان هذا الطريق يمكن ان ينقسم الي طريقين ب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 أي عند الوفاة.

مراجع

مقالات ذات صلة

• خوارزمية فرق تسد
• خوارزمية جشعة

موسوعات ذات صلة :

• موسوعة خوارزميات
• موسوعة رياضيات
• موسوعة علم الحاسوب