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

Understanding Dynamic Programming

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

دراسة حالة: فيبوناتشي

إن تسلسل فيبوناتشي مثال كلاسيكي على إظهار البرمجة الدينامية، والهدف هو إيجاد رقم فيبوناتشي بكفاءة.

وباستخدام التكرار الساذج، فإن التعقيد الزمني أمر متفشي، فالبرمجة الدينامية تقلل من هذا إلى الزمن الخطي بتخزين القيم الحاسوبية السابقة.

For example, to compute Fibonacci(10):

Fibonacci(10) = Fibonacci(9) + Fibonacci(8)

ومن خلال تخزين فيبوناتشي (8) و Fibonacci(9)، تُقلل الحسابات إلى أدنى حد، مما يؤدي إلى زيادة كبيرة في الأداء.

Case Study: Knapsack Problem

وتشمل مشكلة الاختناق التي تبلغ صفر/1 اختيار الأصناف ذات الأوزان والقيم المعطّلة لتحقيق أقصى قدر من القيمة الإجمالية دون تجاوز الحد الأقصى للوزن.

وتحل البرمجة الدينامية هذا الأمر ببناء جدول يمثل فيه كل بند القيمة القصوى التي يمكن تحقيقها بمجموعة فرعية من البنود وقدرة وزن محددة.

وتشمل الحسابات تكرارها من خلال البنود وتحديث الجدول استنادا إلى ما إذا كان إدراج بند ما يحسن القيمة الإجمالية.

التنفيذ

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

  • تحديد المشاكل الفرعية المتداخلة
  • تحديد الحالات الأساسية صراحة
  • استخدام هياكل البيانات المناسبة
  • تحقيق الحد الأمثل للفضاء وتعقيد الوقت