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

تُعد البرمجة الديناميكية (Dynamic Programming) منهجية قوية في علم الحاسوب تهدف إلى حل المشكلات المعقدة عن طريق تقسيمها إلى مسائل فرعية أصغر. ولكن، على عكس بعض المنهجيات الأخرى، لا تُحل هذه المسائل الفرعية بشكل مستقل. الشرط الأساسي لتطبيق البرمجة الديناميكية هو أن تكون هذه المسائل الفرعية متداخلة (overlapping sub-problems)، مما يعني أن حل مسألتين فرعيتين أو أكثر قد يؤدي إلى نفس النتيجة. لتجنب إعادة الحسابات غير الضرورية، نستخدم تقنية التخزين المؤقت للنتائج (memoization) لتذكر نتائج المسائل الفرعية التي تم حلها مسبقًا. تُخزّن هذه النتائج في ذاكرة مؤقتة (cache storage) وتُسترجع عند مواجهة مسألة فرعية مماثلة في المستقبل، مما يقلل بشكل كبير من وقت التنفيذ. دعونا نتعمق أكثر في هذا المفهوم.

ما هو التخزين المؤقت للنتائج (Memoization)؟

التخزين المؤقت للنتائج (Memoization) هو أسلوب برمجي يقوم على حفظ نتائج استدعاءات الدوال التي تتم بنفس المعاملات. بعبارة أخرى، هو شكل متخصص من أشكال التخزين المؤقت (caching). يضمن هذا الأسلوب تخزين النتائج المحسوبة مسبقًا، عادةً في بنية بيانات مثل جدول التجزئة (hashmap)، ليتم الوصول إليها لاحقًا عند الحاجة لحل مسائل فرعية مشابهة. يساهم هذا النهج في تقليل وقت تشغيل البرنامج بشكل ملحوظ ويؤدي إلى كتابة كود أقل تعقيدًا. ومع ذلك، وكما هو الحال مع أي تحسين، يأتي هذا الفائدة بتكلفة. عند استخدام البرمجة الديناميكية مع التخزين المؤقت للنتائج، تتحسن التعقيد الزمني (time complexity) على حساب زيادة في التعقيد المكاني (space complexity) نتيجة لتخزين النتائج.

النهج المختلفة في البرمجة الديناميكية (DP)

في البرمجة الديناميكية، يمكننا اعتماد إحدى طريقتين رئيسيتين: النهج من الأعلى للأسفل (Top-Down) أو النهج من الأسفل للأعلى (Bottom-Up).

النهج من الأعلى للأسفل (Top-Down)

يتضمن هذا النهج البدء بحل المشكلة الرئيسية بشكل مباشر، مع التحقق في كل خطوة مما إذا كنا قد حسبنا حل المسألة الفرعية المعنية مسبقًا. يعتمد هذا الأسلوب بشكل كبير على الاستدعاءات التكرارية (recursive calls) للدوال، مما يؤدي إلى بناء مكدس استدعاءات (call stack) يستهلك الذاكرة. كما أنه عرضة لأخطاء تجاوز سعة المكدس (stack overflow errors) في حال كانت الاستدعاءات التكرارية عميقة جدًا.

النهج من الأسفل للأعلى (Bottom-Up)

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

مقارنة بين النهجين

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

ملاحظة هامة: البرمجة الديناميكية ليست خوارزمية!

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

مثال عملي: إيجاد أطول تسلسل مشترك (Longest Common Subsequence – LCS)

لتعزيز فهمنا لكيفية عمل البرمجة الديناميكية فعليًا، دعونا نتناول مشكلة عملية: إيجاد أطول تسلسل مشترك (LCS) بين سلسلتين معطاة. على سبيل المثال، السلسلتان 'gtcab' و 'gxtxab'.

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

كيف نحدد ما إذا كانت المشكلة قابلة للحل بالبرمجة الديناميكية؟

السؤال هنا هو: كيف نعرف أن هذه المشكلة تحديدًا يمكن حلها باستخدام البرمجة الديناميكية؟ الإجابة تكمن في تحديد ما إذا كانت تحتوي على مسائل فرعية متداخلة.

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

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

منهجية المصفوفة لإيجاد أطول تسلسل مشترك

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

بناء المصفوفة وتعبئتها

نقوم بإنشاء مصفوفة ثنائية الأبعاد حيث يمثل الصف الأول السلسلة الأولى ويمثل العمود الأول السلسلة الثانية. ثم نملأ الصف الثاني والعمود الثاني بالأصفار لتهيئة المصفوفة قبل بدء الخوارزمية. نرمز للصفوف بالحرف 'i' وللأعمدة بالحرف 'j'.

الآن ننتقل إلى تعبئة خلايا المصفوفة. تتم المقارنة بين السلسلتين حتى الحرف الأخير من السلسلتين الفرعيتين قيد المقارنة.

• إذا لم تكن الأحرف الأخيرة من السلسلتين المتطابقتين متساوية، فإن قيمة الخلية الحالية (T[i][j]) ستكون القيمة الأكبر بين الخلية الموجودة على يسارها (T[i][j-1]) والخلية الموجودة فوقها (T[i-1][j]).
• إذا كانت الأحرف الأخيرة من السلسلتين متساوية، يتم تعبئة الخلية بزيادة قيمة الخلية القطرية العلوية اليسرى (T[i-1][j-1]) بمقدار 1.

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

 if (input[i]==input[j]) //Check if last characters are equal
 T[i][j]=T[i -1 ][j -1 ]+ 1 //Entry is incremental of upper left element
 else //If the last character are not equal
 T[i][j]=max(T[i -1 ][j], T[i][j -1 ]) //Entry is max of element to its left and top

في نهاية المطاف، ستعطينا القيمة الموجودة في الزاوية السفلية اليمنى من المصفوفة طول أطول تسلسل مشترك (LCS).

استخراج أطول تسلسل مشترك من المصفوفة

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

• إذا كانت القيمة الحالية هي نفس قيمة الخلية العلوية أو اليسرى (أي T[i][j] == T[i-1][j] أو T[i][j] == T[i][j-1])، فهذا يعني أن الحرف الحالي ليس جزءًا من التسلسل المشترك، وننتقل إلى الخلية التي جاءت منها القيمة الأكبر.
• إذا كانت القيمة الحالية أكبر من قيمة الخلية القطرية العلوية اليسرى بمقدار 1 (أي T[i][j] == T[i-1][j-1] + 1)، فهذا يشير إلى أن الأحرف المقابلة في السلسلتين متطابقة، وأن الحرف الحالي هو جزء من التسلسل المشترك. في هذه الحالة، نضيف هذا الحرف إلى التسلسل وننتقل قطريًا إلى الخلية العلوية اليسرى (T[i-1][j-1]).

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

الخلاصة التقنية

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

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