العقلية الجشعة

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

في كل لحظة، اطرح على نفسك سؤالًا واحدًا: أي خيار يساعد أكثر محليًا؟ اختره، ثم انتقل إلى القرار التالي.

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

لأنها تتخذ قرارًا واحدًا في كل خطوة، تعمل الخوارزمية الجشعة عادةً بزمن O(n) أو O(n log n) بعد الفرز. وهذه السرعة أهم ما يميزها في المسابقات.

تبدأ معظم الحلول الجشعة بعملية فرز العناصر. إذ يكشف الترتيب العنصر الذي يبدو الاختيار الأفضل بوضوح في كل مرحلة.

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

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

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

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

هذا هو الشكل العام لمعظم الخوارزميات الجشعة: رتّب العناصر، ثم مرّ عليها مرة واحدة، واختر كل ما يطابق قاعدتك.

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

تقرر ما إذا كان النهج الجشع جديرًا بالثقة.

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