البرمجة الديناميكية: الخصائص ، مثال ، المزايا ، العيوب - تقنية - 2026

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

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

البرمجة الديناميكية. المشاكل الفرعية متراكبة في تسلسل فيبوناتشي. المصدر: Wikimedia commons، en: User: Dcoatzee، trace by User: Stannered / Public domain

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

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

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

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

الخصائص الأساسية التالية هي ما يجب أن تواجه مشكلة فيه قبل أن تتمكن من تطبيق البرمجة الديناميكية:

البنية التحتية المثلى

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

على سبيل المثال ، في الرسم البياني ، سيتم تقديم البنية التحتية المثلى في أقصر مسار r الذي ينتقل من قمة s إلى قمة t:

وهذا يعني أنه في هذا أقصر مسار r يمكن اتخاذ أي قمة وسيطة. إذا كان r حقًا هو أقصر طريق ، فيمكن تقسيمه إلى subroutes r1 (من s إلى i) و r2 (من i إلى t) ، بحيث تكون هذه بدورها أقصر الطرق بين القمم المقابلة.

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

المشاكل الفرعية المتداخلة

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

على سبيل المثال ، لإنشاء سلسلة فيبوناتشي ، يمكننا اعتبار هذه الصيغة العودية: Fn = F (n - 1) + F (n - 2) ، مع الأخذ في الاعتبار أن F1 = F2 = 1. ثم سنحصل على: F33 = F32 + F31 و F32 = F31 + F30.

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

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

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

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

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

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

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

يتم ذلك أيضًا بشكل عام في شكل جدول ، حيث يتم إنشاء حلول متكررة للمشاكل الفرعية الأكبر والأكبر باستخدام حلول للمشكلات الفرعية الأصغر. على سبيل المثال ، إذا كانت قيم F31 و F30 معروفة بالفعل ، فيمكن حساب قيمة F32 مباشرة.

مقارنة مع تقنيات أخرى

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

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

مثال

الحد الأدنى من الخطوات للوصول إلى 1

لأي عدد صحيح موجب "e" يمكن تنفيذ أي من الخطوات الثلاث التالية.

- اطرح 1 من الرقم. (ه = ه -1).

- إذا كانت قابلة للقسمة على 2 ، فإنها تقسم على 2 (إذا كانت e٪ 2 == 0 ، فإن e = e / 2).

- إذا كانت قابلة للقسمة على 3 ، فإنها تقسم على 3 (إذا كانت e٪ 3 == 0 ، فإن e = e / 3).

بناءً على الخطوات المذكورة أعلاه ، يجب العثور على الحد الأدنى لعدد هذه الخطوات لإحضار e إلى 1. على سبيل المثال:

- إذا كانت e = 1 ، تكون النتيجة: 0.

- إذا كانت e = 4 ، فالنتيجة: 2 (4/2 = 2/2 = 1).

- عندما تكون e = 7 ، تكون النتيجة: 3 (7-1 = 6/3 = 2/2 = 1).

التركيز

قد يفكر المرء دائمًا في اختيار الخطوة التي تجعل n أدنى مستوى ممكن والاستمرار على هذا النحو ، حتى تصل إلى 1. ومع ذلك ، يمكن ملاحظة أن هذه الإستراتيجية لا تعمل هنا.

على سبيل المثال ، إذا كانت e = 10 ، ستكون الخطوات: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 خطوات). ومع ذلك ، فإن الشكل الأمثل هو: 10-1 = 9/3 = 3/3 = 1 (3 خطوات). لذلك ، يجب تجربة جميع الخطوات الممكنة التي يمكن القيام بها لكل قيمة n تم العثور عليها ، واختيار الحد الأدنى لعدد هذه الاحتمالات.

كل شيء يبدأ بالعودية: F (e) = 1 + min {F (e-1)، F (e / 2)، F (e / 3)} إذا كانت e> 1 ، مع الأخذ كحالة أساسية: F (1) = 0. بوجود معادلة التكرار ، يمكنك البدء في ترميز العودية.

ومع ذلك ، يمكن ملاحظة أن لديها مشاكل فرعية متداخلة. علاوة على ذلك ، يعتمد الحل الأمثل لمدخل معين على الحل الأمثل لمشاكله الفرعية.

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

حفظ

البرمجة الديناميكية من أسفل إلى أعلى

مميزات

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

الخوارزميات الشرهة مقابل البرمجة الديناميكية

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

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

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

سلبيات

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

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

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

العودية مقابل البرمجة الديناميكية

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

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

التطبيقات

البرمجة الديناميكية هي طريقة فعالة لحل المشكلات التي قد يبدو حلها صعبًا للغاية في فترة زمنية معقولة.

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

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

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

- سلسلة أرقام فيبوناتشي.

- أبراج هانوي.

- جميع أزواج الطرق الأقصر عبر Floyd-Warshall.

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

- جدولة المشروع.

- أقصر طريق عبر Dijkstra.

- التحكم في الطيران والتحكم في الروبوتات.

- مسائل التحسين الرياضي.

- المشاركة بالوقت: جدولة المهمة لتعظيم استخدام وحدة المعالجة المركزية.

سلسلة أرقام فيبوناتشي

أرقام فيبوناتشي هي الأرقام الموجودة في التسلسل التالي: 0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89 ، 144 ، إلخ.

في المصطلحات الرياضية ، يتم تحديد تسلسل Fn لأرقام فيبوناتشي بواسطة صيغة التكرار: F (n) = F (n -1) + F (n -2) ، حيث F (0) = 0 و F (1) = 1.

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

في هذا المثال ، يتم تهيئة مصفوفة بحث بكل القيم الأولية بـ -1. كلما دعت الحاجة إلى حل مشكلة فرعية ، سيتم البحث في مصفوفة البحث هذه أولاً.

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

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

في هذه الحالة ، لنفس سلسلة فيبوناتشي ، يتم حساب f (0) أولاً ، ثم f (1) ، f (2) ، f (3) ، وهكذا. وبالتالي ، يتم بناء حلول المشكلات الفرعية من الأسفل إلى الأعلى.

المراجع

1. فينيت شودري (2020). مقدمة في البرمجة الديناميكية. مطور إنسايدر مأخوذ من: developerinsider.co.
2. أليكس ألين (2020). البرمجة الديناميكية في C ++. البرمجة C. مأخوذة من: cprogramming.com.
3. بعد الأكاديمية (2020). فكرة البرمجة الديناميكية. مأخوذة من: afteracademy.com.
4. أنيرودا تشودري (2019). البرمجة الديناميكية والتكرار - الاختلاف والمزايا مع المثال. مكدس CSE. مأخوذة من: csestack.org.
5. كود شيف (2020). البرنامج التعليمي للبرمجة الديناميكية. مأخوذة من: codechef.com.
6. Programiz (2020). البرمجة الديناميكية. مأخوذة من: programiz.com.