البرمجة الديناميكية، والمبادئ الأساسية

لتحديد الحل الأمثل عند تنفيذ المهام المطلوبة والبرمجة في بعض الأحيان لفرز كميات كبيرة من مجموعات البيانات التي يحمل ذاكرة الكمبيوتر الشخصي. وتشمل هذه الطرق، على سبيل المثال، وطريقة برمجة "فرق تسد". في هذه الحالة توفر الخوارزمية مشكلة الفصل في المهام الفرعية أصغر منفصلة. هذا الأسلوب لا ينطبق إلا في الحالات التي يكون فيها المهام الفرعية الصغيرة المستقلة للطرفين. لتجنب أداء عمل غير ضروري إذا المهام الفرعية المترابطة، يستخدم أسلوب البرمجة الديناميكية المقترح الأمريكي R.Bellmanom في 50s.

طريقة

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

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

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

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

طريقة تحسين أداء المهام حلها عن طريق المتغيرات، أو الإعادة.

خوارزمية مهمة بناء

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

في بعض الأحيان، على 3rd خطوة غير لحفظ بعض المعلومات الأساسية إضافية عن التقدم المحرز في كل مهمة. وهذا ما يسمى السكتة الدماغية العودة.

طريقة التطبيق

يتم تطبيق البرمجة الديناميكية عندما يكون هناك نوعان من السمات المميزة:

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

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

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

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