الخوارزميات الجشعة (Greedy Algorithms)

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

تخيل أنك دائمًا تأخذ أكبر بسكوتة أولًا — على أمل أن يقودك ذلك لأفضل نتيجة ممكنة.

ماذا يعني Greedy؟

كلمة “Greedy” تعني محليًا أمثل — أي أنك في كل خطوة تختار القرار الذي يبدو الأفضل في اللحظة الحالية.

أحيانًا هذا يصل إلى الحل الأمثل (أفضل حل ممكن)، وأحيانًا يفشل. السر هو معرفة متى تعمل الاستراتيجية الجشعة ومتى لا تعمل.

الفكرة العامة

• لديك هدف (مثل تقليل التكلفة أو زيادة القيمة).
• في كل خطوة تأخذ الخيار الذي يبدو الأفضل الآن.
• تستمر حتى تُكمل الحل.

لا تعود لتعديل قراراتك السابقة أبدًا.

النمط العام:

while (المشكلة لم تُحل) {
    اختر أفضل خيار في الوقت الحالي;
    حدّث حالة المشكلة;
}

أمثلة مسائل

Coin change

Coin change

معك عملات: 1، 5، 10، 25 أوجد أقل عدد عملات لصنع المبلغ 63.

Solution

الفكرة الجشعة: اخذ أكبر عملة ممكنة دائمًا.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int amount = 63;
    vector<int> coins = {25, 10, 5, 1};
    int count = 0;

    for (int c : coins) {
        count += amount / c;
        amount %= c;
    }
    cout << count; // 6 coins
}

الاختيارات: 25 + 25 + 10 + 1 + 1 + 1 = 63 النتيجة = 6 عملات.

هذه الطريقة تعمل في أغلب أنظمة العملات الحقيقية.

Activity selection

Activity selection

معك مجموعة نشاطات، كل نشاط له وقت بداية ونهاية، ولا يمكنك القيام إلا بنشاط واحد في نفس الوقت. ما هو أكبر عدد نشاطات يمكنك إنهاؤها؟

Solution

الفكرة الجشعة: اختر النشاط الذي ينتهي أولًا.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<pair<int, int>> act = {{1, 3}, {2, 5}, {4, 6}, {6, 8}, {5, 7}};
    sort(act.begin(), act.end(), [](auto &a, auto &b){ return a.second < b.second; });

    int count = 0, end = 0;
    for (auto &p : act) {
        if (p.first >= end) {
            count++;
            end = p.second;
        }
    }
    cout << count; // 3
}

نختار دائمًا النشاط الذي ينتهي مبكرًا — لأنه يترك مساحة للأنشطة الأخرى.

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

تنجح عندما يكون الاختيار المحلي الأفضل يقود دائمًا إلى الحل الأفضل عالميًا.

هذا يحدث عندما تمتلك المشكلة:

• خاصية الاختيار الجشع
• خاصية البنية المثلى (optimal substructure)

لا تحتاج لحفظ هذه المصطلحات — فقط اختبر إذا كانت الجشع يعمل في كل الحالات.

أمثلة تعمل فيها الجشع

• نظام العملات (1، 2، 5) → الأكبر أولًا يعطي دائمًا العدد الأدنى.
• جدولة المهام القصيرة أولًا — يسمح بإنهاء أكبر عدد منها.
• اختيار أكبر القيم عندما توجد حدود معينة.

أمثلة تفشل فيها الجشع

• العملات {1، 3، 4} والمبلغ 6:

  • الجشع: 4 + 1 + 1 = 3 عملات
  • الأفضل: 3 + 3 = 2 عملات → الجشع يفشل هنا

• ترتيب العناصر الكبيرة أولًا عند محاولة تعبئة حقيبة — قد يمنع حلولًا أفضل.

خطوات تصميم خوارزمية جشعة

1. قم بترتيب شيء (حسب القيمة، الوقت، النسبة، …).
2. مرّ على العناصر بالترتيب.
3. اختر أفضل اختيار صالح في كل مرة.
4. حدّث الحالة (الوقت المتبقي، السعة المتبقية، …).

نمط شائع:

sort(items.begin(), items.end(), rule);
for (auto &item : items) {
    if (can_take(item)) take(item);
}

المميزات

• سريعة جدًا وبسيطة
• غالبًا \(O(n log n)\) أو أفضل
• سهلة الفهم
• مناسبة لمشاكل الجدولة والاختيار

العيوب

• لا تعطي دائمًا الحل الأمثل
• القرارات المبكرة قد تدمّر الحل لاحقًا
• يجب اختبارها أو إثباتها بعناية

نصائح

• دائمًا اسأل: هل هذا الاختيار قد يمنع حلولًا أفضل لاحقًا؟
• جرّب بناء أمثلة مضادة.
• كثير من مسائل الجشع تعتمد على فرز + اختيار.

خلاصة سريعة

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