مشاكلي الفرعية كانت تتكرر بلا نهاية: كيف أنقذتني ‘البرمجة الديناميكية’ من جحيم الحسابات الزائدة؟

يا جماعة الخير، السلام عليكم ورحمة الله.

بتذكر مرة، في بداياتي كـ “Freelancer”، مسكت مشروع صغير لشركة ناشئة. كانوا بدهم نظام يحسب احتمالات معينة لنمو عدد المستخدمين على منصتهم. المعادلة اللي وصلت إلها بعد تحليل كانت بسيطة، وشكلها рекурсивный (يعني بتستدعي حالها). فرحت على حالي وكتبت الكود بسرعة، وشغلته على أرقام صغيرة (مثلاً، حساب النمو للشهر الخامس أو السادس)، وكانت النتائج تطلع بثواني. الأمور تمام التمام.

المشكلة بلشت لما العميل طلب مني أجرب أحسب النمو للشهر رقم 40 أو 50. شغّلت الكود… واستنيت. ودقيقة ورا دقيقة، والجهاز مروحة المعالج شغالة على أعلى سرعة وصوته صار زي صوت ماتور تكسي قديم، والشاشة “علّقت”. قلت في بالي “شو القصة؟ الجهاز إمكانياته ممتازة!”.

قعدت يومين كاملين وأنا بعمل “Debugging”، بمشي مع الكود سطر سطر. ولما طبعت استدعاءات الدالة (Function calls)، انصدمت. اكتشفت إنه الكمبيوتر “زي الأهبل”، قاعد برجع بحسب نفس القيمة مئات، بل آلاف المرات! مثلاً، عشان يحسب قيمة الشهر 40، كان لازم يحسب قيمة الشهر 38 و 39. وعشان يحسب 39، كان لازم يرجع يحسب 38 و 37. شفتوا كيف قيمة الشهر 38 انحسبت مرتين؟ هسا تخيلوا هاد التكرار على مستوى 40 شهر! حسيت حالي بغرق في بحر من الحسابات اللي ما إلها داعي.

وقتها، لجأت لمهندس أقدم مني في شركة كنت أتعاون معها، وشرحت له المشكلة. ضحك وقال لي جملة لهلأ بترن في بالي: “يا أبو عمر، ليش تخلي الكمبيوتر غبي؟ علّمه يتذكر!”. ومن هنا، كانت رحلتي مع مفهوم غيّر طريقة تفكيري في حل المشاكل: البرمجة الديناميكية (Dynamic Programming).

ما هي البرمجة الديناميكية (DP)؟ مش سحر أسود!

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

الفكرة كلها بتدور حول مبدأ “التذكر” أو “التخزين المؤقت” (Caching). بدل ما الكمبيوتر يضل يحسب نفس الشغلة كل مرة، بنخليه يحفظ النتيجة في مكان ما (مثل مصفوفة أو جدول)، ولما يحتاجها مرة ثانية، بجيبها من الذاكرة بدل ما يرجع يحسبها من الصفر. بسيطة، صح؟

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

1. المشاكل الفرعية المتداخلة (Overlapping Subproblems): هذا يعني أن المشكلة الكبيرة يمكن تقسيمها إلى مشاكل فرعية أصغر، وهذه المشاكل الفرعية تتكرر وتظهر أكثر من مرة أثناء عملية الحل. هذه بالضبط كانت مشكلتي في قصة حساب النمو!
2. البنية التحتية المثلى (Optimal Substructure): هذا يعني أن الحل الأمثل للمشكلة الكبيرة يمكن بناؤه من الحلول المثلى للمشاكل الفرعية المكونة لها. مثلاً، أقصر طريق من رام الله إلى غزة عبر الخليل، هو عبارة عن مجموع “أقصر طريق من رام الله إلى الخليل” و “أقصر طريق من الخليل إلى غزة”.

مثال كلاسيكي: سلسلة فيبوناتشي (Fibonacci Sequence)

أفضل طريقة لفهم البرمجة الديناميكية هي من خلال مثال فيبوناتشي، اللي كان بالصدفة هو أساس المشكلة اللي واجهتني. معادلة فيبوناتشي بسيطة: كل رقم هو مجموع الرقمين اللي قبله (…,1, 1, 2, 3, 5, 8). رياضياً:

fib(n) = fib(n-1) + fib(n-2)

لو كتبنا هذا الحل باستخدام الـ Recursion العادي، سيبدو الكود هكذا (باستخدام Python كمثال):

# الحل الساذج باستخدام الـ Recursion
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# جرب استدعاء الدالة لرقم كبير نسبياً
# ستلاحظ بطء شديد جداً!
# print(fibonacci(40)) 

هذا الكود جميل وأنيق، ولكنه كارثي من ناحية الأداء. عند حساب fibonacci(5)، سيتم استدعاء fibonacci(3) مرتين، و fibonacci(2) ثلاث مرات، وهكذا. كلما زاد الرقم n، زادت الحسابات المتكررة بشكل أُسّي (Exponentially). وهنا يأتي دور البرمجة الديناميكية لإنقاذ الموقف بطريقتين أساسيتين.

الطريقة الأولى: التخزين المؤقت (Memoization) – النهج من الأعلى للأسفل (Top-Down)

هذه الطريقة هي الأقرب لطريقة التفكير البشرية والحل الـ Recursive الأصلي. الفكرة هي أننا سنحتفظ بنفس الدالة الـ Recursive، ولكن سنضيف “ذاكرة” (عادة ما تكون مصفوفة أو hash map) لتخزين النتائج التي حسبناها بالفعل.

قبل أن نبدأ أي عملية حسابية، نسأل: “هل حسبنا هذه القيمة من قبل؟”.

