برمجة ديناميكية
المحتويات
على سبيل التعريف، البرمجة الديناميكية ( بالإنجليزية: Dynamic programming) في الرياضيات وعلم الحاسوب، هي: طريقة لحل المسائل المعقّدة الصعبة عن طريق تقسيمها لمسائل فرعية أبسط وأسهل حلًا. ونتناول فيما يلي مزيدًا من التفاصيل.
إضافةً إلى ذلك، عند استخدام هذه الطريقة سيتوفر الكثير من الوقت مقارنة بالطرق الأخرى التي لا تتمتع بقدرة حل المسائل الثانوية المتداخلة مثل: (البحث بعمق أولًا).
وفي هذا الصدد، يوجد هناك بدائلُ كثيرةٌ لهذه الطريقة مثل الخوارزمية الجشعة، والتي بها يحصل على الخيار الأمثل الموضعي في كل فرع في الطريق. الخيار الأمثل الموضعي من الممكن أن يكون حلا سَيئا للمسألة بالكامل، مع أن الخوارزمية الجشعة لا تضمن الحل الأمثل، فإنها أحيانًا تقدم حسابات أسرع. ولحسن الحظ، بعضٌ من الخوارزميات الجشعة (الشجرة الممتدة ذات الوزن الأدنى) أثبتت أنها تقدم الحل الأفضل.
وفي هذا الصدد، لحل مسألة ما، وباستخدام البرمجة الديناميكية، نحتاج لحل أجزاء مختلفة من المسألة (المسائل الثانويّة)، وبعدها يتم الدمج بينهم للحصول على الحل للمسألة بشكل عام، وعند استخدام طريقة الخوارزمية الجشعة فإنه يكون هناك الكثير من المسائل الثانويّة التي تُحَل بشكل متكرر، ولكن البرمجة الديناميكية تهدف إلى حل كل مسألة ثانويّة لمرة واحدة فقط، مما يؤدي إلى تقليل عدد الحسابات، فإنه بمجرد حل مسألة ثانوية تُخزن مباشرةً في «المذكرة التلقائية»، لذا في المرة القادمة عندما نحتاج لنفس الحل، فإنه ببساطة يُبحث عنه، وهذا النهج مفيد خاصةً عندما يكون عدد المسائل المتكررة يزداد بشكل مفرط كدالة في حجم المدخلات.
علاوةً على ذلك، عادةً ما تكون الفكرة وراء البرمجة الديناميكية بسيطة لحل مسألة ما، فنحتاج إلى حل أجزاءَ مختلفةٍ من المشكلة (المسائل الفرعية)، ومن ثم جمع حلول المسائل الفرعية للحصول على الحل الشامل. والكثير من تلك المسائل الفرعيّة تكون متشابهة. نهج البرمجة الديناميكية يتم من خلال البحث عن حل كل مسألة فرعيّة مرة واحدة فقط، مما يقلل من عدد العمليات الحسابية، وبمجرد حساب حل مسألة فرعيّة معينة، يتم حفظ الحل، ويكون الحل نفسه في المرة القادمة هو نفس عدد المسائل الفرعية المتكررة، وهذا الأسلوب مفيد بشكل خاص عندما ينمو حجمُ المدخلات إلى حدّ كبير (النمو الأسي).
في هذا الإطار، تستعمل خوارزميّات البرمجة الديناميكية لتعظيم الاستفادة (مثلًا للحصول على أقصر طريق بين نقطتين أو أسرع طريقة لضرب مصفوفات). خوارزميات البرمجة الديناميكية ستدْرُس الحلول السابقة للمسائل الثانويّة وتقوم بدمجها للحصول على أفضل حل للمسألة المرادِ حلها.
وفي السياق ذاته، إذا كنا نريد الوصول من النقطة (a) إلى النقطة (b) في ساعة الذروة، فإن البرمجة الديناميكية ستبحث عن النقاط القريبة من النقطة (a) ثم تُستعمل للحصول على أقرب طريق إلى النقطة (b)، وعلى الجانب الآخر، ستبدأ بالقيادة ومن ثم سيتم البحث عن الطريق الأسرع عند كل تقاطع. ولك أن تتخيل أن هذه الطريقة قد لا تؤدي إلى أسرع وقت للوصول، حيث إنه من الممكن أن تختار طريقًا ظنًا بأنه الطريق الأسرع، ثم تجد أنك وقعت في أزمة مرورية.
البرمجة الديناميكية في برمجة الحاسوب
وفي السياق ذاته، هناك مفتاحان رئيسان يجب أن يتواجدا في المشكلة لكي يمكن أن تطبق عليها البرمجة الديناميكية: البناء الأمثل والمسائل الثانوية المتداخلة. إذا كانت المسألة ممكن أن تنحل عن طريق دمج عدد من الحلول المثلي لمشاكل ثانوية غير متداخلة فان هذه الطريقة تسمي فرق تسد بدلا من ذلك لهذا السبب فإن تصنيف الدمج والتصنيف السريع لا يمكن أن تصنف ضمن مسائل البرمجة الديناميكية.
ومن جهة أخرى، هي عبارة عن إسقاط مباشر لأي صيغة رجعية لأي مسألة. إذا كان الحل لأي مسألة يمكن أن يتكون بشكل رجعي باستخدام الحل لمسائل الثانوية له فإنه يمكن تسجيل أو تخزين الحل لهذه المسائل الثانوية في جدول. لذا عند حل أي مسائل ثانوية جديدة نبحث اولاً في الجدول إذا كانت تم حلها بالفعل. إذا كان الحل مسجل فإننا يمكننا استخدامه مباشرةً غير ذلك فإنه يتم حل المسألة وإضافاتها في الجدول. طريقه من أسفل إلى أعلى:
من جانب آخر، بالرغم من أن العدد الكلي للمسائل الثانوية صغير بالفعل (فقط 43) فإننا يمكننا إنهاء حل نفس المسائل مرارا وتكرارا إذا تمكنا من الوصول إلى حل متكرر ساذج مثل ذلك، لأن البرمجة الديناميكية أخذت ذلك في الاعتبار هذه الحقيقة تقوم بحل المسائل الثانوية لمرة واحدة. وذلك ممكن أن يتحقق بطريقتين:
علاوةً على ذلك، يقصد بالبناء الأمثل أن الحل للمسألة الأمثل المعطى يمكن الحصول عليها عن طريق دمج الحلول المثلى للمسائل الثانوية. لذلك فإن أول خطوة لإعطاء حل للبرمجة الديناميكية هو التأكد من وجود مثل ذلك البناء الأمثل لهذه المسالة. مثل هذا البناء الامثل يتم وصفه عادة عن طريق التكرار. عن طريق المثال: لرسم معين ج (ف، ي)
2-مثال: اقتصاد أمثل
في هذا الإطار، بعض لغات البرمجة من الممكن أن تقوم بتخزين النتائج بطريقة أوتوماتيكية كدالة يمكن مناداتها باستخدام عدد من الأوامر وذلك لكي يتم تسريع تقييم المناداة بالاسم (هذه الطريقة التي تسمي المناداة حسب الحاجة) بعض اللغات تجعل من الممكن تنقلنا. بعض اللغات لديها آلية التحفيظ في بني مثل جداول Prolog and J والتي تدعم التخزين باستخدام M adverb
في هذا الإطار، ف أ = ف أ-1 + ف أ-2 بحالة أساسية ف1=ف2=1 وبالتالي فإن ف34= ف24+ف14 و ف24= ف14+ف04 الآن فإن ف14 تم حلها باستخدام شجرة ثانوية من كلا ف 34 وف 24
إضافةً إلى ذلك، فان أقصر طريق ب من النقطة فالنقطة كله بناء أمثل إذا: يمكن أن نختار نقطاً في منتصف الطريق بين النقطتين «و» حيث إنه إذا كان الطريق ب هو الطريق الأمثل فان هذا الطريق يمكن ان ينقسم طريقين ب 1 من النقطة» إلى النقطة» وطريق ب2 من النقطة» إلى النقطة «ك» بنفس الطريقة يكونوا كذلك أصغر طرق بين النقاط المقابلة (باستخدام ببساطة مبدأ قص ولصق المشروحة في مقدمة الخوارزميات). وهكذا فانه ممكن فانه بسهولة إيجاد الطريق الأقصر بطريقة متكررة وهذا نفس ما قام به خوارزميات بولمان–فورد و خوارزميات فولياد وارشال.
طريقه من الأعلى إلى أسفل:
كذلك، بمجرد تكوين الحل للمسألة بطريقة رجعية في صيغة مسائلها الثانوية نقوم بإعادة تكوين المسألة من أسفل إلى أعلى: عن طريق محاولة إيجاد حل للمسائل الثانوية ومن ثم إيجاد الحل للمسائل الأكبر. هذه كذلك يتم تكوينها في صيغة جدولية عن طريق تكوين الحل للمسائل الأكبر فالأكبر باستخدام الحلول للمسائل الأصغر. عن طريق المثال إذا تم الوصول لحل ف 14 و ف 04 يمكن إيجاد حل ل ف 24
علاوةً على ذلك، المسائل الثانوية المتداخلة مقصود بها ان المساحة المسموحة للمسائل الثانوية يجب أن تكون صغيرة لذا فإن أي خوارزميات متكررة لحل هذه المسألة يجب أن تحل هذه المسائل الثانوية بدلا من إيجاد مسائل ثانوية جديدة. علي طريق المثال: اعتبر الصيغة المتكررة لإنشاء متسلسلات Fibonacci
البرمجة الديناميكية في المعلوماتية الحيوية
وفي هذا السياق، اولا فان خوارزميات البرمجة الديناميكية استعملت بشكل منفصل في روابط بروتين حمض نووي ريبوزي منقوص الأكسجين في سنة 1970 عن طريق تشارلز ديليسيس في الولايات المتحدة الأمريكية
وفي السياق ذاته، و GeorgهGurskii و Alexander Zasedetelv في الاتحاد السوفييتي السابق.
كذلك، تستعمل البرمجة الديناميكية بشكل واسع في المعلوماتية الحيوية في كثير من المهام مثل تسلسل المحاذاة و وطي البروتين وتوقع بناء حمض نووي ريبوزي وروابط بروتين حمض نووي ريبوزي منقوص الأكسجين.
إضافةً إلى ذلك، في الوقت الحالي، أصبحت هذه الخوارزميات معروفة في المعلوماتية الحيوية وعلم الأحياء الحسابي خاصة في الدراسات المختصة بالمواقع جسيم نووي وعامل النسخ ملزمة.
ويمكن أن تبسط إلى
ومن جهة أخرى، كما هو واضح فإنه يتم استهلاك كمية أكبر من الصحة كلما يكبر في العمر ويقوم باستهلاك كل الصحة عند وقت T أي عند الوفاة.
- مراجع
- انظر كذلك
- خوارزمية فرق تسد
البرمجة الديناميكية في الأمثل الرياضي
وفي السياق ذاته، في مصطلح الأمثل الرياضي البرمجة الديناميكية تشير ببساطة إلى تفكيك القرار إلى سلسلة من خطوات القرار على مدار الوقت. يتم فعل ذلك عن طريق القيام بتعريف قيم الدوال بف1, ف2........ف ن بمتغير x الذي يعبر عن حالة النظام في فترات زمنية a من 1 الي n. تعريف (f n (x بأنها القيمة التي يتم الحصول عليها من الحلة ص عند آخر وقت n.
إضافةً إلى ذلك، قيم فا في أوقات أبكر في ن-1, ن- 2,....... 2, 1 يمكن الحصول عليها عن طريق الحساب للخلف باستخدام علاقات متكررة مسماه بمعادلة بيلمان لكل أ=2,.... ن ف أ-1 عند كل قيمه ل ستحسب من ف أ عن طريق الحصول على أكبر قيمة لدالة بسيطة (غالباً عن طريق الجمع) للربح من القرار عند وقتا-1 ودالة ف أ عند الحلة الجديدة النظام إذا تم اتخاذ القرار. حيث أن قيمة ف أ تم حسابها للحالة المطلوبة فان العملية السابقة ينتج عنها قيمة ف أ-1 لهذه الحالات. اخيراً فان قيمة ف 1 للحالة الابتدائية هي قيمة الحل الأمثل للمسألة. القيم المثلى للمتغيرات الخاصة بالقرار ممكن إيجادها عن طريق الرجوع إلى الحسابات التي تمت بالفعل.
نظرة عامة
وعلى صعيد آخر، البرمجة الديناميكية هي طريقة للحصول على الأمثل رياضيا برمجيا و حاسوبيا كذلك. في كلا السياقين تهدف إلى تبسيط المسائل المعقدة عن طريق تجزئتها إلى مسائل ثانوية أبسط في طريقة التكرار. في حين أن بعض المسائل المتعلقة باتخاذ قرار لا يمكن أن تحل بهذه الطريقة فإنه في كثير من الأحيان القرارات التي تمتد على مدار الوقت لكثير من النقاط لا تتفكك بشكل مستمر. بيلمان سمي ذلك في "Principle of optimality" بطريقة متشابهة فإنه في علم الكمبيوتر المسائل التي تحل للحصول على الحل الأمثل عن طريق تجزئة المسالة إلى مسائل أصغر وأسهل وبعدها يتم حل باقي المسائل بطريقة متكررة للوصول للحل الأمثل للمسألة يقال إن لها بناء أمثل.
من جهة ثانية، إذا كانت المسائل الثانوية ممكن أن تكون متداخلة بشكل متكرر داخل المسألة حيث يمكن أن تطبق البرمجة الديناميكية عليها فإنه يوجد علاقة بين قيم المسألة الكبيرة وبين قيم المسائل الصغيرة الثانوية. في أدب الأمثلية "optimization literature" تسمي هذه العلاقة بمعادلة بيلمان.
الاستهلاك والتوفير الأمثل
علاوةً على ذلك، بهذه الطريقة فإن المسألة تبدو معقدة حيث انه يجب ايجاد الحلول لكل المتغيرات المتاحة
في هذا الإطار، كتطبيق مسألة الأمثل رياضيا التي تستعمل غالبا في تعليم البرمجة الديناميكية متعلقة بمستهلك يعيش على فترات زمنية 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
ومن جهة أخرى، قيمة VT+1(K) معروفة لذا باستخدام معادلة Bellman يمكن حساب VT(K) ونستمر كذلك حتى يتم حساب V0(K) والتي تمثل القيمة للقرار الابتدائي للمسألة على مدار حياته
وفي السياق ذاته، حيث كل VT-j ثابت لذا الكمية المثلى للاستهلاك عند فترة زمنية t=T-j
علاوةً على ذلك، لحل المسألة بالضبط فإننا نرجع للخلف. كتبسيط مستوى الرأس مال عند هذه النقط يعرف ب K
بالعمل للخلف واضح أن قيمة الدالة لفترة زمنية t=T-j
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