البرمجة الديناميكية: ما هي وكيف تعمل ومصادر التعلم

البرمجة الديناميكية هي مفهوم طوره ريتشارد بيلمان ، عالم رياضيات ، وخبير اقتصادي.

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

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

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

ما هي البرمجة الديناميكية؟

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

كيف تعمل البرمجة الديناميكية؟

يتضمن حل مشكلة باستخدام البرمجة الديناميكية الخطوات التالية:

1. تحديد المشاكل الفرعية : تنقسم المشكلة الكبيرة إلى مشاكل فرعية صغيرة.
2. حل المشكلات الفرعية : يتضمن ذلك حل المشكلة الفرعية المحددة ، والتي يمكن إجراؤها باستخدام العودية أو التكرار.
3. تخزين الحلول : يتم تخزين حلول المشكلات الفرعية بحيث يمكن إعادة استخدامها.
4. بناء الحل للمشكلة الأصلية : حل المشكلة الكبيرة مبني من المشاكل الفرعية التي تم حسابها بالفعل.

لرؤية هذا في الواقع ، نحسب رقم فيبوناتشي السادس ، F (6) ، باستخدام هذه العملية.

أولاً ، حدد المشاكل الفرعية التي تحتاج إلى حل.

F (n) = F (n-1) + F (n-2) لـ n> 1

لذلك: F (6) = F (5) + F (4)

و (5) = و (4) + ث (3)

و (4) = و (3) + و (2)

و (3) = و (2) + و (1)

و (2) = و (1) + و (0)

و (1) = 1

و (0) = 0

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

و (0) = 0

و (1) = 1

و (2) = و (1) + و (0) = 1 + 0 = 1

و (3) = و (2) + و (1) = 1 + 1 = 2

و (4) = و (3) + و (2) = 2 + 1 = 3

و (5) = و (4) + و (3) = 3 + 2 = 5

و (6) = و (5) + و (4) = 5 + 3 = 8

أثناء قيامنا بحل كل مشكلة فرعية ، نقوم بتخزين الحلول في مصفوفة أو جدول بحيث يمكن إعادة استخدامها في حل المشكلات الفرعية الأكبر مثل:

بمجرد حل جميع المشكلات الفرعية ، نستخدم الحلول لإنشاء حل للمشكلة الأصلية.

في هذه الحالة ، حل المشكلة الأصلية هو رقم فيبوناتشي السادس ، والذي تم العثور عليه من خلال جمع نتائج F (5) و F (4) ، المشاكل الفرعية التي تم تحديدها من أكبر مشكلة. النتيجة تعطينا 8.

أين ولماذا تستخدم البرمجة الديناميكية؟

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

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

في الاقتصاد ، يتم استخدامه لحل مشاكل التحسين في التمويل والإنتاج وتخصيص الموارد. في الرياضيات ، تُستخدم البرمجة الديناميكية في نظرية الألعاب والإحصاءات والاحتمالات ، حيث تُستخدم لحل مشكلات التحسين.

في الهندسة ، يتم استخدامه لحل المشكلات في تخصيص الموارد والجدولة والتصنيع والاتصال وأنظمة التحكم.

هناك العديد من المزايا لاستخدام البرمجة الديناميكية لحل مشاكل التحسين:

1. الكفاءة : يمكن أن تكون البرمجة الديناميكية أكثر كفاءة من خوارزميات التحسين الأخرى لأنها تتجنب إعادة حساب المشكلات المماثلة عدة مرات.
2. حل المشكلات الكبيرة : البرمجة الديناميكية مثالية لمشاكل التحسين الكبيرة التي يصعب حلها باستخدام طرق أخرى. هذا لأنه يقسم المشكلة إلى مشاكل أصغر مما يقلل من تعقيدها.
3. الحلول المثلى : يمكن لخوارزميات البرمجة الديناميكية إيجاد الحل الأمثل لمشكلة ما إذا تم تحديد المشكلات الفرعية والأهداف بشكل صحيح.
4. البساطة: خوارزميات البرمجة الديناميكية سهلة التنفيذ والفهم ، خاصة إذا كان من الممكن تحديد المشكلة بترتيب معين.
5. القابلية للتوسعة: يمكن توسيع خوارزميات البرمجة الديناميكية بسهولة لحل المشكلات الأكثر تعقيدًا عن طريق إضافة مشاكل فرعية إضافية وتعديل أهداف المشكلة.

عندما يتعلق الأمر بحل مشاكل التحسين ، فإن البرمجة الديناميكية هي أداة مفيدة للغاية لضمان الكفاءة في الحلول.

الأساليب المستخدمة في البرمجة الديناميكية

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

نهج من أعلى إلى أسفل

يُعرف هذا النهج أيضًا باسم التحفيظ. Memoization هي تقنية تحسين تستخدم بشكل أساسي لجعل برامج الكمبيوتر أسرع من خلال تخزين نتائج استدعاءات الوظائف في ذاكرة التخزين المؤقت وإرجاع النتائج المخزنة مؤقتًا في المرة التالية التي تكون فيها مطلوبة بدلاً من حسابها مرة أخرى.

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

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

النهج التصاعدي

النهج التصاعدي ، المعروف أيضًا باسم الجدولة ، يلغي العودية ، ويستبدلها بالتكرار ، وبالتالي تجنب أخطاء تجاوز المكدس.

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

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

النتائج المخزنة تحل مشاكل أكبر تعتمد على المشاكل الفرعية. ثم يتم العثور على نتيجة المشكلة الأصلية عن طريق حل أكبر مشكلة فرعية باستخدام القيم المحسوبة مسبقًا.