• إذا كانت الإجابة “نعم”، نرجع القيمة المخزنة مباشرة.
• إذا كانت الإجابة “لا”، نحسب القيمة، نخزنها في الذاكرة، ثم نرجعها.

هيك بكون شكل الكود:

# ذاكرة لتخزين النتائج التي تم حسابها
memo = {}

def fib_memoization(n):
    # إذا كانت القيمة موجودة في الذاكرة، أرجعها مباشرة
    if n in memo:
        return memo[n]
    
    # حالة الأساس (Base case)
    if n <= 1:
        return n
    
    # إذا لم تكن موجودة، احسبها
    result = fib_memoization(n-1) + fib_memoization(n-2)
    
    # خزّن النتيجة في الذاكرة قبل إرجاعها
    memo[n] = result
    return result

# الآن جرب استدعاء الدالة لرقم كبير
# ستلاحظ أن النتيجة تظهر فوراً!
print(f"Fib(40) using Memoization: {fib_memoization(40)}")

نصيحة من أبو عمر

طريقة الـ “Memoization” ممتازة جداً وهي غالباً ما تكون أول ما أفكر به عند تحويل حل Recursive بطيء إلى حل ديناميكي. إنها تحافظ على بنية الكود الأصلية وسهولة قراءته، مما يجعلها خياراً رائعاً للمشاكل المعقدة التي يصعب تصور حلها من “الأسفل للأعلى”.

الطريقة الثانية: الجدولة (Tabulation) – النهج من الأسفل للأعلى (Bottom-Up)

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

في حالة فيبوناتشي، أصغر المشاكل هي fib(0) و fib(1). يمكننا بناء جدول (أو مصفوفة) والبدء بملئه من البداية.

1. ننشئ جدول بحجم n+1.
2. نضع القيم الأولية المعروفة (table[0] = 0, table[1] = 1).
3. نستخدم حلقة (loop) لحساب كل قيمة بالاعتماد على القيمتين السابقتين اللتين أصبحتا معروفتين ومخزنتين بالفعل في الجدول.

الكود سيبدو هكذا:

def fib_tabulation(n):
    if n <= 1:
        return n
    
    # 1. إنشاء جدول لتخزين النتائج
    table = [0] * (n + 1)
    
    # 2. وضع القيم الأولية
    table[1] = 1
    
    # 3. بناء الحل من الأسفل للأعلى
    for i in range(2, n + 1):
        table[i] = table[i-1] + table[i-2]
        
    return table[n]

# الآن جرب استدعاء الدالة
# النتيجة فورية أيضاً!
print(f"Fib(40) using Tabulation: {fib_tabulation(40)}")

نصيحة من أبو عمر

طريقة الـ “Tabulation” غالباً ما تكون أسرع بقليل في التنفيذ الفعلي لأنها تتجنب الحمل الزائد (overhead) لاستدعاءات الدوال الـ Recursive المتكررة. إنها خيار ممتاز عندما يكون ترتيب حل المشاكل الفرعية واضحاً وبسيطاً، من الأصغر إلى الأكبر.

متى أعرف أنني بحاجة للبرمجة الديناميكية؟

هذا هو السؤال الذهبي. الممارسة هي أفضل معلم، ولكن يمكنك أن تسأل نفسك هذه الأسئلة الثلاثة عندما تواجه مشكلة ما:

1. هل يمكنني تقسيم المشكلة إلى أجزاء أصغر؟ (مثلاً، لحل مشكلة بحجم N، هل أحتاج لحل نفس المشكلة بحجم N-1 أو N-2؟).
2. هل الحل الأمثل للمشكلة الكلية يعتمد على الحلول المثلى للأجزاء الأصغر؟ (خاصية البنية التحتية المثلى).
3. هل هذه الأجزاء (المشاكل الفرعية) تتكرر وتتداخل؟ (خاصية المشاكل الفرعية المتداخلة).

إذا كانت إجابتك “نعم” على هذه الأسئلة الثلاثة، فهناك فرصة كبيرة جداً أن البرمجة الديناميكية هي الحل الأمثل لمشكلتك. ابدأ بالتفكير في الحالتين: الـ Memoization والـ Tabulation، واختر الأنسب لك.

تظهر هذه المشاكل بكثرة في مجالات مثل: مشاكل إيجاد المسار الأمثل (مثل خوارزمية Dijkstra)، مشاكل التحسين (مثل مشكلة حقيبة الظهر – Knapsack Problem)، مشاكل العد (مثل حساب عدد الطرق المختلفة لصعود سلم)، وفي الكثير من تطبيقات الذكاء الاصطناعي ومعالجة اللغات الطبيعية.

الخلاصة ونصيحة من أخوك أبو عمر

البرمجة الديناميكية ليست مجرد مجموعة من الخوارزميات، بل هي طريقة تفكير. هي فن تحويل الحلول “الساذجة” البطيئة إلى حلول “ذكية” وفعالة عبر تعليم الكمبيوتر أن “يتذكر” ما قام به سابقاً. في المرة القادمة التي تجد فيها نفسك تكتب دالة Recursive وتشعر أن الأداء بطيء، توقف لحظة واسأل نفسك: “هل أنا أطلب من الكمبيوتر أن يحسب نفس الشيء مراراً وتكراراً؟”.

إذا كانت الإجابة “نعم”، تذكر قصة أبو عمر مع مشروعه الأول، وقم بتطبيق أحد أساليب البرمجة الديناميكية. ستوفر على نفسك وعلى معالج حاسوبك الكثير من العناء والوقت. تعلم أن تفكر بـ “ديناميكية”، وسترى كيف أن العديد من المشاكل التي كانت تبدو مستحيلة الحل، تصبح في متناول يدك. 😉

وفقكم الله، والسلام عليكم.