لالچی الگورتھم (Greedy Algorithms) کیا ہیں، اور وہ کب کام کرتے ہیں؟

Question

Accepted Answer

ایک **لالچی الگورتھم** ہر قدم پر **مقامی طور پر بہترین انتخاب** کرتا ہے، اس امید میں کہ یہ عالمی بہتری کی طرف لے جائے۔ یہ سادہ اور تیز ہے، لیکن صرف تب درست ہے جب مسئلہ **لالچی انتخاب کی خاصیت** اور **بہترین substructure** رکھتا ہے۔

## خیال

ماضی کے انتخابات پر دوبارہ غور نہ کریں — بہترین فوری آپشن پر عمل کریں اور آگے بڑھیں۔

## مثال: منونی سکے کے ساتھ سکہ تبدیل کرنا

```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} جیسے سیٹس کے لیے **ناکام** ہوتا ہے جہاں لالچی 6 کے لیے 4+1+1 دیتا ہے بجائے 3+3 کے۔

## کب لالچی کام کرتا ہے

- **بہترین substructure:** ایک بہترین حل میں بہترین ذیلی حل ہوتے ہیں۔
- **لالچی انتخاب کی خاصیت:** ایک مقامی بہتری عالمی بہتری کا حصہ ہے۔

مثالیں جو کام کرتی ہیں: Dijkstra، Kruskal/Prim (MST)، Huffman coding، interval scheduling۔

## پیچیدگی

عام طور پر تیز — اکثر ترتیب دینے کے بعد O(n log n)۔

## نقصانات

لالچی ہمیشہ **درست نہیں** ہے۔ لالچی انتخاب کی خاصیت کو ثابت کریں یا اسے قابل اعتماد ماننے سے پہلے brute-force/DP baseline کے خلاف ٹیسٹ کریں۔

## اہمیت

جب لالچی لاگو ہوتا ہے، تو یہ DP یا brute force سے بہت سادہ اور تیز ہے۔

یہ جاننا کہ *کب* یہ درست ہے — اور کب خاموشی سے غلط جوابات دیتا ہے — الگورتھم کی بالغی کا نشان ہے۔

بہت سے بنیادی graph الگورتھم دل میں لالچی ہیں۔