ما معنى Greedy Algorithm؟ شرح الخوارزمية الجشعة بالأمثلة ومتى تفشل

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

كيف تعمل الخوارزمية الجشعة خطوة بخطوة

تسير معظم الخوارزميات الجشعة وفق نمط ثابت وبسيط:

1. رتّب أو حدّد المعيار: عرّف قاعدة واضحة تحدّد ما هو "الخيار الأفضل" في كل خطوة (الأصغر، الأكبر، الأقرب، الأعلى قيمة...).
2. اختر محليًا: خذ العنصر الأفضل وفق هذا المعيار من بين الخيارات المتاحة الآن.
3. حدّث الحالة: أضف الاختيار إلى الحل واستبعد ما لم يعد ممكنًا بسببه.
4. كرّر: أعد العملية حتى تكتمل المسألة أو تنفد الخيارات.

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

أشهر الأمثلة الصحيحة

في هذه المسائل ثبتت رياضيًا صحة النهج الجشع، أي إنه يعطي الحل الأمثل فعلًا:

• اختيار الأنشطة (Activity Selection): لجدولة أكبر عدد من المهام غير المتداخلة، نختار في كل مرة النشاط الذي ينتهي أبكر.
• ترميز هافمان (Huffman Coding): يُستخدم في ضغط الملفات، إذ يبني شجرة ترميز بدمج الرمزين الأقل تكرارًا في كل خطوة.
• خوارزميتا Prim وKruskal: لإيجاد الشجرة الممتدة الدنيا (Minimum Spanning Tree) في الشبكات، باختيار الحافة الأقل تكلفة المتاحة.
• خوارزمية Dijkstra: لإيجاد أقصر مسار في رسم بياني ذي أوزان غير سالبة.

متى تفشل الخوارزمية الجشعة؟ مثال يوضّح كل شيء

أفضل درس عملي يأتي من مسألة صرف العملات (Coin Change). لنفترض أن لديك فئات: 1، 3، 4، وتريد صرف المبلغ 6 بأقل عدد قطع ممكن.

• النهج الجشع يبدأ بأكبر فئة لا تتجاوز المبلغ: يأخذ 4، فيتبقّى 2، ثم يأخذ 1 و1. النتيجة: ثلاث قطع (4+1+1).
• الحل الأمثل الحقيقي هو: قطعتان فقط (3+3).

هنا فشلت الخوارزمية الجشعة لأن القرار المحلي "الأكبر أفضل" أغلق الباب أمام تركيبة عامة أفضل. الدرس المهم: النهج الجشع لا يصلح إلا إذا أثبتّ أن للمسألة خاصية الاختيار الجشع (greedy choice property) والبنية المثلى الجزئية. لا تفترض صحته لمجرد أنه يبدو منطقيًا.

الجشعة أم البرمجة الديناميكية؟

كثيرون يخلطون بين النهجين لأن كليهما يبني الحل تدريجيًا. الفرق الجوهري في الجدول التالي:

المعيار	الخوارزمية الجشعة	البرمجة الديناميكية
طريقة القرار	خيار محلي واحد لا يُراجَع	تستكشف عدة خيارات وتحتفظ بالأفضل
السرعة	أسرع عادةً	أبطأ لكنها أشمل
استهلاك الذاكرة	منخفض	أعلى (تخزين نتائج جزئية)
ضمان الحل الأمثل	ليس دائمًا	نعم إن صيغت المسألة صحيحًا
مثال	صرف العملات القياسي، هافمان	صرف العملات بأي فئات، حقيبة 0/1

القاعدة العملية: إن كانت فئات العملات "قياسية" مثل عملات معظم الدول، يكفي النهج الجشع. أما مع فئات عشوائية، فالبرمجة الديناميكية هي الضمان الوحيد للحل الأمثل.

مزايا وعيوب باختصار

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

العيوب: قد تعطي حلًّا قريبًا من الأمثل لكن ليس الأمثل، وتتطلّب إثباتًا رياضيًا لصحتها قبل الاعتماد عليها.

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

الأسئلة الشائعة

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

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

ما الفرق بينها وبين خوارزميات القوة الغاشمة (Brute Force)؟ القوة الغاشمة تجرّب كل الاحتمالات الممكنة وتضمن الحل الأمثل لكنها بطيئة جدًا. الجشعة تتّخذ مسارًا واحدًا سريعًا دون تجريب البدائل، فتربح السرعة وتخاطر بالدقة.

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