متى تستخدم الخوارزميات الجشعة ومتى يجب تجنبها؟ مع أمثلة تطبيقية

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

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

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

ملاحظة: كثير من الأمثلة هنا تعتمد على مفهوم Graphs أو الرسوم البيانية، لذا ستكون الاستفادة أكبر إذا كانت لديك معرفة أساسية بالعُقد والحواف والمسارات.

ما هي الخوارزميات الجشعة؟

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

تمتاز هذه الخوارزميات بأنها:

• أسرع غالباً من أساليب مثل Dynamic Programming.
• أبسط في التطبيق والفهم في عدد كبير من الحالات.
• لا تستكشف فضاء الحلول بالكامل، ولهذا فهي أقل كلفة حسابياً.

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

كيف تعمل الاستراتيجية الجشعة عملياً؟

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

من المهم هنا التمييز بين نوعين من المسائل:

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

أمثلة على مسائل تنجح فيها الخوارزميات الجشعة

خوارزمية Dijkstra لإيجاد أقصر المسارات

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

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

فيما يلي صياغة شبه برمجية مبسطة لها، حيث يمثّل G الرسم البياني وs عقدة البداية:

Dijkstra(G, s):
    distances <- list of length equal to the number of nodes of the graph,
                 initially it has all its elements equal to infinite
    distances[s] = 0
    queue = the set of vertices of G

    while queue is not empty:
        u <- vertex in queue with min distances[u]
        remove u from queue

        for each neighbor v of u:
            temp = distances[u] + value(u,v)
            if temp < distances[v]:
                distances[v] = temp

    return distances

بعد تنفيذ الخوارزمية، نحصل على قائمة distances بحيث تمثل distances[u] أقل تكلفة للوصول من العقدة s إلى العقدة u.

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

مسألة الحقيبة الكسرية Fractional Knapsack

من الأمثلة الكلاسيكية أيضاً مسألة Fractional Knapsack. لدينا مجموعة عناصر، لكل عنصر وزن Wi أكبر من الصفر وقيمة ربح Pi أكبر من الصفر، ولدينا حقيبة بسعة قصوى W. المطلوب هو تحقيق أكبر ربح ممكن دون تجاوز السعة.

في النسخة الكسرية من المسألة، يمكننا أخذ العنصر كاملاً أو أخذ جزء منه فقط. إذا أخذنا نسبة X بحيث 0 <= X <= 1 من العنصر رقم i، فسنحصل على ربح يساوي X * Pi ونضيف إلى الحقيبة وزناً مقداره X * Wi.

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

متى تصبح الخوارزميات الجشعة خياراً سيئاً؟

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

فشل Dijkstra مع الأوزان السالبة

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

في هذا المثال، تفشل الخوارزمية في إيجاد المسافة الصحيحة بين A وC. فقد تحسب أن d(A, C) = 0 بينما القيمة الصحيحة هي -200. وإذا جرى تقليل قيمة الحافة D -> B أكثر، فسيصبح الخطأ أكبر.

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

مسألة الحقيبة 0-1 Knapsack

عندما لا يُسمح بتجزئة العناصر، ننتقل إلى نسخة مختلفة هي 0-1 Knapsack. هنا إما أن تأخذ العنصر كاملاً أو تتركه. في هذه الحالة، لا يعود الاختيار الجشع المبني على نسبة القيمة إلى الوزن مضموناً.

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

مسألة البائع المتجول TSP

مسألة Travelling Salesman Problem أو TSP تسأل عن أقصر مسار يزور جميع المدن مرة واحدة فقط ثم يعود إلى نقطة البداية.

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

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

متى تكون الخوارزميات الجشعة مفيدة حتى دون حل مثالي؟

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

في هذه الحالات، لا نطلب من الخوارزمية الوصول إلى أفضل حل ممكن، بل نطلب منها حلاً قريباً من الأفضل ضمن تكلفة تنفيذ منخفضة.

تقريب مسألة غطاء الرؤوس Vertex Cover

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

لكن يمكننا الحصول على تقريب جيد باستخدام خوارزمية جشعة بسيطة:

1. اختر أي حافة <u, v> من الرسم البياني.
2. أضف العقدتين u وv إلى مجموعة الغطاء.
3. احذف كل الحواف المتصلة بـ u أو v.
4. كرر العملية حتى لا تبقى أي حافة.

وهذه صياغة شبه برمجية لهذه الفكرة:

vertexCover(G):
    VertexCover <- {}   // empty set
    E' <- edges of G

    while E' is not empty:
        VertexCover <- VertexCover U {u,v} where <u,v> is in E'
        E' = E' - {<u, v> U edges incident to u, v}

    return VertexCover

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

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

مقارنة سريعة بين حالات النجاح والفشل

كيف تعرف إن كانت الاستراتيجية الجشعة مناسبة لمسألتك؟

قبل اعتماد أي حل جشع، اطرح على نفسك الأسئلة التالية:

• هل يمكن إثبات أن أفضل اختيار محلي يقود إلى أفضل حل عالمي؟
• هل تمتلك المسألة خاصية البنية المثلى Optimal Substructure؟
• هل يؤدي القرار الحالي إلى تقييد خطير للخيارات المستقبلية؟
• هل نبحث عن حل مثالي أم عن تقريب جيد وسريع؟
• هل توجد حالات مضادة معروفة تكسر النهج الجشع؟

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

لماذا تحظى الخوارزميات الجشعة بأهمية كبيرة؟

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

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

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

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

الخوارزميات الجشعة أداة قوية عندما تتوافق بنية المسألة مع فكرة الاختيار المحلي الأمثل، كما في Dijkstra للأوزان غير السالبة وFractional Knapsack. لكنها قد تكون مضللة جداً في مسائل مثل 0-1 Knapsack وTSP أو عند وجود حواف سالبة. القيمة الحقيقية لهذا النهج تظهر أيضاً في الخوارزميات التقريبية، حيث يمكن الوصول إلى حلول جيدة بسرعة وبتكلفة تنفيذ منخفضة. من الناحية التقنية، لا ينبغي تبني استراتيجية جشعة إلا بوجود برهان صحة واضح أو ضمان تقريبي مضبوط.