البرمجة الديناميكية هي مصطلح من المحتمل أن يتم طرحه الآن إذا كنت في الميدان لأي فترة زمنية. يتم طرح الموضوع بشكل متكرر في اجتماعات مراجعة التصميم وفي تفاعلات المهندسين اليومية ، وهو أيضًا نقطة محورية في المقابلات الفنية. استراتيجية فرق تسد هي طريقة مضمونة لتحقيق أي هدف. في برمجة الكمبيوتر ، هذه الفكرة نفسها صحيحة. العديد من الصعوبات لها أنواع فرعية يمكن عزلها ومعالجتها بشكل منفصل ، مما يسمح بالحل النهائي للمشكلة الأساسية. في هذه المقالة ، سنناقش خوارزمية البرمجة الديناميكية و Python.
ما هي البرمجة الديناميكية؟
البرمجة الديناميكية هي طريقة لحل المشكلات المعقدة عن طريق تقليلها أولاً إلى مشكلات أبسط ، ثم استخدام الحلول لتلك المشكلات الأبسط كوحدات بناء لحل المشكلة الأصلية.
نقوم بتقسيم المشكلة المطروحة إلى أجزاء يمكن التحكم فيها. في معظم الحالات ، يكون الفارق الحقيقي الوحيد بين مشكلة الوالدين ومشاكل طفلهما هو الحجم النسبي. وبالتالي ، يمكن تقسيم هذه المشكلات الصغيرة إلى المزيد من المشكلات الصغيرة ، وما إلى ذلك ، إلى أجل غير مسمى. تخيل أن مشكلة ما ومختلف مشكلاتها الفرعية تشكل شجرة. يتم التعامل مع مشاكل "الورقة" أولاً ، تليها المشكلات "الأصل" ، وهكذا حتى شجرة المشكلة. بينما نتعامل مع الصعوبات الأصغر ، نسجل التقدم الذي أحرزناه لاستخدامه لاحقًا. هذا يسمح لنا بتخطي هذا الجزء من المشكلة في المستقبل.
تشبه هذه الطريقة تقنية فرق تسد من حيث أنها تقسم المشكلة إلى مشاكل أصغر يمكن حلها بشكل مستقل ثم دمجها للحصول على الحل النهائي.
كيف تعمل البرمجة الديناميكية؟
تعتبر البرمجة الديناميكية فعالة لأنها تبسط القضايا الصعبة عن طريق تحليلها إلى أجزاء مكونة. الخطوة التالية هي تحديد أفضل الإجابات على هذه التحديات الناشئة. يمكن حفظ نتائج هذه الإجراءات بحيث يمكن استرجاع الحلول المقابلة من التخزين واستخدامها دون مزيد من الحسابات. أيضًا ، يمكن حفظ الحل لتجنب إعادة حساب المشكلات الفرعية التي تم حلها مسبقًا.
توجد طريقتان لإنجاز البرمجة الديناميكية:
# 1. نهج من أعلى إلى أسفل
في علوم الكمبيوتر ، يتم حل المشكلات عادةً عن طريق إنشاء الحلول بشكل متكرر ، أو باستخدام نتائج الخطوات السابقة لمعالجة المشكلة المطروحة. من الممكن حفظ أو الاحتفاظ بجدول الحلول للمشاكل الفرعية إذا كانت متشابهة. تعتمد الطريقة التنازلية على التعلم بالذاكرة عن ظهر قلب. Memoization هو نفسه إجراء العودية والتخزين المؤقت مرتين. تتضمن العودية إجراء استدعاء غير مباشر للوظيفة ، بينما يتضمن التخزين المؤقت تتبع النتائج الوسيطة.
من بين المزايا العديدة للنهج التنازلي:
- الطريقة التنازلية سهلة الفهم والتطبيق. لفهم ما يجب القيام به بشكل أفضل ، تقوم هذه الطريقة بتفكيك المشكلات إلى عناصرها المكونة. كل تطور جديد يجلب معه راحة من عقبة لم يكن من الممكن التغلب عليها في السابق. قد تكون بعض القطع قابلة للتطبيق على مشاكل أخرى.
- أنها تمكن من حل المشاكل الفرعية عند الطلب. ستسمح الطريقة من أعلى إلى أسفل بتحليل المشكلات إلى أجزاء يمكن التحكم فيها ، مع تخزين حلول تلك الأجزاء لاستخدامها لاحقًا. بعد ذلك ، يمكن للعملاء طلب المساعدة في إصلاح كل مكون.
- التصحيح مبسط أيضًا. يسهل تقسيم المشكلة إلى أجزاء أصغر متابعة الإجابة ورؤية الأخطاء المحتملة.
فيما يلي بعض عيوب استخدام نهج من أعلى إلى أسفل:
- تستفيد إستراتيجية أعلى لأسفل من طريقة العودية ، والتي تشغل مساحة أكبر من الذاكرة في مكدس الاستدعاءات مقارنة بالطرق الأخرى. يؤدي هذا في النهاية إلى انخفاض في الأداء. بالإضافة إلى ذلك ، يمكن أن يحدث تجاوز سعة المكدس إذا ذهب العودية بعيدًا جدًا إلى الماضي.
# 2. النهج التصاعدي
بعد التعبير عن حل المشكلة من حيث مشكلاتها الفرعية بطريقة تدور مرة أخرى حول نفسها ، يمكن للمستخدمين إعادة كتابة المشكلة باستخدام النهج التصاعدي ، حيث يقومون بحل المشكلات الفرعية الأصغر أولاً ثم تطبيق حلولهم على المشكلات الأكبر .
على عكس طريقة من أعلى إلى أسفل ، يتم التخلص من العودية عند استخدام طريقة من أسفل إلى أعلى. لذلك ، لا تضيف الوظائف العودية مقدار حمل غير ضروري أو تتسبب في تجاوز سعة المكدس. بالإضافة إلى ذلك ، فإنه يتيح ضغط البيانات. يتم تقليل التعقيد الزمني للتكرار من خلال التخلص من الحاجة إلى إعادة حساب نفس القيم.
بعض فوائد العمل من الألف إلى الياء هي كما يلي:
- يحدد أولاً كيف سيتم إنشاء مشكلة ضخمة من مشكلات فرعية أصغر قابلة لإعادة الاستخدام.
- من خلال التخلص من العودية ، فإنه يساعد على الاستفادة بشكل أفضل من الذاكرة المتاحة. يتم تقليل تعقيد التوقيت كأثر جانبي.
خصائص البرمجة الديناميكية
هناك نوعان من الخصائص المميزة للبرمجة الديناميكية:
# 1. تداخل المشاكل الفرعية
يُطلق على التعديلات التي تُجرى على مشكلة أساسية يمكن إدارتها اسم "مشكلات فرعية". تسلسل فيبوناتشي ، حيث يساوي كل رقم مجموع الرقمين السابقين (0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، ...). يمكنك تقسيم مهمة إيجاد القيمة التاسعة في تسلسل فيبوناتشي إلى أجزاء أكثر قابلية للإدارة. عندما تجد حلولًا من خلال معالجة نفس المشكلة الفرعية مرارًا وتكرارًا ، يصبح حل هذه المجموعات المتداخلة من الصعوبات صعبًا بشكل متزايد.
يمكن استخدام البرمجة الديناميكية لتقسيم وظائف البرمجة الكبيرة إلى أجزاء يمكن إدارتها بسبب التواجد العالمي للمشكلات الفرعية المتداخلة.
# 2. البنية التحتية لها الخاصية المثلى
تتجلى خاصية البنية التحتية المثلى عندما يكون من الممكن إنشاء حل مثالي من الحلول لجميع المشكلات الفرعية. لكي تعمل العودية ، يجب عليك تطبيق الإجابة التي تستمدها من كل تداخل على المشكلة بأكملها. يتم عرض خاصية البنية التحتية المثلى بالمشكلة بأكملها عندما ، كما في حالة تسلسل فيبوناتشي ، يكون لكل مشكلة فرعية حل يمكن تطبيقه على المشكلة الفرعية التالية في التسلسل لتحديد قيمتها.
استخدامات البرمجة الديناميكية في العالم الحقيقي
فيما يلي استخدامات البرمجة الديناميكية.
# 1. مشكلة حقيبة الظهر
تم استخدام البرمجة الديناميكية على نطاق واسع لحل مشكلة الحقيبة. هذه هي المشكلات التي نواجهها:
يمكن تخزين القيمة المثالية لكل قضية فرعية ، والتي يتم تحديدها من خلال عدد العناصر المعنية ومقدار المساحة المتبقية في الحقيبة ، في مصفوفة ثنائية الأبعاد ، مما يؤدي إلى سرعة حل هذه المشكلة. يمكننا تعظيم القيمة من خلال تضمين أو استبعاد العنصر الحالي في كل مرحلة. يمكن العثور على الإجابة في الزاوية اليمنى السفلية للمصفوفة.
يمكن استخدام مشكلة الحقيبة في مجموعة متنوعة من السياقات ، من حزم الأمتعة إلى اتخاذ قرارات الاستثمار إلى تخصيص الموارد.
# 2. كل زوج أقصر طريق
تعد مشكلة أقصر مسار في الرسم البياني الموزون استخدامًا نموذجيًا آخر للبرمجة الديناميكية. باستخدام تقنيات مثل Floyd-Warshall أو Bellman-Ford ، يمكننا العثور على أقصر طريق بين أي زوجين من العقد.
من أجل تتبع أقصر مسار بين أي عقدتين ، تستخدم هذه الخوارزميات مصفوفة ثلاثية الأبعاد. أيضًا ، من أجل تتبع مدى بُعدهم عن نقطة البداية ، يقارنون النتيجة بالمسافة بين نقطة البداية والعقدة الوسيطة في كل مرحلة. بعد كل شيء ، التكرارات كاملة ، سيكون الحل النهائي هو مصفوفة المسافة.
هناك العديد من الاستخدامات لحل مشكلة أقصر مسار لجميع الأزواج ، مثل تحليل الشبكة ، والتوجيه ، والملاحة ، وتحليل الشبكة الاجتماعية ، وما إلى ذلك.
# 3. نحت التماس
في مجال معالجة الصور ، يعد نحت التماس تطبيقًا مثيرًا للاهتمام للبرمجة الديناميكية. تتمثل المهمة الحالية في تقليل حجم الصورة دون تغيير أي من خصائصها الأساسية. يمكن استخدام المسارات منخفضة الطاقة في صورة ما ، والمعروفة باسم اللحامات ، لطرح أو إضافة وحدات بكسل لتحقيق هذا التأثير.
باستخدام البرمجة الديناميكية ، يمكننا حساب الطاقة التراكمية لكل بكسل في الصورة بناءً على التدرج اللوني والجيران ، ثم استخدام هذه المعلومات لتحديد اللحامات التي يجب إزالتها أو إضافتها. بعد ذلك ، من خلال العمل في طريقنا من أسفل الصورة ، قد نحدد موقع التماس بأقل قدر من الطاقة الكامنة. يمكن استخدام هذه الطريقة مرة أخرى حتى يتم تحقيق الحجم المطلوب.
بالإضافة إلى ذلك ، يمكن تغيير حجم الصور واقتصاصها وإعادة استهدافها والمزيد بمساعدة نحت التماس.
# 4. تعلم الآلة وعلم الجينوم
تعد تحديات التعلم الآلي وعلم الجينوم مثل محاذاة التسلسل ونماذج ماركوف المخفية وأشجار النشوء والتطور جميعها قابلة لقدرات حل المشكلات في البرمجة الديناميكية.
يُطلق على محاذاة سلاسل متعددة من الرموز (غالبًا الحمض النووي أو البروتينات) للكشف عن القواسم المشتركة محاذاة التسلسل. يمكن أن يلقي هذا الضوء على الروابط التطورية ، أو الوظائف في المجتمع ، أو الخصائص الهيكلية. يمكن العثور على المحاذاة المثلى من خلال البرمجة الديناميكية عن طريق تعيين الدرجات للمطابقات وعدم التطابق بين التسلسلات.
تُستخدم النماذج الاحتمالية المعروفة باسم نماذج ماركوف المخفية لوصف بيانات السلاسل الزمنية المشروطة بحالات غير معروفة. إنها مفيدة لنمذجة الظواهر الصعبة مثل التعرف على الكلام ، ومعالجة اللغة الطبيعية ، والمعلوماتية الحيوية ، وما إلى ذلك. عند إعطاء مجموعة من الملاحظات ، يمكن لتقنيات البرمجة الديناميكية مثل Viterbi و Forward-Backward تحديد التسلسل الأكثر احتمالية للحالات المخفية.
تُظهر أشجار النشوء والتطور الروابط بين الأنواع أو الجينات بمرور الوقت. من الممكن استنتاج أسلاف مشتركين ، وتواريخ الاختلاف ، والأحداث التطورية من هذه القواسم المشتركة. أيضًا ، يمكن استخدام خوارزمية البرمجة الديناميكية مثل Fitch و Sankoff لإنشاء أشجار النشوء والتطور المثلى باستخدام بيانات التسلسل.
# 5. التشفير
يستفيد علم التشفير ، وهو دراسة الاتصالات السرية ، من قدرات حل مشكلات البرمجة الديناميكية. يعد التشفير وفك التشفير والتوقيعات الرقمية والمصادقة والعمليات المماثلة الأخرى جزءًا من التشفير.
يحول التشفير المعلومات من يمكن قراءتها بواسطة الإنسان إلى مفتاح سري مقروء. فك التشفير هو عملية تحويل البيانات المشفرة مرة أخرى إلى نص عادي باستخدام المفتاح الأصلي أو مفتاح جديد. تسمح التوقيعات الرقمية بالتحقق من صحة وسلامة رسالة أو مستند. يمكن أن يتحقق التحقق من بيانات اعتماد المرسل أو المتلقي من هوية المرسل أو المتلقي.
يمكن تنفيذ أنواع مختلفة من التشفير ، بما في ذلك تشفير المفتاح الديناميكي ، والتشفير القائم على الشفرة ، والتشفير الديناميكي القائم على البرمجة ، باستخدام البرمجة الديناميكية.
تشفير المفتاح الديناميكي هو آلية لتشفير وفك تشفير الرسائل باستخدام مفاتيح متغيرة باستمرار. المفاتيح "الديناميكية" هي تلك التي تتطور بمرور الوقت أو استجابةً لعوامل أخرى. هذا يجعلها أكثر أمانًا من المفاتيح الثابتة ، والتي تكون عرضة للهجمات. من الممكن استخدام البرمجة الديناميكية لإنشاء المفاتيح وتحديثها باستمرار عند تنفيذ تشفير المفاتيح الديناميكي.
باستخدام تقنية تُعرف باسم التشفير المستند إلى الكود ، من الممكن تشفير الرسائل وفك تشفيرها عن طريق استخدام أكواد تصحيح الأخطاء في عملية القيام بذلك. من الممكن إصلاح أخطاء الإرسال برموز تصحيح الأخطاء. يُنظر إلى استخدام التشفير المستند إلى الشفرة على نطاق واسع على أنه مقاوم للكم لأنه آمن ضد الهجمات من أجهزة الكمبيوتر الكمومية. يمكن استخدام البرمجة الديناميكية لتشفير وفك تشفير الاتصالات باستخدام نظام تشفير قائم على الكود.
كطريقة لتشفير وفك تشفير البيانات ، يعتمد التشفير الديناميكي القائم على البرمجة على خوارزمية برمجة ديناميكية. من أجل مواجهة تحديات التحسين ، عادةً ما تقسم تقنيات البرمجة الديناميكية المشكلة إلى مجموعة من المشكلات الفرعية الأبسط. يستخدم تشفير البرمجة الديناميكية حقيبة الظهر وأقصر مسار ونحت التماس.
ما هو العالم الحقيقي مثال على البرمجة الديناميكية؟
تستخدم الأمثلة العديدة لتطبيقات البرامج الواقعية البرمجة الديناميكية للحفاظ على السرعة والكفاءة مع تقليل تأثير مواردها على النظام المضيف. بعض الأمثلة هي كما يلي:
- خرائط جوجل. تستخدم خرائط Google البرمجة الديناميكية للعثور على أسرع طريق من أصل معين إلى عدة وجهات مختلفة.
- الشبكات. نقل البيانات المتسلسل من مرسل واحد إلى عدة مستلمين.
- المدققات الإملائية. تحدد خوارزمية تعديل المسافة عدد الخطوات اللازمة لتحويل كلمة إلى أخرى وتوفر مقياسًا كميًا لدرجة الاختلاف بين الكلمتين.
- برامج الانتحال. تساعد طرق مسافة المستند في تحديد تشابه المستند النصي.
- محركات البحث. لتحديد مدى تشابه جزأين من محتوى الإنترنت.
كيف تحل مشاكل البرمجة الديناميكية؟
تعلم صيغة حل مشاكل البرمجة الديناميكية هو الخطوة التالية بعد فهم مفهوم البرمجة الديناميكية. فيما يلي بعض الاقتراحات حول كيفية تطبيق البرمجة الديناميكية على المشكلة المطروحة والتوصل إلى حل عملي:
# 1. اعترف بمشكلة البرمجة الديناميكية
الجزء الأكثر أهمية هو إدراك أن خوارزمية البرمجة الديناميكية يمكنها حل بيان المشكلة المحدد. يتطلب حل هذه المشكلة تحديد ما إذا كان من الممكن تقسيم كل عبارات المشكلة إلى أجزاء أصغر كوظيفة.
# 2. تحديد أسباب المشكلة
إذا كنت قد استنتجت بالفعل أن البرمجة الديناميكية هي الأداة المناسبة للوظيفة ، فإن الخطوة التالية هي تحديد البنية التكرارية للمشكلة بين المشكلات الفرعية المكونة لها. في هذه الحالة ، يجب أن تأخذ في الاعتبار الطبيعة المتغيرة لظروف المشكلة. يمكن أن يكون هذا المتغير موضع صفيف أو مشكلة في سرعة الدقة.
بالإضافة إلى ذلك ، يعد حساب الأجزاء المكونة للمشكلة أمرًا بالغ الأهمية.
# 3. اختر بين أسلوب تكراري وتكراري
لإصلاح مشاكل البرمجة الديناميكية ، يمكنك استخدام الأساليب التكرارية أو العودية. مما قيل حتى الآن ، من الآمن أن نقول إن الطريقة العودية هي الأفضل. ومع ذلك ، فإن جميع الاعتبارات المذكورة أعلاه تظل قائمة بذاتها ، بغض النظر عن الطريقة المختارة لحل المشكلة.
يحتاج كل من النهجين التكراري والتكراري إلى تحديد علاقة التكرار والحالة الأساسية للمشكلة.
# 4. دمج نظام الحفظ
عند معالجة مشكلة بهيكل مماثل ، قد يكون من المفيد تذكر الخبرة السابقة في التعامل مع المشكلات الفرعية المماثلة. نتيجة لذلك ، سوف ينخفض تعقيد المشكلة الزمني. قد يزداد التعقيد الزمني لمهمة ما بشكل كبير إذا واصلنا حل المشكلات الفرعية نفسها مرارًا وتكرارًا دون استخدام الحفظ.
# 5. ضع علاقة التكرار في الكلمات
عند حل مشكلة ما ، يتخطى العديد من المبرمجين تحديد علاقة التكرار والانتقال مباشرة إلى الترميز. سيكون لديك فهم أفضل للمشكلة وستكون قادرًا على ترميزها بسرعة أكبر إذا كان بإمكانك التعبير عن علاقة التكرار بشكل صريح قبل البدء.
البرمجة الديناميكية الخوارزمية
تتضمن معظم تطبيقات البرمجة الديناميكية الخوارزمية العودية. يشير استخدام البرمجة الديناميكية من أجل التحسين إلى أن التكرار أمر جوهري لمعظم مشكلات التحسين.
ومع ذلك ، لا يمكن حل جميع المشكلات المتكررة باستخدام البرمجة الديناميكية. يمكن أن تجد العودية الحل فقط من خلال استراتيجية فرق تسد ما لم يكن هناك وجود مشاكل فرعية متداخلة ، كما هو الحال في مشكلة تسلسل فيبوناتشي.
هذا لأن المشاكل الفرعية الأساسية في خوارزمية عودية مثل Merge Sort لا تتداخل ، مما يستبعد استخدام البرمجة الديناميكية.
أنواع مختلفة من خوارزميات البرمجة الديناميكية
فيما يلي الأنواع المختلفة لخوارزميات البرمجة الديناميكية.
# 1. أطول نتيجة مشتركة
من الممكن أن تظهر عناصر أطول سلسلة متتابعة مشتركة (LCS) بأي ترتيب ضمن التسلسلات الأصلية ؛ يتم تعريف LCS على أنه أطول سلسلة متتالية مشتركة بين جميع التسلسلات المحددة.
إذا تم توفير تسلسلين S1 و S2 ، فإن التسلسل Z الذي هو تتابع لكل من S1 و S2 يسمى تتابعاتهما المشتركة. كشرط إضافي ، يجب أن تتكون Z من تسلسل تصاعدي صارم لمؤشرات المجموعتين S1 و S2.
يجب زيادة مؤشرات العناصر المحددة في Z بشكل صارم لتشكيل تسلسل صاعد.
# 2. خوارزمية فلويد وارسال
هدف خوارزمية Floyd-Warshall هو إيجاد أقصر مسار بين كل زوج من القمم في الرسم البياني الموزون. تعالج هذه الطريقة الرسوم البيانية بالأوزان في كلا الاتجاهين. من ناحية أخرى ، يفشل في الدورات التي يكون فيها مجموع حوافها سالبًا.
خوارزمية Floyd ، وخوارزمية Roy-Floyd ، وخوارزمية Roy-Warhshall ، وخوارزمية WFI كلها أسماء لخوارزمية Floyd-Warhshall.
تستخدم هذه الخوارزمية تقنية برمجة ديناميكية لتحديد الاختصارات المثلى.
كيف تحل خوارزمية البرمجة الديناميكية مشاكل Lcs بشكل أسرع من الأسلوب التكراري؟
تقلل البرمجة الديناميكية من عبء استدعاء الوظيفة. يتذكر نتيجة كل استدعاء وظيفي بحيث يمكن للمكالمات اللاحقة الاستفادة من البيانات المخزنة دون تكرار نفس العمل.
في كل مرة تتم فيها مقارنة عنصر X بعنصر Y ، تتم كتابة النتائج في جدول بحيث يمكن استخدامها في الحسابات اللاحقة في العملية الديناميكية المذكورة أعلاه.
لذلك ، فإن وقت تشغيل الطريقة الديناميكية هو نفس الوقت اللازم لملء الجدول (O (mn)). في المقابل ، فإن تعقيد الخوارزمية العودية هو 2max (m ، n). اقرأ أيضًا كيفية اختيار النوع المناسب من خوارزمية التشفير لاحتياجات عملك
ما هي مشاكل البرمجة الديناميكية في بايثون
باستخدام البرمجة الديناميكية ، يمكن للمرء تحديد الحل الأنسب لأي عدد من عبارات المشكلة المختلفة. في ما يلي ، سنستعرض بعض عبارات المشكلات الشهيرة الأكثر طلبًا ونقدم شرحًا موجزًا جنبًا إلى جنب مع كود Python المناسب.
# 1. الحقيبة (0-1) محدودة
في هذه الحالة ، يتم إعطاؤك أسعار وأوزان البضائع N وتكليفك بوضعها في حقيبة ظهر بسعة W ؛ الهدف هو تقليل عدد العناصر المختارة مع الاستمرار في تركيب كل شيء في الحقيبة.
تتطلب معظم المقابلات الفنية لمؤسسات السلع من المرشحين حل مشكلة الحقيبة ، وهو مثال كلاسيكي على تقنية البرمجة الديناميكية.
بيان المشكلة افترض أن لديك حقيبة بسعة W وقائمة بالأشياء ، لكل منها وزن وربح مماثل. الهدف هو زيادة الأرباح إلى الحد الأقصى عن طريق الملء السيئ الفعال.
الإجابة هي عمل جدول بأعمدة لكل وزن يمكن تصوره بين 1 و W وصفوف للأوزان التي تحددها بالفعل. سيعرف هذا الجدول باسم dp [] []. إذا كانت "j" هي سعة الحقيبة وتم تضمين عناصر "i" الأولى في مصفوفة الوزن / العنصر ، فإن الحالة / الخلية dp [i] [j] في الجدول تشير إلى أعلى ربح ممكن.
نتيجة لذلك ، ستشير القيمة الموجودة في الخلية النهائية إلى الحل. من المهم أن تحزم فقط ما لا يتجاوز الوزن المسموح به على الحقيبة. يوجد بديلان لمعيار "الوزن> الوزن [i-1]" حيث يمكن ملء جميع الأعمدة.
# 2. 0/1 حقيبة مقيدة بعلامة تجارية
املأ كيسًا بالعناصر المعروفة بالوزن والربح ، بحجم K. هدفك هو زيادة أرباحك إلى أقصى حد. هنا ، سنستخدم الحفظ بدلاً من الجدولة لمعرفة ما إذا كان بإمكاننا حل المشكلة.
استخدمت مشكلة حقيبة الظهر 0/1 المذكورة أعلاه استراتيجية من أسفل إلى أعلى لاكتشاف حل ، بينما تستخدم هذه المشكلة نهجًا من أعلى إلى أسفل يعتمد على الحفظ للحصول على حل.
تستخدم البرمجة الديناميكية الحفظ لتقليل الحاجة إلى حل نفس أجزاء المشكلة عدة مرات. هذا يلغي الحاجة إلى حل المشكلة الفرعية باستمرار ويبسط عملية توليد المخرجات.
بيان المشكلة افترض أن لديك حقيبة بسعة W وقائمة بالأشياء ، لكل منها وزن وربح مماثل. إذا كانت الحقيبة ممتلئة بأكبر قدر ممكن من الكفاءة ، فيمكن للمرء الحصول على أعلى مستوى محتمل للربح.
الحل هو أولاً إنشاء مصفوفة ثنائية الأبعاد لعقد الإجابات النهائية للمشكلات الفرعية الفردية. ستدرج أعمدة الجدول جميع الأوزان المحتملة بين 1 و W ، وتقسيمها إلى العديد من الأقسام ، وستعرض الصفوف الأوزان التي تحددها في كل مرة.
نستخدم مصفوفة dp لتتبع كل مشكلة فرعية تم حلها. بدلاً من حل مشكلة فرعية تم حلها مسبقًا ، نرجع إجابتها فقط.
# 3. مشكلة مجموعة جزئية متساوية
ابحث عن قسم من المجموعة المحددة بحيث يكون إجمالي العناصر في كلتا المجموعتين الفرعيتين هو نفسه باستخدام البرمجة الديناميكية لحل مشكلة المجموعة الفرعية المتساوية. بالإضافة إلى أسمائها الأخرى ، فإن مشكلة المجموعة الفرعية المتساوية (أو مشكلة التقسيم) هي توضيح رئيسي لقوة البرمجة الديناميكية.
تتطلب المهمة التي نحن بصددها تقسيم المصفوفة إلى نصفين بحيث يكون لكل من المجموعات الفرعية التالية نفس الحجم الكلي.
كحل ، نحتاج إلى بناء مصفوفة ثنائية الأبعاد بأبعاد (مجموع / 2 + 1) * (هدف + 1). هنا ، يمكن تخزين نتائج تقسيم المصفوفة الأصلية لكل مجموعة فرعية وكل مجموع ، واسترجاعها لاحقًا. سيمثل البعد الأول للمصفوفة المجموعات الفرعية المختلفة التي يمكن إنشاؤها ، بينما سيمثل البعد الثاني للصفيف المجاميع المختلفة التي يمكن حسابها من خلال الجمع بين المجموعات الفرعية.
مزايا البرمجة الديناميكية
فيما يلي بعض مزايا البرمجة الديناميكية.
# 1. علاج فعال
البرمجة الديناميكية هي أداة قوية لإيجاد الحلول المثلى للقضايا المتعلقة بالبنية التحتية المثلى والمشاكل الفرعية المتداخلة. من خلال تحليلها إلى أجزاء يمكن التحكم فيها ، يسهل التعامل مع هذه التحديات بهذه الطريقة. البرمجة الديناميكية قادرة على إنشاء حل أمثل عن طريق تجنب الحسابات المتكررة وإعادة استخدام الإجابات على المشاكل الفرعية.
# 2. يسهل إيجاد المشاكل بسهولة
يمكن أن يكون حل مشكلة صعبة أسهل عن طريق تحليلها أولاً إلى أجزاء أبسط. إنه يسهل معالجة المشكلات المعقدة عن طريق تقسيمها إلى أجزاء يسهل التحكم فيها. هذه الطريقة تبسط الحل وتجعل المشكلة أكثر سهولة.
# 3. فعال
من خلال التخلص من الحسابات غير الضرورية وإعادة تدوير المشكلات الفرعية التي تم حلها مسبقًا ، يمكن أن تقلل البرمجة الديناميكية بشكل كبير من الوقت المطلوب لحل المشكلة. عندما تتداخل المشاكل الفرعية ، يمكن أن تساعد الطريقة عن طريق تقليل العدد الإجمالي للإجراءات المطلوبة لحل المشكلة.
# 4. فعالة عندما يكون للمشكلة حلول متعددة
يمكن أن تساعد البرمجة الديناميكية في تحديد التفسيرات المحتملة العديدة التي من المرجح أن تكون هي الحالة. عندما يكون هناك العديد من الخيارات القابلة للتطبيق لإصلاح مشكلة ، يمكن أن تساعدنا هذه الطريقة في التركيز على أفضلها.
ما هي عيوب البرمجة الديناميكية؟
فيما يلي بعض عيوب البرمجة الديناميكية.
# 1. القضايا الفرعية التي تتكرر باستمرار
تعمل البرمجة الديناميكية بشكل أفضل عندما تحتوي المشكلة على مشاكل فرعية متداخلة ، والتي قد لا تكون كذلك دائمًا. لن ينجح الأمر ، وربما لن يوفر لك الحل الأفضل ، إذا لم تتقاطع المشاكل الفردية.
# 2. التعقيد في الزمان والمكان
إذا كانت المشكلة كبيرة ، فقد تتطلب البرمجة الديناميكية مساحة كبيرة من الذاكرة والتخزين ، مما يزيد من تعقيد الحل في الوقت والمساحة. باستخدام الذاكرة ، يخزن الأسلوب النتائج المؤقتة في جدول أو جدول حفظ.
# 3. إطار القضية
على الرغم من فعاليتها في بعض هياكل المشكلات ، إلا أن البرمجة الديناميكية ليست دائمًا الخيار الأفضل. تعمل هذه الطريقة بشكل أفضل عندما تحتوي المشكلة على مشاكل فرعية متداخلة ، وبالتالي قد لا تنطبق على المواقف الأخرى.
# 4. من الصعب وضعها موضع التنفيذ
تحتاج البرمجة الديناميكية إلى معرفة متعمقة بالخوارزميات وهياكل البيانات ، مما يجعل تنفيذها أمرًا صعبًا للمبتدئين. تتطلب الطريقة التفكير المسبق والإلمام العميق بالقضية المطروحة.
الحد الأدنى
في الختام ، تعد البرمجة الديناميكية طريقة فعالة للعثور على إجابات ، على الرغم من تفضيل الأساليب الأخرى. من الأهمية بمكان معرفة الإيجابيات والسلبيات واختيار الطريقة الصحيحة وفقًا للقضية المطروحة. بالنسبة للمشكلات المتعلقة بالبنية التحتية المثلى والمشكلات الفرعية المتداخلة ، يمكن أن تسفر البرمجة الديناميكية عن الحل الأمثل ؛ ومع ذلك ، قد لا تكون هذه الطريقة قابلة للتطبيق دائمًا.
على الرغم من صعوبة تطوير واستخدام الكثير من الذاكرة ، إلا أن قدرتها على تبسيط عملية حل المشكلات وتقصير أوقات الحساب تجعلها موردًا مهمًا لعلماء الكمبيوتر وعلماء الرياضيات.
الأسئلة الشائعة حول البرمجة الديناميكية
ما هو الفرق بين البرمجة الخطية والبرمجة الديناميكية؟
بالنسبة لمشاكل التحسين الخطي ، لدينا خوارزمية البرمجة الخطية (LP) ، وبالنسبة لمشاكل التحسين غير الخطية العامة ذات القيود غير المحدبة ، لدينا برمجة ديناميكية (DP) ، والتي تضمن الأمثلية العالمية للحل.
ما مدى صعوبة تعلم البرمجة الديناميكية؟
من المعروف أن البرمجة الديناميكية هي موضوع معقد ، خاصة بالنسبة للقادمين الجدد في مجال علوم الكمبيوتر. ومع ذلك ، يمكن للمرء أن يتعلم البرمجة الديناميكية بسهولة من خلال فهم راسخ للمبادئ الأساسية والممارسة الواسعة.
هل البرمجة الديناميكية صعبة للغاية؟
إنهم صعبون! للبدء ، قد يكون من الصعب فهم فكرة طرق البرمجة الديناميكية. يشهد أي مبرمج خبير أن إتقان برنامج DP يتطلب التزامًا كبيرًا بالوقت. من الضروري أيضًا مهارة تحليل المشكلة إلى الأجزاء المكونة لها وإعادة تجميعها في كل قابل للتطبيق.
مقالات مماثلة
- إدارة وقت المشروع: العمليات والأدوات والبرامج للإدارة الفعالة
- AMAZON SEO: كيفية تحسين منتجاتك لترتيب أفضل
- لغات البرمجة الأكثر شيوعًا: دليل 2023
- ما هي برمجة الكمبيوتر: أمثلة ، أنواع ، دورات وبرامج
- الوصايا على الإنترنت: أفضل صانعي الإرادة على الإنترنت.
الرقم المرجعي
