مقدمة في البرمجة الديناميكية: المشاكل الفرعية المتداخلة والبنية التحتية المثلى
نشرت: 2021-02-08جدول المحتويات
مقدمة
لنفترض أن لدينا سؤالاً لحل مربع 25. إذا واجهنا هذا السؤال لأول مرة ، فيمكننا حله إما في متناول اليد أو باستخدام الآلة الحاسبة. ولكن إذا رأينا هذا السؤال من قبل أو حللناه من قبل ، فهناك احتمال أن نجيب عليه بسرعة عن طريق حفظه.
يقودنا هذا إلى استنتاج مفاده أنه إذا تمكنا من تذكرها ، فيمكننا تخطيها في المرة القادمة. تعمل البرمجة الديناميكية على مفهوم مماثل ، والفكرة هي تذكر نتيجة الحساب واستخدامه في المستقبل إذا لزم الأمر.
هذا الإجراء البسيط للبرمجة الديناميكية يجعله سلاحًا قويًا للمبرمج لقهر معركة الكود الفعال.
على سبيل المثال ، لنفترض أن لدينا سؤالًا معقدًا ونفكر دائمًا في حل يقسم السؤال إلى مشاكل فرعية. لكننا قد نتعثر في موقف حيث سنقوم بحساب مشكلة فرعية عدة مرات. هناك نستخدم البرمجة الديناميكية لحل أمثل.
البرمجة الديناميكية لها مفهومان:
- المشاكل الفرعية المتداخلة
- البنية التحتية المثلى
المشاكل الفرعية المتداخلة
المثال الكلاسيكي لفهم مفهوم المشكلة الفرعية المتداخلة هو برنامج لطباعة سلسلة فيبوناتشي.
يتم إعطاء منطق سلسلة فيبوناتشي بواسطة "فيبوناتشي (ن) = فيبوناتشي (ن -1) + فيبوناتشي (ن -2)". ويمكن تنفيذ هذه الوظيفة بسلاسة باستخدام محلول متكرر ، مع حالة أساسية من فيبوناتشي (0) = 0 وفيبوناتشي (1) = 1.
| فيبوناتشي العامة الثابتة (int n) { إذا (ن == 0 || ن == 1 ) عودة ن ؛ عودة فيبوناتشي (ن -1 ) + فيبوناتشي (ن -2 ) ؛ } العامة الثابتة الفراغ الرئيسي (سلسلة [] args) { System.out.print ( "رقم فيبوناتشي الرابع هو" + فيبوناكسي ( 4 )) ؛ } |
لنفترض أننا بحاجة إلى طباعة رقم فيبوناتشي الرابع ، ثم تصبح شجرة العودية كما هي
فيبوناكسي (4)
/ \
فيبوناكسي (3) + فيبوناتشي (2)
/ \ / \
فيبوناتشي (2) + فيبوناكسي (1) فيبوناتشي (1) + فيبوناتشي (0)
/ \
فيبوناتشي (1) + فيبوناتشي (0)
لاحظ أن فيبوناتشي (4) هو الرقم الخامس في سلسلة فيبوناتشي لأننا نبدأ من فيبوناتشي (0). في شجرة العودية أعلاه ، يمكننا أن نرى أن فيبوناتشي (2) يتكرر مرتين. لقد لاحظنا ازدواجية في شجرة عودية بارتفاع 4 ، والآن تخيل أن لدينا نداء تكراري بعدد ضخم ، وبعد ذلك ، ستكون هناك شجرة عودية بارتفاع كبير. وسيكون هناك العديد من هذه الحسابات المكررة ، والتي تُعرف بالمشكلات الفرعية المتداخلة.
لدينا طريقتان للتعامل مع هذا (1) الجدولة ، (2) الحفظ
دعونا نفهمها من خلال استعراض تطبيقاتها.
Memoization
يمكن حل مشكلة فيبوناتشي باستخدام طريقة الحفظ كما هو موضح أدناه
| مذكرة int [] ثابتة ؛ فيبوناتشي العامة الثابتة (int n) { إذا (مذكرة [n]! = - 1) عودة المذكرة [ن] ؛ إذا (n == 0 || n == 1) { مذكرة [ن] = ن ؛ عودة ن ؛ } مذكرة [ن] = فيبوناتشي (ن -1) + فيبوناتشي (ن -2) ؛ عودة المذكرة [ن] ؛ } العامة الثابتة الفراغ الرئيسي (سلسلة [] args) { memo = new int [5] ؛ لـ (int i = 0 ؛ i <= 4 ؛ i ++) مذكرة [i] = - 1 ؛ System.out.println ("رقم فيبوناتشي الرابع هو" + فيبوناكسي (4)) ؛ } |
في الكود أعلاه ، نقوم بإنشاء ملف سجل للاحتفاظ أو الاحتفاظ بجدول بحث وتخزين قيم النتائج المحسوبة. نظرًا لأننا حفظنا جميع القيم المحسوبة ، يمكننا استخدامها في المستقبل إذا لزم الأمر ، وبالتالي تجنب الحسابات المكررة والمشاكل الفرعية المتداخلة.
كل المنطق مشابه للحل العودي ، لكن الاختلاف الوحيد الذي أحدثناه هو أننا نلاحظها في مصفوفة المذكرات قبل أن نعيد القيمة إلى الطريقة الرئيسية. القيد الوحيد لهذه الخوارزمية هو أننا نحتاج إلى مساحة إضافية بالحجم O (n) ، لكننا نقوم بتحسين الحل العودي السابق.
جدولة
هذه الطريقة مختلفة قليلاً عن الحل أعلاه. Memoization يتبع نفس الحل العودي. لكن في الجدولة ، نتبع حلاً تكراريًا. ويسمى أيضًا النهج التصاعدي. دعونا نلقي نظرة على تنفيذ النهج التصاعدي.
| فيبوناتشي العامة الثابتة (int n) { جدول int [] = new int [n + 1 ] ؛ لـ (int i = 0 ؛ i <= n ؛ i ++) { إذا (أنا == 0 || أنا == 1 ) الجدول [i] = أنا ؛ آخر { جدول [i] = جدول [i -1 ] + جدول [i -2 ] ؛ } } جدول العودة [ن] ؛ } العامة الثابتة الفراغ الرئيسي (سلسلة [] args) { System.out.println ( "رقم فيبوناتشي الرابع هو" + فيبوناكسي ( 4 )) ؛ } |
كما نعلم أن فيبوناتشي (ن) = فيبوناتشي (ن -1) + فيبوناتشي (ن -2) ، في الحفظ بدأنا باستدعاء دالة فيبوناتشي (4) ، ثم أدركنا أننا لم نحسب قيمتها ، لذلك نحن قمنا بحساب قيمها ثم تخزينها.
سيواجه موقف مشابه من خلال استدعاءات متكررة أخرى مثل فيبوناتشي (3) ، فيبوناتشي (2). الآن هذا يجعل الكثير من المكالمات العودية تنتظر في مكدس العودية ، ولكن على أي حال نحن نتخطى تكرار المشاكل الفرعية المتداخلة.
لدينا أيضًا طريقة لحساب فيبوناتشي من 0 إلى العنصر n بشكل تكراري ثم إعادة عنصر فيبوناتشي nth. هذا ما قمنا بتطبيقه في الكود أعلاه. يحتوي هذا الرمز أيضًا على نفس متطلبات المساحة O (n).
الخروج: مهارات لتصبح مطور مكدس كامل
البنية التحتية المثلى
في هذا المفهوم ، لا يمكننا الحصول على الحل الأمثل لمشكلة ما إلا إذا قمنا بحل المشكلات الفرعية المقابلة لها بالشكل الأمثل.
والمثال الكلاسيكي لهذا المفهوم هو النظر في المسح بين العقد في الرسم البياني.
لنفترض أن لدينا جذورًا متعددة من تيلانجانا إلى دلهي. وإذا كان لدينا أقصر طريق يمر عبر ناجبور وجواليور. ثم يجب أن يمر أقصر طريق من ناجبور إلى دلهي عبر جواليور. الآن يمكننا تقسيم مشكلتنا إلى مشكلات فرعية وهي تيلانجانا إلى ناجبور ، وناغبور إلى جواليور ، وجواليور إلى دلهي.
والمثال الكلاسيكي لهذه الخاصية هو أطول نتيجة شائعة في كلتا السلسلتين. اللاحقة تختلف عن سلسلة فرعية. في اللاحقة ، لا يلزم أن تكون الأحرف مترتبة في السلسلة الأصلية.
لذا فإن الفكرة هي حلها عن طريق حل مشاكلها الفرعية على النحو الأمثل. لنفترض أن n هو طول أطول عملية تالية شائعة.
إذا كانت n = LCS (بطاطس ، وشم) ، فعندئذٍ n = LCS (بطاطس ، تاتو) +1 (إذا كانت الأحرف الأخيرة متطابقة) ، وإلا n = الحد الأقصى (LCS (بطاطس ، تاتو) ، LCS (بطاطس ، وشم).
| ثابت int lcs (String s1، String s2، int m، int n) { int dp [] [] = new int [m + 1 ] [n + 1 ] ؛ لـ (int i = 0 ؛ i <= m ؛ i ++) { لـ (int j = 0 ؛ j <= n ؛ j ++) { إذا (i == 0 || j == 0 ) dp [i] [j] = 0 ؛ وإلا إذا (s1.charAt (i -1 ) == s2.charAt (ي -1 )) dp [i] [j] = dp [i -1 ] [j -1 ] + 1 ؛ آخر dp [i] [j] = Math.max (dp [i -1 ] [j] ، dp [i] [j -1 ]) ؛ } } عودة موانئ دبي [م] [ن] ؛ } العامة الثابتة الفراغ الرئيسي (سلسلة [] args) { System.out.println ( "الجزء الأكبر من التتابع المشترك الأطول هو" + lcs ( "البطاطس" ، "الوشم" ، 6 ، 6 )) ؛ } |
في الكود أعلاه ، قمنا بتطبيق منطقنا باستخدام طريقة الجدولة وحساب طول أطول التتابع المشترك الموجود في كلا السلاسل.
اقرأ أيضًا: راتب Full Stack Developer في الهند
تعلم دورات تطوير البرمجيات عبر الإنترنت من أفضل الجامعات في العالم. اربح برامج PG التنفيذية أو برامج الشهادات المتقدمة أو برامج الماجستير لتتبع حياتك المهنية بشكل سريع.
خاتمة
الآن بعد أن أصبحت على دراية باستخدام إحدى التقنيات القوية للتغلب على معركة الكود الفعال ، حاول تنفيذ البرمجة الديناميكية للمشكلات الأخرى وابدأ في تعزيز قدرتك على كتابة سؤال باستخدام البرمجة الديناميكية.
في الختام ، فإن دورات Full Stack Developers هي خبراء ذوو مهارات عالية يمكنهم التعامل مع كل ما يتعلق بتطوير الويب. مهارات Full Stack Developer هي ما يميزهم عن مطوري الواجهة الأمامية والخلفية.
ما هي البرمجة الديناميكية؟
يحتوي برنامج الكمبيوتر على الكثير من التعليمات البرمجية المتكررة. هذا غير فعال وقد يؤثر على أدائها. في هذه الحالة ، يتم استخدام البرمجة الديناميكية. البرمجة الديناميكية هي طريقة لحل مشكلة معقدة عن طريق تقسيمها إلى مشاكل فرعية أبسط ، وحل كل من هذه المشاكل الفرعية مرة واحدة فقط ، وتخزين حلولها باستخدام الجداول ، والتي يتم البحث عنها بعد ذلك كلما حدثت مشكلة فرعية مماثلة لاحقًا في حل المشكلة المعقدة. تُستخدم خوارزميات البرمجة الديناميكية لحل أنواع مختلفة من مشاكل التحسين في مجالات البحث التشغيلي ، والتقدير الإحصائي ، والتعرف على الأنماط ، والذكاء الاصطناعي ، والتعلم الآلي ، والبيولوجيا الحسابية ، ومجالات أخرى.
ما هي المشكلة الفرعية المتداخلة في البرمجة الديناميكية؟
المشكلة الفرعية المتداخلة هي مفهوم يستخدم عندما يكون للمشاكل الفرعية حلول يتم استخدامها في مشاكل فرعية أخرى أيضًا. يؤدي هذا التداخل إلى حل نفس المهمة الفرعية أكثر من مرة. تكمن المشكلة في إيجاد طريقة لحل المهمة الفرعية مرة واحدة فقط ، واستخدام هذا الحل للحصول على حلول للمشكلات الفرعية الأخرى. تحل خوارزميات البرمجة الديناميكية هذه المشكلة باستخدام الحفظ. Memoization هي تقنية نقوم فيها بتخزين حلول للمشاكل الفرعية حتى لا نضطر إلى حلها مرة أخرى.
ما هي البنية التحتية المثلى في البرمجة الديناميكية؟
تعني البنية التحتية المثلى أن الحل الأمثل لمشكلة ما يرتبط بالحل الأمثل لمشكلة أصغر داخل نفس تعريف المشكلة. البنية التحتية المثلى هي مطلب إضافي مطلوب لحل المشكلات أو لإثبات عدم وجود حل. مع البنية التحتية المثلى ، يمكننا إثبات العديد من المشكلات NP-hard. تتمثل الطريقة العامة لحل مشكلات DP في استخدام مصفوفة البرمجة الديناميكية لتخزين الحل الأمثل للمشكلات الفرعية. يمكن استخدام مصفوفة البرمجة الديناميكية لحل أي مشاكل DP للبنية التحتية المثلى غير الصفرية.