ملخص

النقاط الرئيسية

• تفكّك البرمجة الديناميكية المسائل وتتجنّب الحساب المكرر بتخزين حلول المسائل الفرعية، مما يحسّن كفاءة الحساب تحسيناً كبيراً.
• من دون النظر إلى قيود الزمن، يمكن حل جميع مسائل البرمجة الديناميكية بالتتبّع الرجعي (البحث الشامل)، لكن شجرة التعاود تحتوي على عدد كبير من المسائل الفرعية المتداخلة، مما يؤدي إلى كفاءة منخفضة للغاية. وبإدخال قائمة الحفظ (memo)، يمكننا تخزين حلول جميع المسائل الفرعية المحسوبة، بما يضمن ألا تُحسب المسائل الفرعية المتداخلة إلا مرة واحدة.
• الحفظ (memoization) حل تعاودي من الأعلى إلى الأسفل، بينما البرمجة الديناميكية المقابلة حل تكراري من الأسفل إلى الأعلى، أشبه بـ"ملء جدول". وبما أن الحالة الحالية تعتمد على حالات محلية معيّنة فقط، يمكننا حذف بُعد واحد من جدول $dp$ لتقليل التعقيد المكاني.
• تفكيك المسائل إلى مسائل فرعية نهج خوارزمي عام، وله خصائص مختلفة في التقسيم والتغلب والبرمجة الديناميكية والتتبّع الرجعي.
• تتمتع مسائل البرمجة الديناميكية بثلاث خصائص رئيسية: المسائل الفرعية المتداخلة، والبنية الفرعية المثلى، وانعدام التأثيرات اللاحقة.
• إذا أمكن بناء الحل الأمثل للمسألة الأصلية من الحلول المثلى للمسائل الفرعية، فإن للمسألة بنية فرعية مثلى.
• يعني انعدام التأثيرات اللاحقة أنه بالنسبة إلى حالة معيّنة، يرتبط تطورها المستقبلي بهذه الحالة وحدها ولا علاقة له بجميع الحالات السابقة. وكثير من مسائل التحسين التوليفي لا تستوفي هذه الخاصية ولا يمكن حلها بكفاءة باستخدام البرمجة الديناميكية.

مسألة الحقيبة

• مسألة الحقيبة من أكثر مسائل البرمجة الديناميكية نموذجية، ولها صيغ مثل حقيبة 0-1، والحقيبة غير المحدودة، والحقيبة المتعددة.
• تعريف الحالة في حقيبة 0-1 هو أقصى قيمة يمكن تحقيقها باستخدام أول $i$ من العناصر بسعة حقيبة $c$. واستناداً إلى القرارين المتمثلين في عدم وضع العنصر في الحقيبة ووضعه فيها، يمكن تحديد البنية الفرعية المثلى وبناء معادلة انتقال الحالة. وفي تحسين المساحة، وبما أن كل حالة تعتمد على الحالة التي فوقها مباشرة والحالة الواقعة في أعلى اليسار، يجب اجتياز القائمة بترتيب عكسي لتجنّب الكتابة فوق الحالة العلوية اليسرى.
• لا يوجد في مسألة الحقيبة غير المحدودة حدّ لكمية الاختيار من كل نوع من العناصر، لذلك يختلف انتقال الحالة عند اختيار وضع عنصر عن مسألة حقيبة 0-1. وبما أن الحالة تعتمد على الحالة التي فوقها مباشرة والحالة التي على يسارها مباشرة، ينبغي أن يستخدم تحسين المساحة الاجتياز الأمامي.
• مسألة تغيير العملة صيغة من مسائل الحقيبة غير المحدودة. وقد تغيّر المطلوب فيها من "أقصى" قيمة إلى "أدنى" عدد من العملات، لذا يجب تغيير $\max()$ في معادلة انتقال الحالة إلى $\min()$. كما تغيّر المطلوب من "عدم تجاوز" سعة الحقيبة إلى "تسديد" مبلغ الهدف بدقة، لذا يُستخدم $amt + 1$ لتمثيل الحل غير الصالح "تعذّر تسديد مبلغ الهدف".
• مسألة تغيير العملة II تغيّر المطلوب من "أدنى عدد من العملات" إلى "عدد توليفات العملات"، لذا تتغير معادلة انتقال الحالة تبعاً لذلك من $\min()$ إلى عامل جمع.

مسألة مسافة التحرير

• تُستخدم مسافة التحرير (مسافة ليفنشتاين) لقياس التشابه بين سلسلتين نصيتين، وتُعرَّف بأنها أدنى عدد من خطوات التحرير للانتقال من سلسلة إلى أخرى، وتشمل عمليات التحرير الإدراج والحذف والاستبدال.
• تعريف الحالة في مسألة مسافة التحرير هو أدنى عدد من خطوات التحرير اللازمة لتحويل أول $i$ من محارف $s$ إلى أول $j$ من محارف $t$. وعندما $s[i-1] \ne t[j-1]$، تكون هناك ثلاثة قرارات: الإدراج والحذف والاستبدال، ولكل قرار مسألة فرعية متبقية مقابلة. ومن ذلك يمكن تحديد البنية الفرعية المثلى وبناء معادلة انتقال الحالة. وعندما $s[i-1] = t[j-1]$، لا حاجة إلى تحرير المحرف الحالي.
• في مسافة التحرير، تعتمد الحالة على الحالة التي فوقها مباشرة والحالة التي على يسارها مباشرة والحالة الواقعة في أعلى اليسار، لذا بعد تحسين المساحة لا يمكن لأي من الاجتياز الأمامي أو العكسي إجراء انتقالات الحالة بشكل صحيح. ولهذا السبب نستخدم متغيراً لتخزين الحالة العلوية اليسرى مؤقتاً، فنحوّل الوضع إلى ما يكافئ مسألة الحقيبة غير المحدودة، مما يتيح الاجتياز الأمامي بعد تحسين المساحة.