سلسلة تعلم الخوارزميات: ما هي خوارزميات البرمجة الديناميكية؟
سلسلة تعلم الخوارزميات: ما هي خوارزميات البرمجة الديناميكية؟ تُعرف خوارزميات البرمجة الديناميكية بأنها طريقة حل مشكلة معقدة عن طريق تقسيمها إلى مجموعة من المشاكل الفرعية الأبسط، وحل كل مشكلة فرعية مرة واحدة فقط وتخزين حلولها باستخدام بنية بيانات قائمة على الذاكرة كالمصفوفة أو الخريطة مثلًا. ومن ثم فهرسة كل حل من حلول المشكلة الفرعية بطريقة ما بناءً على قيم معلمات الإدخال الخاصة به وذلك لتسهيل البحث.
لذلك في المرة التالية التي تحدث فيها نفس المشكلة الفرعية، بدلاً من إعادة حساب حلها، يبحث المرء أو الحاسوب ببساطة عن الحل المحسوب مسبقًا وبالتالي توفير وقت الحساب. لتقريب مفهوم خوارزميات البرمجة الديناميكية أكثر تخيل أن شخصًا ما طلب منك حساب مجموع 1+1+1+1+1+1 فبعد أن تقوم بالحساب ستقول له ان الإجابة هي 6. الآن إذا طلب منك +1 للسؤال السابق وطلب منك الإجابة بسرعة فم الذي ستقوم به؟
بالتأكيد لن تقوم بالحساب من جديد لأنك لا زلت تتذكر الجواب السابق وبالتالي ستقوم بإضافة الرقم 1 للجواب السابق 6 وستكون إجابتك للسؤال الجديد هو 7 وهذا بالضبط ما تقوم به خوارزميات البرمجة الديناميكية إذ تُخزن النتائج التي نحصل عليها من المسائل الفرعية وبهذا تنتفي الحاجة إلى إعادة حساب تلك النتائج في وقت لاحق.
محتويات المقال :
يمكن تلخيص خطوات حل مسائل البرمجة الديناميكية كالتالي:
تنتمي مسألة حقيبة الظهر إلى فئة من مسائل “NP”، والتي تعني “زمن كثيرة الحدود غير الحتمية” ويُشير هذا الاسم إلى الكيفية التي تجبر بها هذه المسائلُ جهاز الحاسوب على المرور بالعديد من الخطوات للوصول إلى حل، ويزداد العدد بشكل كبير بناءً على حجم المدخلات. لتبسيط مفهوم مسألة حقيبة الظهر، لنفترض أنك بصدد السفر إلى منطقة ما لزيارة أصدقائك ولديك العديد من الهدايا في داخل حقيبتك ولكن شركة الطيران تسمح لك بحمل وزن معين فقط ولا يجب أن تتعداه فقررت في هذه الحالة تعبئة الحقيبة بعدد معين من الهدايا بحيث تمثل أكبر قيمة ولا تتعدى وزنها الحد المسموح به من الوزن بعبارة أخرى نعبئها بما خف وزنه وغلا ثمنه.
من الواضح في البداية أنَّ ما يجب فعله هو اختبار كل المجموعات الممكنة، وحساب قيمتها ووزنها، ثم اختيار المجموعة التي تحقق الحد المقبول للوزن والحد الأقصى للقيمة. هذا يفي بالغرض إذا كان عدد العناصر قليلا، لكن الأمر يصبح أصعب مع عدد كبير منها ولتوضيح صعوبة الأمر دعنا نبدأ بالمثال التالي: افترض أن لديك في الحقيبة خمسة عناصر والمطلوب منك اختيار العناصر التي تحقق أعلى قيمة وفي الوقت ذاته لا يتجاوز وزنها الحد المسموح به وهو 10 كيلو جرام وكانت العناصر كالتالي: العنصر الأول قيمته 5 دولار ووزنه 4 كيلو جرام.
العنصر الثاني قيمته 10 دولار ووزنه 8 كيلو جرام. العنصر الثالث قيمته 3 دولار ووزنه 3 كيلو جرام. العنصر الرابع قيمته 2 دولار ووزنه 5 كيلو جرام والعنصر الخامس قيمته 3 دولار ووزنه 2 كيلو جرام. بعد القليل من التفكير ستجد أن العنصر الثاني والعنصر الخامس هما أفضل عنصران يحققان أعلى قيمة (13 دولار) وفي الوقت ذاته لا يتجاوزان الوزن المسموح (10 كيلو جرام).
الآن، ماذا لو كان عدد العناصر كبيرًا للغاية؟ إذا استخدمت الطريقة التقليدية للحل ستسهلك الكثير من الوقت لمعرفة مجموعة العناصر التي تحقق شرطي القيمة المثلى والوزن المسموح به بمعنى اخر لو كان لديك 10 عناصر فإن عدد المجموعات الفرعية التي ستقوم بفحصها هو 1024 مجموعة فرعية ومن ثم ستقوم باختيار أنسب مجموع تحقق الشرطين السابقين.
تحقق مسألة حقيبة الظهر شرط البرمجة الديناميكية إذ أنه بالإمكان الحصول على الحل المثالي للمسألة المعطاة بجمع الحلول المثالية للمسائل المتفرّعة عن المسألة الرئيسية. لحل المثال السابق دعنا نرمز للوزن بالرمز w وبما ان الحد المسموح به هو 10 كيلو جرام إذن w=10 .
أيضًا نرمز للعناصر بالرمز n. الخطوة الأولى للحل هو تكوين مصفوفة ثنائية الأبعاد أو بمعنى آخر جدول عدد صفوفه (n+1) وعدد أعمدته (w+1) يعني في مثالنا هذا سيكون عدد الصفوف (5+1=6) وذلك لأنه لدينا 5 عناصر بينما عدد الأعمدة (10+1=11) وذلك لأن أقصى وزن مسموح به 10.
يمثل رقم العمود j سعة وزن حقيبة الظهر الخاصة بنا. لذلك، القيم في العمود 5، على سبيل المثال، تفترض أن حقيبة الظهر الخاصة بنا يمكن أن تحتوي على 5 وحدات وزن. بعد ذلك نبدأ بملء الجدول بالقيم المحسوبة مع ملاحظة أن الصف رقم 0 يمثل الحالة التي لا يوجد لدينا عناصر للاختيار من بينها لذا يجب أن تكون القيمة القصوى التي يمكن تخزينها في أي حقيبة ظهر في هذه الحالة 0.
بالمثل، في العمود 0، بالنسبة للحقيبة التي يمكن أن تحتوي على 0 وحدة وزن، لذا فإن القيمة القصوى التي يمكن تخزينها فيه هي 0. أما بالنسبة لبقية الاعمدة والصفوف فنتبع التالي: لحساب الحد الأقصى للقيمة التي يمكننا الحصول عليها من العنصر i، نحتاج أولاً إلى مقارنة وزن العنصر i بسعة وزن الحقيبة.
من الواضح، إذا كان وزن العنصر أكبر مما يمكن أن تحمله الحقيبة، فلا يمكننا تضمينه، لذلك ليس من المنطقي إجراء الحساب. في هذه الحالة، يكون حل هذه المشكلة هو ببساطة القيمة القصوى التي يمكننا الحصول عليها بدون العنصر i (أي القيمة الموجودة في الصف أعلاه، في نفس العمود). ومع ذلك، لنفترض أن وزن هذا العنصر أقل من سعة حقيبة الظهر.
بالتالي لدينا خيار إدراجه، إذا كان من المحتمل أن يؤدي إلى زيادة الحد الأقصى للقيمة التي يمكن الحصول عليها. وبالتالي، فإن الحد الأقصى للقيمة التي يمكن الحصول عليها من خلال تضمين العنصر i هو = قيمة العنصر i نفسه + القيمة القصوى التي يمكن الحصول عليها مع السعة المتبقية من الحقيبة. بمعنى آخر، نريد الاستفادة الكاملة من سعة حقيبة الظهر الخاصة بنا وعدم ترك أي سعة متبقية تذهب سدى.
وبتطبيق ما سبق على المثال السابق نتحصل على الجدول الآتي:
من الجدول نلاحظ أن أقصى قيمة تحصلنا عليها هي 13 والتي تنتج من جمع قيمة العنصر الثاني (10دولار) مع العنصر الخامس (3دولار) والذان في نفس الوقت لم يتجاوزا الوزن المسموح به 10 كيلو جرام.
تكمن أهمية خوارزميات البرمجة الديناميكية في تقليل الوقت المستغرق لحساب المسائل الرياضية إذ تعمل على تخزين قيم هذه المسائل الفرعية وفي كل مرة تُصادف فيه المسألة الفرعية مرة أخرى، فإنها تبحث فقط عن القيمة بينما الخوارزميات العودية تعمل على تنفيذ ذلك بشكل متكرر، مع الاستمرار في استدعاء الوظيفة في كل مرة احتجنا إلى القيم السابقة. لمتابعة الأجزاء السابقة من سلسلة تعلم الخوارزميات اضغط هنا وهنا وهنا.
brilliant.org
smithsonian magazine
geeksforgeeks 1
geeksforgeeks 2
plus.maths
لا تزال أفكار نيتشه الفلسفية يتردد صداها في المجتمع المعاصر، وتتحدى فهمنا للأخلاق ومكانتها في…
تخيل فريقًا من العلماء الرواد يعملون بلا كلل لكشف أسرار الدماغ البشري. إنهم في سعيهم…
في عالم وسائل التواصل الاجتماعي، تظهر الصيحات وتختفي، لكن بعضها يجعلك تتساءل: ما السبب وراء…
الصداع تجربة إنسانية عالمية، وعلى الرغم من انتشاره إلا أن الأسباب الكامنة وراءه لا تزال…
إن فهم كيف بدأت الحياة وتطورت على الأرض هو السؤال الذي أذهل البشر على مر…
يصادف في شهر أغسطس الذكرى السنوية الثالثة لانسحاب الولايات المتحدة من أفغانستان وعودة طالبان إلى…
View Comments