48. الخوارزميات الجشعة (Greedy): الخصائص والمزالق
تبني الخوارزميات الجشعة حلاً قطعة قطعة، وتختار دائماً القطعة التالية التي توفر الفائدة الأكثر وضوحاً وفورية.
الخصائص الرئيسية
- البنية المثلى (Optimal Substructure): يحتوي الحل الأمثل للمشكلة على الحل الأمثل لمشكلاتها الفرعية.
- خاصية الاختيار الجشع (Greedy Choice Property): يمكن الوصول إلى حل أمثل عالمياً عن طريق اتخاذ خيار أمثل محلياً (جشع) في كل خطوة.
المزالق: عندما يفشل الجشع
على الرغم من كون النهج الجشع بسيطاً وسريعاً، إلا أنه لا يؤدي دائماً إلى أمثل عالمي. إنه يعمل فقط إذا أظهرت المشكلة خاصية الاختيار الجشع.
- مثال: تخيل نظام عملات بفئات {1, 7, 10}. إذا كنت بحاجة إلى صنع 15 سنتاً، فقد يختار النهج الجشع 10، ثم 1، 1، 1، 1، 1 (6 عملات). الحل الأمثل هو 7 + 7 + 1 (3 عملات).
إذا كان الاختيار الجشع خاطئاً، فلا توجد آلية للتراجع وتصحيحه.