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

البرمجة الديناميكية (بالإنجليزية: Dynamic programming)‏ في الرياضيات وعلم الحاسوب، هي طريقة لحل مسائل معقدة وصعبة الحل عن طريق تقسيمها لمسائل فرعية أبسط وسهلة الحل. الفكرة وراء البرمجة الديناميكية بسيطة. بشكل عام، لحل مسألة ما، نحن بحاجة إلى حل أجزاء مختلفة من المسألة (مسائل فرعية)، ومن ثم جمع حلول المسائل الفرعية للحصول على حل شامل. في كثير من الأحيان، كثير من هذه المسائل الفرعية هي في الواقع متشابهة. نهج البرمجة الديناميكية هو البحث عن حل كل مسألة فرعية مرة واحدة فقط، وبالتالي تقليل عدد الحسابات: حالما يتم حساب حل مسألة فرعية ما، يتم حفظه، وفي المرة القادمة عند الحاجة للحل نفسه، يتم ببساطة استرجاعه. هذا النهج مفيد خصوصاً عندما يكون عدد المسائل الفرعية المتكررة ينمو بشكل أُسي كعلاقة بحجم المدخل. عندما تطبق هذه الطريقة فإنها تستغرق وقتاً أقل مما تستغرقه الطرق الأخرى التي ليس لها ميزة حل المسائل الثانوية المتداخلة (مثل بحث العمق أولا). لحل مسألة ما، وباستخدام البرمجة الديناميكية نحتاج لحل أجزاء مختلفة من المسألة (مسائل ثانوية) بعدها يتم الدمج بينهم للحصول على الحل للمسألة بشكل عام. في الكثير من الأحيان عند استخدام طريقة خوارزمية جشعة فإنه يكون هناك العديد من المسائل الثانوية التي تحل بشكل متكرر. البرمجة الديناميكية تهدف إلى حل كل مسألة ثانوية لمرة واحدة فقط مما يؤدي إلى تقليل عدد الحسابات. فإنه بمجرد حل مسألة ثانوية فإنه يتم تخزينها «أوتوماتيكية مذكرة» لذا في المرة القادمة عندما نحتاج لنفس الحل فإنه ببساطة يتم البحث عنه. هذا النهج مفيد خاصةً عندما يكون عدد المسائل المتكررة يزداد بشكل مفرط كدالة في حجم المدخلات. تستخدم خوارزميات البرمجة الديناميكية لتعظيم الإستفادة (مثلاً للحصول على أقصر طريق بين نقطتين أو أسرع طريقة لضرب مصفوفات). خوارزميات البرمجة الديناميكية ستدرس الحلول السابقة للمسائل الثانويه وتقوم بدمجها للحصول على أفضل حل للمسألة المراد حلها. يوجد هناك بدائل كثيرة لهذه الطريقة مثل خوارزمية جشعة والتي بها يتم الحصول على الخيار الأمثل الموضعي في كل فرع في الطريق. الخيار الأمثل الموضعي ممكن أن يكون حل سيئ للمسألة بالكامل.بالرغم ان greedy algorithm لا تضمن الحل الامثل فإنها في كثير من الأحيان تقدم حسابات أسرع. لحسن الحظ فإن بعض من greedy algorithm (minimum spanning trees) أثبت أنها تقدم الحل الأفضل. على سبيل المثال، إذا كنا نريد الوصول من النقطة a إلى النقطة b في ساعة الذروة فإن البرمجة الديناميكية سوف تبحث عن النقاط القريبة من النقطة وa ثم يتم استخدامها للحصول على أقرب طريق إلى النقطة b على الجانب الآخر فإنك سوف تبدأ بالقيادة ومن ثم يتم البحث عن الطريق الأسرع عند كل تقاطع. لك أن تتخيل أن هذه الطريقة قد لا تؤدي إلى أسرع وقت للوصول حيث إنه من الممكن أن تختار طريقاً ظناً بأنه الطريق الأسرع ثم تجد أنك وقعت في أزمة مرورية. 2- مثال: اقتصاد أمثل