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