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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في الرياضيات وعلم الحاسوب، البرمجة الديناميكية (بالإنكليزية: Dynamic programming) هي طريقة لحل مسائل معقدة عن طريق تقسيمهن لمسائل فرعية أبسط.

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

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

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

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

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

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

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

نظرة عامة[عدل]

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

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

البرمجة الديناميكية في الامثل الرياضي[عدل]

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

انظر أيضا[عدل]

Midori Extension.svg
هذه بذرة مقالة بحاجة للتوسيع. شارك في تحريرها.