ما هي الخوارزميات الجشعة، وفي أي الحالات تعمل؟

Question

Accepted Answer

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

## الفكرة

لا تعيد النظر في الخيارات السابقة — التزم بأفضل خيار فوري وانتقل إلى الأمام.

## مثال: تغيير العملات مع العملات الكنسية

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

هذا مثالي للعملات الأمريكية، لكن **يفشل** مع مجموعات مثل {1, 3, 4} حيث يعطي الجشع 4+1+1 لـ 6 بدلاً من 3+3.

## متى تعمل الخوارزمية الجشعة

- **البنية الجزئية المثلى:** الحل الأمثل يحتوي على حلول جزئية مثلى.
- **خاصية الاختيار الجشع:** الأمثل المحلي جزء من الأمثل العام.

أمثلة تعمل: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## التعقيد

عادة ما تكون سريعة — غالبًا O(n log n) بعد الفرز.

## المخاطر

الخوارزمية الجشعة **ليست دائمًا صحيحة**. أثبت خاصية الاختيار الجشع أو اختبرها مقابل خط أساس brute-force/DP قبل الثقة بها.

## لماذا يهم

عندما تنطبق الخوارزمية الجشعة، فإنها أبسط وأسرع بكثير من DP أو brute force.

معرفة *متى* تكون صالحة — وفي أي الحالات تعطي بصمت إجابات خاطئة — هي علامة النضج الخوارزمي.

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