تتميز هذه الطريقة بكونها فعالة في الذاكرة والوقت من خلال التخلص من العودية.

أمثلة على المشكلات التي يمكن حلها عن طريق البرمجة الديناميكية

فيما يلي بعض مشكلات البرمجة التي يمكن حلها باستخدام البرمجة الديناميكية:

# 1. مشكلة حقيبة الظهر

الحقيبة هي حقيبة مصنوعة من القماش أو النايلون أو الجلد تُربط عادةً بالظهر ويستخدمها الجنود والمتنزهون لحمل الإمدادات.

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

فيما يلي مثال على مشكلة حقيبة الظهر:

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

اختر مجموعة فرعية من العناصر لإحضارها بحيث يتم تكبير القيمة الإجمالية للعناصر بينما يكون الوزن الإجمالي أقل من أو يساوي سعة الحقيبة ، وهي 15 كجم.

تتضمن التطبيقات الواقعية لمشكلة الحقيبة على الظهر اختيار الأوراق المالية لإضافتها إلى المحفظة لتقليل المخاطر وزيادة الأرباح إلى أقصى حد وإيجاد الطرق الأقل إهدارًا لخفض المواد الخام.

# 2. مشكلة الجدولة

مشكلة الجدولة هي مشكلة تحسين حيث يكون الهدف هو تعيين المهام على النحو الأمثل لمجموعة من الموارد. قد تكون الموارد آلات أو موظفين أو موارد أخرى تستخدم لإكمال المهام.

فيما يلي مثال لمشكلة الجدولة:

تخيل أنك مدير مشروع مسؤول عن جدولة مجموعة من المهام التي يجب إكمالها بواسطة فريق من الموظفين. لكل مهمة وقت بدء ووقت انتهاء وقائمة بالموظفين المؤهلين لإكمالها.

فيما يلي جدول يصف المهام وخصائصها:

قم بتعيين كل مهمة للموظف لتقليل وقت الانتهاء الإجمالي.

يمكن مواجهة مشكلة الجدولة في الصناعة التحويلية عند محاولة تحسين تخصيص الموارد مثل الآلات والمواد والأدوات والعمالة.

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

# 3. مشكلة بائع متجول

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

توفر مشكلة البائع المتجول قائمة بالمدن والمسافات بين كل زوج من المدن. أنت مطالب بالعثور على أقصر طريق ممكن يزور كل مدينة مرة واحدة بالضبط ويعود إلى المدينة الأصلية.

فيما يلي مثال على مشكلة بائع متجول:

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

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

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

ضع في اعتبارك الموارد التالية لتوضيح معرفتك بالبرمجة الديناميكية.

موارد

البرمجة الديناميكية لريتشارد بيلمان

البرمجة الديناميكية كتاب لريتشارد بيلمان الذي ابتكر البرمجة الديناميكية وطورها في مراحلها الأولى.

معاينة	المنتج	تقييم	سعر
	البرمجة الديناميكية (كتب دوفر في علوم الكمبيوتر)	لا يوجد تقييم	17.29 دولارًا أمريكيًا	شراء على أمازون

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

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

أفضل ما في الكتاب هو أن بيلمان يقدم أمثلة على العديد من المشكلات المعقدة في مجالات مثل اللوجستيات ونظرية الجدولة ونظرية الاتصال والاقتصاد الرياضي وعمليات التحكم ويوضح كيف يمكن للبرمجة الديناميكية حل المشكلات.

الكتاب متاح في إصدارات Kindle و Hardcover و paperback.

دورة ماجستير خوارزميات البرمجة الديناميكية

يقدم Udemy هذه الدورة التدريبية الرئيسية لخوارزميات البرمجة الديناميكية بواسطة Apaar Kamal ، مهندس برمجيات في Google ، و Prateek Narang ، الذي عمل أيضًا مع Google.

تم تحسين الدورة لمساعدة المتعلمين على التفوق في مسابقة البرمجة التي تتميز بالكثير من المشكلات التي تتطلب البرمجة الديناميكية.

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

الدورة ، التي تزيد عن 40 ساعة ، تغطي البرمجة الديناميكية بعمق. تقدم الدورة التدريبية أولاً تنشيطًا لمفاهيم مثل التكرار والتراجع.

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

أساسيات البرمجة التنافسية ، الخوارزميات الرئيسية

يقدم Udemy دورة أساسيات البرمجة التنافسية من قبل Prateek Narang و Amal Kamaar والتي تغطي البرمجة الديناميكية والرياضيات ونظرية الأرقام وهياكل البيانات المتقدمة والخوارزميات بطريقة مفيدة وذات صلة بالمبرمجين التنافسيين.

تقدم الدورة التدريبية تجديدًا على هياكل البيانات والخوارزميات قبل الغوص في خوارزميات وتقنيات أكثر تعقيدًا والتي تكون مفيدة في البرمجة التنافسية.

تغطي الدورة البرمجة الديناميكية ، والرياضيات ، ونظرية الألعاب ، ومطابقة الأنماط ، والقناع النقطي ، وعدد لا يحصى من الخوارزميات المتقدمة المستخدمة والمختبرة في مسابقات البرمجة.

تنقسم دورة Udemy إلى 10 وحدات و 42 قسمًا وتوفر الكثير من أسئلة التدريب بعد كل قسم. تعد هذه الدورة التدريبية الأكثر مبيعًا أمرًا ضروريًا لأي شخص مهتم بالبرمجة التنافسية.

الكلمات الأخيرة

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

بعد ذلك ، يمكنك التحقق من لغات البرمجة لاستخدامها في علم البيانات.